我说的O(n) 是用2叉树列出来所有的给定的一个person的所有的祖先. -boolean(北漂一族) @佛州华人论坛:佛州枫下论坛 The Rolia Forum of Florida

工作学习 / 学科技术讨论 / 有一道Java面试题能不能帮我看看? -sallay(sallay); 2014-12-2 {262} (#9131730@0)
今天online test，问了我一道Java面试题，‘Person’ class 有String name, int age, char sex, Person spouse, Person mother, Person father, List<Person> children, 让我写method，找到list of all older sisters和list of all ancestors，这道题主要想考察什么？怎么写比较好？

说实话，这题真心不难！考你什么？就是基本的代码编写加上点数据结构的东西。 -boolean(北漂一族); 2014-12-2 (#9131902@0)
我个人感觉这个题目就是上大学的一个课后作业的题目。^_^ 如何做？帖子里面敲字儿太麻烦 :-) -boolean(北漂一族); 2014-12-2 (#9131910@0)
list all older sisters 这个最简单。list of all ancestors 稍微动点脑筋，其实也木有啥，就做个类似的2叉树的遍历就搞定了！你递归遍历一下2叉树就搞定了。思路就是这个思路 ^_^ -boolean(北漂一族); 2014-12-2 (#9131916@0)

recursive -ysysning(樱桃三果); 2014-12-2 (#9131918@0)

恩是的就是这个思路。递归结束条件就是mother or father is NULL，然后剩下的打印出来就可以了。 -boolean(北漂一族); 2014-12-2 (#9131922@0)
唯一没有太考虑仔细的就是乱轮的情况下，如何处理？不过估计面试的题目不会让他考虑的那么复杂！ ^_^ -boolean(北漂一族); 2014-12-2 (#9131925@0)

但是我觉得不是binary tree，因为有几个root（祖先） -sallay(sallay); 2014-12-2 (#9132021@0)

有几个root? 你就是root 啊! 哪里来的那么多root啊? 打个比方你是root , 左节点是你的爸爸, 右节点是你的妈妈. 同理你爸爸的左节点是你的爸爸的爸爸(你的爷爷), 你爸爸的右节点是你爸爸的妈妈(你的奶奶). 以此类推, 不就是个2叉树吗? -boolean(北漂一族); 2014-12-3 {55} (#9132104@0)
你遍历的时候, 把他们打印出来就好了. 不知道我说的清楚不?

有几个情况啊，根节点的 spouse在二叉树里怎么表示？一对父母有多个孩子怎么处理？孤儿怎么办-多个根节点？二叉树需要建还是假定已经built好？那个list是打乱排的吗？有复杂度的要求吗？ -changjin(被套住了); 2014-12-3 (#9132193@0)

根节点的 spouse 如何表示? 貌似楼主这个题目的需求跟根节点的spouse 木有啥关联吧? -boolean(北漂一族); 2014-12-3 {676} (#9132259@0)
有几个情况啊，根节点的 spouse在二叉树里怎么表示？
楼主的题目需求貌似跟根节点的spouse 木有啥关联.

一对父母有多个孩子怎么处理？
题目是要一个人的ancestors , ta 的兄弟姐妹跟列出来 ancestors 木有啥关联.

孤儿怎么办-多个根节点？
孤儿就是根节点. 木有明白孤儿为啥需要多个根节点?

二叉树需要建还是假定已经built好？
2叉树肯定是要自己build的了 . ^_^ . 如果已经给你一个build 好的2叉树那是最好了.
但是我想题目的要求应该是自己build 自己遍历.

那个list是打乱排的吗？有复杂度的要求吗？
list 打乱排? 题目的要求是列出来 ancestors , 你可以把他们放到一个 list or array or a map or a hash map , what ever a data structer u like. 或者根本就不存到哪里. 直接打印出来就好了.
^_^

从头说吧。左节点father右节点mother的二叉树，是不是假定一对父母只有一个孩子？如果是，为什么还要问有多少older sisters? -changjin(被套住了); 2014-12-3 (#9132316@0)

相应回答请进! ^_^ -boolean(北漂一族); 2014-12-3 {780} (#9132435@0)
从头说吧。左节点father右节点mother的二叉树，
你的理解非常正确!

是不是假定一对父母只有一个孩子？如果是，为什么还要问有多少older sisters?
我木有假定一对父母只有一个孩子. 有n个孩子都无所谓.
但是题目要求只是一个person的祖先吧 ? 所以 ....

多说无益
我下面的是 Person class 伪代码
Class Person{
...
List<Person> Sib_list;
BST <Person> Ancestor_tree;
....

};

你这个person 如果兄弟姐妹就insert 那个 Sib_list; 里面
如果有父母就insert 到那个 Ancestor_tree 里面.
如果这个 Ancestor_tree 是空的话, 那么这个就是这个人的曾曾曾祖父母了. 估计是猿人了! ^_^ .

根据题目的要求, 你列兄弟姐妹就把那个Sib_list 打印出来就好了.
如果要列出祖先就把 Ancestor_tree 列出来就好了. 即 2叉树的遍历当然你是前序后序还是中序遍历看实际需要了啊.

再说说估计代码都快敲出来了 ^_^

给定the person和list, constructing a BST for ancestors 的代价是多少？worst case O(n^2)对吗？没有任何优势，不如直接一遍一遍扫list,也是O(n^2), 空间开销更小，不需要BST. -changjin(被套住了); 2014-12-3 (#9132693@0)

没有太明白你的意思! -boolean(北漂一族); 2014-12-3 {864} (#9132750@0)
给定the person和list, constructing a BST for ancestors 的代价是多少？worst case O(n^2)对吗？
worst case O(n^2)???? 不会是 O(n^2) 啊? 不知道你哪里得到的这个时间复杂度的啊?

一个人大部分意义上来说都是有父母的吧? 如果clone 这样的极端case 除外. 那么找相应的节点插入在BST 里面最不济就是 O(n) 啊咋 n square 呢?
时间主要是浪费在查找上了啊咋会是 n square的时间复杂度呢?
打个比方如果给定一个女士是root的祖先 , 那你肯定要找右子树的最右边的节点, 那么这个时间复杂度就是 O(n) 吧?
最烂的应该是 O(n) 我想. N square 不知道是如何算出来的?

没有任何优势，不如直接一遍一遍扫list,也是O(n^2), 空间开销更小，不需要BST
扫一个list 时间复杂度也是 O(n)啊哪里出来的 O(n^2) 呢?
需要BST 意思就是一个2叉树表示一个人的父母的关系. 不用2叉树你用list ? 一个list 表示父亲那支儿? 一个list 表示母亲那支儿? 是这样吗?
如果这样的话你不感觉麻烦? ^_^

也可能木有搞懂你的意思!

O(n)是从给出的list中找到一个ancestor的时间，n is size of the list, 找到所有ancestor for the given person需要O(n^2). 你的BST是要找chain of ancestor去build的吧？你是把结果存到了二叉树里面，二叉树本身的优势没有起到作用。不如直接扫list,顺带输出。 -changjin(被套住了); 2014-12-3 (#9132953@0)

我还是木有明白你的时间复杂度为啥是 n square 呢? -boolean(北漂一族); 2014-12-3 {1289} (#9133067@0)
本文发表在 rolia.net 枫下论坛O(n)是找到一个ancestor的时间，找到所有ancestor for the given person需要O(n^2).
找到所有的ancestor 就是个遍历2叉树的时间复杂度, 咋能算出来 n^2 呢?
ok. 打个比方从建好的一个ancestor 的2叉树中, 找到一个特定的节点的ancestor 这个时间复杂度是 O(n) 吧?

然后我可以把这个节点当做一个root 返回到function 外面吧?

Node * getNode( BST * aNode ) --------------> 查找一个特定的节点.
{
....
}

aRoot = getNode( BST * aNode ); ---------> 找到特定节点赋值给 aRoot
void printAncestor( aRoot ) ------------------> 遍历aRoot的 2叉树打印出来所有的ancestors
{
.....
display aNode;
....
}

这个时间复杂度就是O(n) 不知道咋能是 n square 呢? 就是个遍历 n 个节点的过程. 你的函数的输入节点数并没有增加, 而且我的节点只是被遍历一次.(当然我里面有动态编程的优化,保证一个节点只是被遍历一次)
为何是 n suqare 呢?

你的BST是要找所有ancestor的吧？你是把结果存到了二叉树里面，二叉树本身的优势没有起到作用。不如直接扫list,顺带输出
----- 我的BST 或者说不能说是 BST. 其实就是个简单的2叉树而不是 Binary Search Tree. 我是通过用户的输入构造的2叉树.
构造好了再遍历找一个特定的person的祖先.

你说的直接扫 list? 你说的这个list 是啥list? 就是不管啥关系只要是祖先就往这个list 里面塞? 一个人的爷爷往里面塞, 爸爸往里面塞, 只要是>他上一辈儿的都往这个list 里面塞?
是这个意思吗? 还是 ....?更多精彩文章及讨论，请光临枫下论坛 rolia.net

基本上不关二叉树什么事, 查找也不是在二叉树里找到要insert的位置。原题给出的是一个list, O(n^2) 是扫描list的worst case 时间。至于你把结果放在二叉树或是什么地方，不是这题要考察的, 输出就好。 -changjin(被套住了); 2014-12-3 (#9133207@0)

扫描list的worst case 是 O(n^2) ? 不知道你说的list 是不是linklist 还是啥其他的list? 据我所知linklist的遍历是 O(n). -boolean(北漂一族); 2014-12-3 (#9133234@0)

O(n)是从给出的list中找到一个ancestor的时间，n is size of the list, 这是你知道的。但找到all ancestors of a person需要O(n^2). 这句有疑问吗？ -changjin(被套住了); 2014-12-3 (#9133290@0)

java的 list 貌似好像有个叫做 arraylist的吧 ? 不管java的list 背后如何实现的, 我想大约跑不出single link list 跟 double link list. -boolean(北漂一族); 2014-12-3 {754} (#9133376@0)
我貌似大约知道你说的这个list 是啥了, 就是所有的person 都塞到这个list 里面是吧?
就是兄弟姐妹, 父母姥姥老爷啥的都塞到这个list 里面?

那么这些person 之间的关系你如何表示? 兄弟姐妹以及父母爷爷老爷你如何表达?
难道再用n个指针去指来指去? 还是通过地址的索引? n + 1 代表爸爸 n + 2 代表妈妈?
我想起这个数据结构就头疼. 感觉这样的设计是给自己找麻烦.

清清爽爽的设计就是兄弟姐妹一个 list
然后祖先关系搞个 2叉树 , 简单清爽. 如果以后用户的需求改变, 你也很好的能handle.

简单的说就是跟这个 person 同level 的一个数据结构. 水平方向的.
比这个person 高一辈儿以上的一个数据结构. 竖直方向的.

像你这样的设计, 如果哪天用户说, 你把我所有的男士的祖先给我罗列出来. 我不知道
你那种数据结构如何实现? 反正我想想脑袋懂疼! 也怪我脑仁儿小! ^_^

so O(n^2)不再是问题？这题给出的就是一个这样所有人都randomly packed together的list，现实往往也是这样。设计一个数据结构清楚地表示这所有人之间的关系，还得让增删改查快捷有效，那时另外一回事，不是这题要考察的。如果一定要做，也不是二叉树，是有向图。 -changjin(被套住了); 2014-12-3 (#9133418@0)

如果一个developer 就这个问题设计成把所有都往一个这样的list 里面塞的话, 呵呵我只能说这个developer该打屁股了! -boolean(北漂一族); 2014-12-3 {290} (#9133450@0)
你自己实现实现看看复杂程度有多少吧? 还不算以后用户的需求有木有变化? BTW , 啥样的数据结构我们可以自己封装的啊. 用户关心的是功能而不是你如何实现的. 是吧?
如果我们team 有这样的设计软件的话, 起码 code review 在我这里肯定是过不去的. 所有的东西都塞到一个list 里面? 那脑袋缺氧得到啥程度啊? 嘿嘿

混沌无序正是现实本色。不管你怎样设计，用什么数据结构，总需要把那些散乱无序的原始数据load进你的数据结构里去吧。你的二叉树+LIST只是for any given person,not for all people, 所以并没有make situation any better. -changjin(被套住了); 2014-12-3 (#9133487@0)

如果你这么说的话, 那CS 就好学了, 要啥array list tree map 啥的啊反正都是随便往一个数据结构里面装就是了! ^_^ 应该起名字叫做大一统的数据结构. 哎 ... union 还真有啊在 C 里面 ^_^ -boolean(北漂一族); 2014-12-3 {224} (#9133515@0)
我设计的 2叉树起码像如果用户说把所有的男的祖先列出来, 起码比放到一个list 里面好实现吧? 其他的需求还真的不知道能有啥花花样呢.
还有找ancestors 也是能达到 O(n) 而不是 O(n^2) 这样的performance 还不满意的话, 那我也无话可说了!

正常的做法是step 1 原始数据放在简单数据结构中,step 2 load进一个well-designed 的数据结构(不是二叉树)中，step 3 所有的操作都应该是基于后一个数据结构的, 理论上说不需要go back to the original list.. 你的二叉树设计则不然，for any person you need to start from -changjin(被套住了); 2014-12-3 {102} (#9133575@0)
原始数据. and pls show us how to make it O(n) worse case to get all ancestors of a person from a list?

我说的O(n) 是用2叉树列出来所有的给定的一个person的所有的祖先. -boolean(北漂一族); 2014-12-3 {546} (#9133631@0)
我真心不知道这么简单的一个问题还列出来啥 step 1 2 3? 来啥叫要开始放到一个简单的数据结构里面啊? 然后再step 2 放到well design的数据结构啊?
假如你从数据库当做拿出来一个person 说这个人是谁谁的兄弟姐妹然后你就看跟你这个人里面包含的人有木有关系就ok了啊. 有关系就插到相应的数据结构就好了啊.
我的数据结构一开始就是well design的啊要啥一开始还放到一个简单的数据结构里面啊? 然后再倒到well design的数据结构里面? 这不是多次一举吗?

其实要考的题目很简单, 就是让你建立个一个人的关系图, 然后把人家的需求也就是兄弟姐妹还有祖先打印出来. 就这么简单.

数据库里的数据对程序员来说很多时候就是原始数据。二叉树是个好东西，可跟这题根本不相干，你把本来扫描过程打印出来就好的结果硬放在了二叉树里，还只是给某一个人的。下个人过来你再build个新的二叉树。不知道你认为原题的那个list应该是怎么样的。 -changjin(被套住了); 2014-12-3 (#9133807@0)

哎... 看来你还是木有搞懂具体设计啊 . -boolean(北漂一族); 2014-12-3 {2049} (#9133887@0)
本文发表在 rolia.net 枫下论坛1. 我建立一个 Person 名字叫做"小明" 可以不?
2. 我访问数据库说小明的兄弟姐妹都有谁啊? 数据库返回给我几个人的属性是吧?
我根据相应的属性可以创建相应的人吧? 也就是 new 相应的person 可以吧?
3. 我把 2 创建相应人的指针 or Java 里面所说的reference 放到我的一个存着小明的兄弟姐妹 Person 指针的 list 里面可以不? 这个list 类似于 List<Person *> Sib_list.
这样我就创建好了小明兄弟姐妹的数据结构了吧?
4. 我访问数据库说小明的爸爸妈妈是谁啊? 好了数据库返回给我小明的爸爸妈妈了是吧? 同样的我那个小明 person 里面有个2叉树左儿子存的是爸爸的 Person 的指针
右儿子存的是小明妈妈的 Person 指针可以不? BTW 小明的爸爸的爸爸妈妈指针这个时候是NULL. 小名的妈妈的爸爸妈妈的指针这个时候也是 NULL.
然后我把小明的爸爸妈妈的指针也插到这个2叉树里面了吧?

5. 目前为止小明的这个对象的所有属性我都构造好了吧?

到了这一步:

那么我就一个Person 小明里面数据结构就有:
1. 一个 List<Person*> 里面含有的全是兄弟姐妹的指针!
2. 一个 2叉树 . root 就是小明
root 的左儿子指针指向的是小明爸爸 .
root 的右儿子指针只想的是小明的妈妈

如果你说小明的爸爸的爸爸妈妈都是谁那你就继续访问数据库生成个 2个相应的 Person* 指针然后把这 2个指针挂到相应的小明爸爸的左儿子那里还有右儿子指针上就好了啊.
其他的就都是同理可证了啊!

这个有啥难的呢? 为啥你说我建一个person 就要一个2叉树呢? 我不会存一个2叉树的指针吗? 就4个字节而已. 有啥浪费的呢?

如果需要说打印出来小明的兄弟姐妹来 , 那么我就iterator 我这个 List<Persion *> 然后打印出来相应的name 就可以了吧?
如果需要说打印出来小明的所有的祖先来 , 那我就iterator 我这个 2叉树可以不? 就中序啊还是前序啥的遍历一遍然后打印就好了.

我还可以提供打印出来小明全部男性的祖先的名字.
还可以打印出来小明全部女性祖先的名字.

我还可以打印出来跟小明差几个备份的祖先的名字.

你如果用一个 list 来把所有的人都塞进去, 您如何实现呢?

我跟 Java的程序员讨论代码真的是很捉急!! 还有啥问题 , 你可以继续发问! 我把回答你的问题也post 到发问的下面要不人家找不到了快!
其实如果明白人我说这2个数据结构就立马就清楚了. 没有必要我这么长篇大论的 ^_^更多精彩文章及讨论，请光临枫下论坛 rolia.net

这题本无设计可言，纯coding. 下面的c# code 是对的。它的二叉关系(实际上是三叉，加spouse，只不过那样就不像树了)是题目本身带来的，不需要你费事费力再build一回。 -changjin(被套住了); 2014-12-3 (#9133924@0)

就这个题目的设计, 我提供的思路也是一家之言. 不知道其他人的思路是啥样的? 不过我是不能接受把所有的东西都塞到一个list 里面这样的design 的. ^_^ -boolean(北漂一族); 2014-12-3 (#9133457@0)

你真的被你的想法套住了。你可能对这道题的数据结构理解有问题。北漂是对的。题目是很直接的。 -calgarycat(POCO大猫); 2014-12-3 (#9133147@0)
还有你说的这个list , 我想不到如何构建? 是 link list? 还是... -boolean(北漂一族); 2014-12-3 {246} (#9133172@0)
打个比方来了个新的person , 说是某人的祖先, 你从list 找出来某人的位置来, 然后再插到这个某人节点的后面? 再调整原先的指针?
你是这个意思吗? 还是啥数据结构来表示啊? 貌似最好把需要的数据结构列出来一下, 然后简单的描述一下如何插入查找遍历比较好 ^_^

list是原题给出的，乱七八糟一堆人全在这个list里，除此之外不需要额外的数据结构。如果一定要有，可以有一个accompany list用来减少比较的次数，but worst case scan time still O(n^2). -changjin(被套住了); 2014-12-3 (#9133218@0)

我认为她列出来的原题可能有误! BTW, OO design 来说, 我们就封装好了就可以了! -boolean(北漂一族); 2014-12-3 {181} (#9133392@0)
你不就是要list old sisters吗? 不就是要list 出来ancestors吗? 我提供功能, 不需要开放我的数据结构. 是吧? 封装的越好, 以后的就越flexible. 不要给用户public 那么多的东西, 让他们瞎搞哦 ^_^

其实说白了, 楼主的这个题目的 person class 里面主要就存2个数据结构就是了! -boolean(北漂一族); 2014-12-3 {152} (#9132267@0)
1. 一个list 或者whatever 一个数据结构保存这个person的兄弟姐妹的信息.
2. 一个 binary tree 存祖先的信息.

Thats it! 然后就遍历这2个数据结构就好了.

p.father.children.addAll(p.mother.children).where(sib-> sib.sex="F" and sib.age>p.age) -sxffff(lookingforjob); 2014-12-3 (#9132338@0)

貌似木有你说的那么麻烦吧? -boolean(北漂一族); 2014-12-3 {701} (#9132372@0)
流程as below:

1. Create a person class.
2. Create a person obj as a root . 就是你要列出祖先的一个 person 的obj
3. Create a person 如果是这个root 的兄弟姐妹就往 root 里的兄弟姐妹的list 插入.
如果这个 person 是 root的爸爸就往 person 里面的2叉树的 left child 节点里面插入
如果这个 person 是 root的妈妈就往 person 里面的2叉树的 right child 节点里面插入

这个是最简单的2叉树就含有自己父母的2叉树的数据结构. 同理如果爸爸的爸爸爸爸的妈妈再往爸爸的相应的2叉树里面插入就是了.
当然你的person 这个class 里面提供一个 getFarther 还有一个 getMonther的函数 , 以便把 person的爸爸妈妈的节点对象返回出去 , 让别人可以
往爸爸妈妈节点里面插入person的 obj .
不知道我说的是否清楚? ^_^
这个domain specific language 牛。不过那个sib从哪里蹦出来的？还有一句addAll已经慢死。 -changjin(被套住了); 2014-12-3 (#9132379@0)

this is Java: -sxffff(lookingforjob); 2014-12-3 {245} (#9132618@0)
p.father.children.addAll(p.mother.children).stream().filter(sib -> sib.getSex() == p.Sex.FEMALE && sib.getAge() > p.getAge() ) .map(p -> p.getName()) .forEach(name -> System.out.println(name));
坑爹啊，居然没有API convert List to Set，不写了

no API convert List to Set? Here it is: public HashSet(Collection<? extends E> c) -changjin(被套住了); 2014-12-4 (#9134282@0)

他的原意是说Java 8的List类型没有 .toSet这样的function，不然的话就可以一个劲的进行functional transformation. 并且保证强类型和元素唯一性。 -wxlin2k(wxlin2k); 2014-12-4 (#9134289@0)

看来lambda function 对很多Java人还是新鲜玩意。 -wxlin2k(wxlin2k); 2014-12-3 (#9134248@0)

基本上牛的公司都自己写编译器，有JVM就够了，并不需要Java的语法，C＃的语法就先进很多．JAVA８的语法实在令我失望． -sxffff(lookingforjob); 2014-12-3 (#9134262@0)

不能同意更多啊，不过起码算有进步了 -wxlin2k(wxlin2k); 2014-12-4 (#9134287@0)

友情提醒, 2叉树的root 不一定要认为是祖先, 记住我们是代码的上帝, 我们要它代表什么就代表什么. 这里的root 就是你需要列出来祖先的person. 其实跟你想象的普通的root的定义是不一样的! ^_^ -boolean(北漂一族); 2014-12-3 (#9132394@0)

你上点代码吧 -sxffff(lookingforjob); 2014-12-3 (#9132630@0)

说老实话, 上代码貌似不是senior developer的打法! ^_^ 代码思路放在那里了, 具体实现就木有必要了吧? -boolean(北漂一族); 2014-12-3 (#9132774@0)

考这个就是看代码，高级的就考别的了 -sxffff(lookingforjob); 2014-12-3 (#9132789@0)

恩是的. 你说的有道理. senior 的话就问问软件的design 啥的了! ^_^ -boolean(北漂一族); 2014-12-3 (#9132803@0)

其实上代码,可以google一下 2叉树的插入,查找以及遍历的代码. copy paste 然后改改就可以用了! ^_^ 自己从头写? 多麻烦哦! 嘿嘿 -boolean(北漂一族); 2014-12-3 (#9132808@0)

应该算很基本 coding... 注意边界条件需求分析 ---- 是否要求包含 step sisters，还有就是考虑出了 5 服可以通婚对算法的影响... lol... -xmlhttprequest(build5381); 2014-12-3 (#9132111@0)

估计就是个简单的面试题目, 出题者不会让她考虑那么复杂的算法. 个人理解就是个2叉树的遍历就搞定了. ^_^ -boolean(北漂一族); 2014-12-3 (#9132118@0)
step-sib 就分别加上父母的children list，再删除重复的即可。 ancestor乱伦也差不多，上一个queue，每次加ancestor的时候检查是否已有数据。 -calgarycat(POCO大猫); 2014-12-3 (#9133246@0)

恩是的. 但是我想出题目者 , 特别是面试的题目不会让做的那么perfect, 主要是看应聘者的解决问题的思路. 其他的都可以慢慢加入. ^_^ -boolean(北漂一族); 2014-12-3 (#9133275@0)

我的解见内。C＃的语法，在JAVA里可能不对。 -deep_blue(BLUE); 2014-12-3 {560} (#9132703@0)
public List<Person> OldSisters()
{
List<Person> list1 = mother.children.Where(c => c.sex == 'F' && c.age > age);
List<Person> list2 = father.children.Where(c => c.sex == 'F' && c.age > age);
return list1.Union(list2).Distinct();
}

public List<Person> AllAncestors()
{
List<Person> list = new List<Person>();
Add(mother, list);
Add(father, list);
return list;
}

private void Add(Person p, List<Person> list)
{
if (p == null) return;
list.Add(p);
Add(p.mother, list);
Add(p.father, list);
}

你2个数据结构就可以了啊! 一个兄弟姐妹的list 数据结构一个 2叉树的祖先的数据结构. 然后要list old sisters 那么就把那个xdjm list 找出来相应的person 打印出来就好了啊. 不用啥 monther father children 啥的关系啊.这样设计简单明了! -boolean(北漂一族); 2014-12-3 (#9132767@0)

已给的数据没有兄弟姐妹啊，只好绕道父母的孩子。 -deep_blue(BLUE); 2014-12-3 (#9133455@0)

我不是太相信出题目者能出这样的绕道儿的问题. 最好把原题目贴上来比较好! 如果出题目者真的这么出题的话, 我建议应聘者好好考虑此公司的机会了! ^_^ -boolean(北漂一族); 2014-12-3 (#9133465@0)

鉴于有人不理解这个代码的设计思路, 好吧我就详细的说一下! -boolean(北漂一族); 2014-12-3 {2049} (#9133888@0)
本文发表在 rolia.net 枫下论坛1. 我建立一个 Person 名字叫做"小明" 可以不?
2. 我访问数据库说小明的兄弟姐妹都有谁啊? 数据库返回给我几个人的属性是吧?
我根据相应的属性可以创建相应的人吧? 也就是 new 相应的person 可以吧?
3. 我把 2 创建相应人的指针 or Java 里面所说的reference 放到我的一个存着小明的兄弟姐妹 Person 指针的 list 里面可以不? 这个list 类似于 List<Person *> Sib_list.
这样我就创建好了小明兄弟姐妹的数据结构了吧?
4. 我访问数据库说小明的爸爸妈妈是谁啊? 好了数据库返回给我小明的爸爸妈妈了是吧? 同样的我那个小明 person 里面有个2叉树左儿子存的是爸爸的 Person 的指针
右儿子存的是小明妈妈的 Person 指针可以不? BTW 小明的爸爸的爸爸妈妈指针这个时候是NULL. 小名的妈妈的爸爸妈妈的指针这个时候也是 NULL.
然后我把小明的爸爸妈妈的指针也插到这个2叉树里面了吧?

5. 目前为止小明的这个对象的所有属性我都构造好了吧?

到了这一步:

那么我就一个Person 小明里面数据结构就有:
1. 一个 List<Person*> 里面含有的全是兄弟姐妹的指针!
2. 一个 2叉树 . root 就是小明
root 的左儿子指针指向的是小明爸爸 .
root 的右儿子指针只想的是小明的妈妈

如果你说小明的爸爸的爸爸妈妈都是谁那你就继续访问数据库生成个 2个相应的 Person* 指针然后把这 2个指针挂到相应的小明爸爸的左儿子那里还有右儿子指针上就好了啊.
其他的就都是同理可证了啊!

这个有啥难的呢? 为啥你说我建一个person 就要一个2叉树呢? 我不会存一个2叉树的指针吗? 就4个字节而已. 有啥浪费的呢?

如果需要说打印出来小明的兄弟姐妹来 , 那么我就iterator 我这个 List<Persion *> 然后打印出来相应的name 就可以了吧?
如果需要说打印出来小明的所有的祖先来 , 那我就iterator 我这个 2叉树可以不? 就中序啊还是前序啥的遍历一遍然后打印就好了.

我还可以提供打印出来小明全部男性的祖先的名字.
还可以打印出来小明全部女性祖先的名字.

我还可以打印出来跟小明差几个备份的祖先的名字.

你如果用一个 list 来把所有的人都塞进去, 您如何实现呢?

我跟 Java的程序员讨论代码真的是很捉急!! 还有啥问题 , 你可以继续发问! 我把回答你的问题也post 到发问的下面要不人家找不到了快!
其实如果明白人我说这2个数据结构就立马就清楚了. 没有必要我这么长篇大论的 ^_^更多精彩文章及讨论，请光临枫下论坛 rolia.net

我说了high level 3 steps, 你嫌多问为啥，我都懒得说。现在你啰里啰唆列了这么多，不知道真正看的人有几个。point is 你不需要build二叉树。上面这个c# code是对的，不过跟你讲的build二叉树可不同，要不你再看看？注意不要离题太远喔。 -changjin(被套住了); 2014-12-3 (#9133908@0)

那好吧，我说的罗嗦。你把你的代码的思路说一下，伪code实现都可以。看看你的是如何创建这个person的数据结构？然后根据人家的需要打印出来！ -boolean(北漂一族); 2014-12-3 {250} (#9133919@0)
就说你的那个把所有的人都塞到那个list 里面去，你给解释以下如何创建这个list 到如何打印出来Person的兄弟姐妹以及所有的祖先的。

我解释的从输入到输出我想我解释的已经非常清楚了。你说你的那个list 能work ，那你上上代码的思路或者伪代码也好。如何？

老大，人家上面c# code是对的。你再读读，然后跟你的思路比较一下不就得了。没你的那么麻烦还设计，这题没什么好设计的，属于抬手就写型的。 -changjin(被套住了); 2014-12-3 (#9133931@0)

你再读读上面的代码吧？ :-) 如果木有构造好 mother 还有 father 那么他的代码就是一层的结构？就父母还有兄弟。我在那个代码里面木有看到任何构造超过2层的祖先来！ -boolean(北漂一族); 2014-12-3 {415} (#9133954@0)
BTW，他的那个 C# 代码，我木有看到那里显示出来所有的祖先的函数，貌似都是往list 里面塞person 吧。而且数据结构内部大约是这个样子的。
A B C 。那么A 是root， B 是爸爸 C 是妈妈。
然后来个新的Person 节点就判断是不是NULL 不是NULL 就又add了那么如果来个 D or E 的节点那个 list.ADD（p）; 加到具体list的啥位置去了？说实话我木有太明白他的内部数据的分布。
然后打印出来所有的祖先代码呢？我没有看到在哪里具体实现啊？

人家的code,最好由人家去说。小声提个醒，那有个递归Add()，有多少代祖先，递归就有多少层, 你不可能不知道，逗大伙吧？ -changjin(被套住了); 2014-12-3 (#9133992@0)

您说的是这个吗？ -boolean(北漂一族); 2014-12-3 {231} (#9134010@0)
private void Add(Person p, List<Person> list)
{
if (p == null) return;
list.Add(p);
Add(p.mother, list);
Add(p.father, list);
}

如果是这个的话，您能给我解释一下：
我真心木有看到在哪里有显示祖先名字的代码？难道我看错了？
哦你说的对！我刚才打眼儿一看以为他代码有bug ^_^ 他那个list.Add()把我给蒙着了。我以为他写的不对无限递归了呢！ :-) -boolean(北漂一族); 2014-12-3 (#9134056@0)

学习了，学习了。上面还有一个Java 8的高手，这个论坛值得常来。 -changjin(被套住了); 2014-12-3 (#9134117@0)

还有如果用户说，罗列出来大小明2辈儿人的女的名单，咋办？再tricky一点的说罗列出来大小明2备份的男人名单来咋实现？ -boolean(北漂一族); 2014-12-3 (#9133957@0)

各位大佬, 如果还不明白的话, 那我就真的黔驴技穷了! 不能解释的再详细了! -boolean(北漂一族); 2014-12-3 (#9133895@0)

根本不需新的数据结构。直接写两个函数，结果放java.util.set对象里，就合并就简单了。 -wangqingshui(忘情水); 2014-12-3 (#9133929@0)

你牛！我来不了这个 :-) set 背后的数据结构是啥？不知道能否体现出来人的祖先关系？最好能上个伪代码顺嘴说太简单了 ^_^ -boolean(北漂一族); 2014-12-3 (#9133935@0)

好吧！貌似我跟Java 还有 C# 的developer 很难沟通！ ^_^ 我败了！服了！厉害！我讲不过你们了！ :-) -boolean(北漂一族); 2014-12-3 (#9133934@0)
扫了一眼上面的发言，貌似 .net 码工还靠点谱 lol.... -xmlhttprequest(build5381); 2014-12-3 (#9134275@0)

写的那么多的就没有一个是对的，妈的equal和hashcode不实现你们写个屁数据结构啊，懂Scala的给我进来挑错 -wxlin2k(wxlin2k); 2014-12-4 {467} (#9134339@0)
case class Person(name: String, age: Int, sex: Char, spouse: Option[Person], mother: Option[Person], father: Option[Person], children: List[Person]) {

private val parents = (father ++ mother).toList

def allOlderSisters: List[Person] = parents.flatMap(_.children).distinct.filter(_.sex.toUpper == 'F').filter(_.age > age)

def allAncestors: List[Person] = parents.flatMap(person => person :: person.allAncestors).distinct

}

／／这是可以跑的通的代码

写得好极，挑不出语法错, Scala牛。只是一点啊，第二个flatMap中，distinct去掉了重复的elements, 却没有去掉递归过程中重复的计算。上面的Java和C# code递归也有这个问题。不过作为面试题，到这一步应该有offer了。 -changjin(被套住了); 2014-12-4 (#9135050@0)

这种递归的过程中所谓的重复运算基本没有超越O(log(n))的范围，算法上没有改进，根本不算优化。option to List 已经减少的无谓的结点查找 -wxlin2k(wxlin2k); 2014-12-4 (#9135124@0)

Router 要是这样传递packets那得慢死，图论有算法可以彻底解决。非递归也可以去除重复。扯远了。不过为什么option to List帮助减少的无谓的结点查找? (father ++ mother).toList是在递归以外吧。 -changjin(被套住了); 2014-12-4 (#9135218@0)

真要在router上就不用JVM了好吧，要说浪费运算资源，GC才更严重吧。递归是stack，如果是TailRec就更省事，非递归在资源上不一定是更优化，heap lookup不一定更快。 -wxlin2k(wxlin2k); 2014-12-4 {437} (#9135408@0)
图论以空间换时间，是改进，但不在本题应用场景，具体问题要具体分析，没有一个算法可以通用所有情景。
option to List 就是因为在递归外边，使本身是空的结点直接就省了进去递归的步骤，连查空结点都不用做了，只生成有效结点的父母辈。
openbsd 是好 router，但是慢死，算法不是问题，而是内存安全校验步骤贼多。你要快，跑linux, 或者直接上FPGA，各人有各人需求。
你单算packet 搬运的话，freebsd是内核两级linked list, 已经很快了，该用递归的地方一样是递归。

Option为None，是递归里base case，为了让递归终止。其实那个function body还是进了一下的: ().flatMap(....).distinct. 返回空list, 然后上一层cons :: 这个空list, apply distinct, 再返回更上一层 ....., 这个可不能算减少的无谓的结点查找。 -changjin(被套住了); 2014-12-5 (#9136265@0)

我就呵呵了 -wxlin2k(wxlin2k); 2014-12-5 (#9136350@0)

你再贴一个tail recursive的版本吧让大家学习学习，以前那个还是比较容易stackoverflow. -changjin(被套住了); 2014-12-5 (#9136476@0)

不是tailrec的问题，（None++None）.toList = Nil, Nil的任何monad function返回都是自己，不进入function body。空结点根本就没产生递归，理解了吗？ -wxlin2k(wxlin2k); 2014-12-5 (#9136556@0)

我说的都是实际trace到的，理解了吗？建议你贴Tail Recursion，跟这个base case没啥关系,是相对于你最上面那个code. FP是个好东西，不过看看底层实现，万法归宗呀。没有什么特别自豪的。 -changjin(养怡之福，可得永年); 2014-12-5 (#9136682@0)

实际trace啥呢？我笨。FP只是关于另外一个软件抽象的方向，当然没有什么好自豪，只是提供了另一种选择和思路，甚至我不认为它运行更高效，因为如何优化是要看具体应用数据和编译器的事。 -wxlin2k(wxlin2k); 2014-12-5 {836} (#9136894@0)
你拿所有不同的语言实现和一万个random例子做基础数据，拿个平均数我们才能看到哪个更快啊。

但是把所有不同类型解决方案都用一句万法归宗，底层实现都一样的话做总结，我们现在是不是应该直接写01呢？
Java 我也可以先查空不递归啊。跟FP一点关系都没有。当然，你做线性游历跑loop一层一层进去去看当然可以，但在算法和速度上是一样的，好处当然是不overflow stack，因为程序猿要自己实现栈的功能。
写递归，JVM上我来个小栈size当然就一下搞死了，对吧？但同理，我可以根据需求调高这个size的大小。没有具体应用场景讨论这个跟说共产主义什么时候实现道理一样好吧？
但一看到结点结构就为什么一定来个二叉树游历？看到了结点就一定要进去递归？这是因为这个写法更简单。不是性能的问题。我就一直不明白你纠结在哪个部分的重复计算呢？我真醉了，求解释。

没有一个完美的工具可以解决所有的问题，所以我们希望有不同的工具处理不同的问题。如果你用惯了的锤子，就认为锤子能解决一切问题？

万法归宗=都一样=010101? 你说的好像有点道理哟,不过我真的必须要口吃一下了.一个工具可以解决所有问题？说明我communication有问题.至于重复计算,那是秃子头上的虱子,何须纠结.难道你希望你那两行Scala摆在那没人理？你还是继续上code吧,我有空再给你comment. -changjin(养怡之福，可得永年); 2014-12-5 (#9137069@0)

开始有考虑删帖了，就咱两在逗乐：）群众不热情啊T_T -wxlin2k(wxlin2k); 2014-12-5 (#9137363@0)

你们单开一贴可能会热闹点。这么个问题，没想到里面有这么多讨论。呵呵。 -geekcode(文心雕码); 2014-12-5 (#9137885@0)

真心对Scala 这个FP 语言不感冒！1. 学习曲线高 2. 因为1 使得team的开发人员很难保证水平同步 3. 比较反人类的语法貌似 :-) -boolean(北漂一族); 2014-12-6 (#9137993@0)

但是那四行代码就已经让编译器帮你生产成了，constructor, getter, hashcode, equal, 空校验，而且还是immutable 和 thread safe, 省事啊。你只需要关心业务逻辑就够了， -wxlin2k(wxlin2k); 2014-12-6 (#9138627@0)

对了，忘了说了，scala的list是二叉树，不是linked list 或double linkedlist，算是回一下 -boolean(北漂一族); 12-3 14:44 的那个贴，所以很多东西不是万变不离其宗 -wxlin2k(wxlin2k); 2014-12-5 (#9136958@0)

这个差别比基督教和佛教之间的差别小。宗还是在那。 -changjin(养怡之福，可得永年); 2014-12-5 (#9137221@0)

基督教和佛教之间?区别老大了，和尚不能破葷戒，神父可以酒肉啊。信佛可以在家做居士，基督要受洗啊。啥都这个区别小好吧。说这个list的例子是说scala的list 单向prepend 好，查找跟倒置都不好。但有他应用的原因，这个应用的前提才是宗。 -wxlin2k(wxlin2k); 2014-12-5 (#9137345@0)

好像是LinkedList 吧？ http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List Scala 语法与Java差别远远大于JAVA和.Net，有点难，所以普及也难，不看好。 -sxffff(lookingforjob); 2014-12-5 (#9137431@0)

这个我确实记错了，的确是单向链表，感谢提醒，我把它在多线程下的父结点记错成子结点了，该骂！因为它用起来的时候，更像树，要递归，还要在前面加结点，呵呵。一般单向链表操作都是线性，而且在后边加。糊涂了我。 -wxlin2k(wxlin2k); 2014-12-5 (#9137622@0)

呵呵差点被你忽悠了！^_^ 所以说嘛还是万变不离其中啊。还能跑出去了基本的数据结构？ -boolean(北漂一族); 2014-12-6 (#9137992@0)

Here you go: -sailor(Ocean & Mountain); 2014-12-4 {823} (#9134297@0)

public class Person {
	String name;
	int age;
	char sex;
	Person spouse;
	Person mother;
	Person father;
	List children;

	List findAncestors() {
		List ancestors = new ArrayList();
		if (mother != null) {
			ancestors.add(mother);
			ancestors.addAll(mother.findAncestors());
		}
		if (father != null) {
			ancestors.add(father);
			ancestors.addAll(father.findAncestors());
		}
		return ancestors;
	}

	List findOlderSisters() {
		List olderSisters = new ArrayList();
		Set kids = new HashSet();
		kids.addAll(mother.children);
		kids.addAll(father.children);
		for (Person kid : kids) {
			if (kid.sex == 'F' && kid.age > this.age) {
				olderSisters.add(kid);
			}
		}
		return olderSisters;
	}
}

Congrats Sailor ;-)) You're hired! -mingyangli(Life is a journey); 2014-12-4 (#9134786@0)

LOL. Thanks! -sailor(Ocean & Mountain); 2014-12-5 (#9136509@0)

如果父母是表亲结婚，或者祖上有表亲结婚，祖先结果会有重复。可能结果用HashSet就可以避免了 -wangqingshui(忘情水); 2014-12-4 (#9134883@0)

That's correct! Thanks! -sailor(Ocean & Mountain); 2014-12-5 (#9136505@0)

第一题直接一个循环parent->children=female >node.age()不就解决了么？ -zhengy4(zhengy4); 2015-1-29 {296} (#9225871@0)
第二题遍历二叉树即可。

find(node){
if(parent->father() exist)
find (parent->father());
if(mother exist);
find (parent->mother());

print node->name;
return;
}

复杂度为O(average(做多existing parents那一代） log _2 (average(做多existing parents那一代）））

这个是什么语言？ -sxffff(lookingforjob); 2015-2-2 (#9231111@0)

psuedo-code -zhengy4(zhengy4); 2015-2-4 (#9236487@0)

都是能人。难怪科技发展这么快。外行问一句，如果是同性恋家庭，变性父母，收养家庭，抱养家庭，拐卖的小孩，一夫多妻制家庭，不知父亲是谁家庭，上面的答案是不是要改写？唉，现代社会真是给人出难题。 -buug(Crouching Tiger); 2015-1-29 (#9225902@0)

同性恋家庭，多夫多妻和离婚的根本不会算到parents里，这里parents应该是有血缘关系的，关键是乱伦会有duplication，好吧这个帖子口味开始变重了。。。。 -zhengy4(zhengy4); 2015-2-1 {467} (#9230594@0)
乱伦用我上面的遍历2叉树一样能找到ancestor,只是会有duplication,我想了想，这样在return node.name()的时候做个， check.duplicate(node.name()) 只要往上找三代基本就可以了， if =true,说明家里有乱伦，这样就直接 break，不return.node.name())中断递归即可。
这样母子，父女，曾祖父曾孙女的xx情况都可以保证没有duplication了，曾祖母应该不用考虑了，理论上这个年龄不会有ancestor了。。。生不出来。。。。
好吧这个回帖口味越来越重了，只能>18岁儿童观看，viewers discretion is advised.

LOL! -arfeifei(老顽童★[O|||||||O]); 2015-2-1 (#9230649@0)

哈哈 -zhengy4(zhengy4); 2015-2-4 (#9236486@0)

@Florida

我说的O(n) 是用2叉树列出来所有的给定的一个person的所有的祖先.

Replies, comments and Discussions:

More Topics