大家G电面都是几轮？（附题目） - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

大家G电面都是几轮？（附题目）

大家G电面都是几轮？（附题目）# JobHunting - 待字闺中

E*D2013-02-21 08:02

1 楼

刚收到信说还要一轮电面。是不是因为第一轮表现不够好所以还要在电面一下？
附第一轮面经（班上有人面过的题目）：
给一个大文件每一行是：
parentId:childId
parentId 和 childId 都是string.
1. 定义自己的数据结构，写一个函数预处理数据。
2. 写一个函数能够快速判断两个给定的id有没有关系，即有没有共同祖先。

f*t2013-02-21 08:02

2 楼

这题我不会做，貌似有个常见版本是读入这些pair然后建立一棵树，谁有好的解法？

r*32013-02-21 08:02

3 楼

建图。
没明白1）的意思，如果求weight，那么就是标准的DFS/BFS。
2）。从两头做traversal，然后看有没有重复的node.

r*32013-02-21 08:02

4 楼

另外回答楼主的问题，既然你的recuiter告诉你要二面就好好准备吧，不要去想一面了
，二面能拿下也能拿到on-site。

j*22013-02-21 08:02

5 楼

这样想会不会很naive
hash_map family_index
vector > family_members
每读一行，如果family_index里有parent没child或者有child没parent，新的那个就随
旧的那个加入family。如果两个都没有就新建一个family set。如果两个都有但是不一
样，就让child随parent，并把child的set和parent的set合并，并修改所有child成员
的family_index.
要查的时候就看family_index里两个id的值是不是一样。

【在 E*****D 的大作中提到】

: 刚收到信说还要一轮电面。是不是因为第一轮表现不够好所以还要在电面一下？
: 附第一轮面经（班上有人面过的题目）：
: 给一个大文件每一行是：
: parentId:childId
: parentId 和 childId 都是string.
: 1. 定义自己的数据结构，写一个函数预处理数据。
: 2. 写一个函数能够快速判断两个给定的id有没有关系，即有没有共同祖先。

G*A2013-02-21 08:02

6 楼

信息不全，可能的情况很多啊

【在 E*****D 的大作中提到】

p*22013-02-21 08:02

7 楼

hashmap＋tree with parent pointer
findAncestor logn
any better solution?

f*m2013-02-21 08:02

8 楼

hashtable of ParentID)
找intersection of 两个vector of ParentID，就得到共同祖先？

j*22013-02-21 08:02

9 楼

一个child可能有两个parent吗？

E*D2013-02-21 08:02

10 楼

对的，每个child有两个parents. 也存在有一个parent的可能: 另外一个parent为null.

【在 j******2 的大作中提到】

: 一个child可能有两个parent吗？

j*22013-02-21 08:02

11 楼

这个跟平时做那个LCA不大一样啊，有两个parent所以无法从根结点开始。

【在 p*****2 的大作中提到】

: hashmap＋tree with parent pointer
: findAncestor logn
: any better solution?

E*D2013-02-21 08:02

12 楼

可以看作是一个upside down的二叉树。从当前节点往上遍历所有parents,存到hashmap
. 然后遍历另外一节点的parents, 查看是否已在hashmap中。

【在 j******2 的大作中提到】

: 这个跟平时做那个LCA不大一样啊，有两个parent所以无法从根结点开始。

p*22013-02-21 08:02

13 楼

这样就不是树了是有向图 shortest path可结吧 n3

【在 j******2 的大作中提到】

: 这个跟平时做那个LCA不大一样啊，有两个parent所以无法从根结点开始。

j*22013-02-21 08:02

14 楼

bfs，用个queue把父母孩子们都放进去，再用个set记录visited，是这样的干活？

c*t2013-02-21 08:02

15 楼

虽然是个图结构，但解这道题感觉就是这么简单

【在 f*********m 的大作中提到】

: hashtable of ParentID)
: 找intersection of 两个vector of ParentID，就得到共同祖先？

l*b2013-02-21 08:02

16 楼

这个题目不是union find？

c*s2013-02-21 08:02

17 楼

这种方法很慢吧。
如果数据很大，比如几百年的人类数据库，那个hashmap会很大。

hashmap

【在 E*****D 的大作中提到】

: 可以看作是一个upside down的二叉树。从当前节点往上遍历所有parents,存到hashmap
: . 然后遍历另外一节点的parents, 查看是否已在hashmap中。

Y*Y2013-02-21 08:02

18 楼

那这就是个DAG了
从两个节点同时做BFS，看有没有overlap. 最坏的是两个没关系的。
要快一些的话，预处理，每个节点存他最早的祖先们（sorted), 也就是DAG的
starting nodes, zero in-degree。对所给的两个nodes, 取两个sorted lists的交集
。

null.

【在 E*****D 的大作中提到】

: 对的，每个child有两个parents. 也存在有一个parent的可能: 另外一个parent为null.

r*e2013-02-21 08:02

19 楼

agree,if the people in the past thousand of years are too many, we can
simplify it by recording the visited ancestor.
// for the root id, dict[root_id] == "#";
// dict is something like map
bool share_ancestor(map dict, string c1, string c2){
set found;
while(true){
if(check(c1,dict, found))
return true;
if(check(c2,dict, found))
return true;
if(c1 == "#" && c2 == "#")
return false;
}
}
bool check(string& child_id, map dict, set& found){
string parent_id = dict[child_id];
if(found.find(parent_id) == found.end()){
found.insert(parent_id);
child_id = parent_id;
return false;
}else{
return true;
}
}

【在 p*****2 的大作中提到】

: hashmap＋tree with parent pointer
: findAncestor logn
: any better solution?