问一道Apple电话面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道Apple电话面试题

问一道Apple电话面试题# JobHunting - 待字闺中

k*t2016-02-11 08:02

1 楼

fail了没做出来
题目是给两个人怎么判断他们是genetically related 例如爸爸和儿子是但是爸爸
和妈妈不是
要求给出person class的设计和算法

l*n2016-02-11 08:02

2 楼

画个graph 找shortest path就行了 finite就是related

【在 k**t 的大作中提到】

: fail了没做出来
: 题目是给两个人怎么判断他们是genetically related 例如爸爸和儿子是但是爸爸
: 和妈妈不是
: 要求给出person class的设计和算法

y*x2016-02-11 08:02

3 楼

公共祖先有基因关系的一定有公共祖先
不管是爹跟儿还是兄弟两
[在 knut (Cute Knut) 的大作中提到：]
：fail了没做出来
：题目是给两个人怎么判断他们是genetically related 例如爸爸和儿子是但是爸
爸和妈妈不是
：...........

C*n2016-02-11 08:02

4 楼

union find 并查集
class Person {
Person * father;
Person(Person * f):father(f){}
};
做你这个题还要定义什么person class，直接一个vector fathers就完了，每一
个int代表一个人, fathers存所有人的father。就这一个fathers就能完成union find
的所有操作了。

【在 k**t 的大作中提到】

: fail了没做出来
: 题目是给两个人怎么判断他们是genetically related 例如爸爸和儿子是但是爸爸
: 和妈妈不是
: 要求给出person class的设计和算法