E*****D
发帖数: 3 | 1 刚收到信说还要一轮电面。是不是因为第一轮表现不够好所以还要在电面一下？
附第一轮面经（班上有人面过的题目）：
给一个大文件每一行是：
parentId:childId
parentId 和 childId 都是string.
1. 定义自己的数据结构，写一个函数预处理数据。
2. 写一个函数能够快速判断两个给定的id有没有关系，即有没有共同祖先。 |
f*******t
发帖数: 7549 | 2 这题我不会做，貌似有个常见版本是读入这些pair然后建立一棵树，谁有好的解法？ |
r******3
发帖数: 221 | 3 建图。
没明白1）的意思，如果求weight，那么就是标准的DFS/BFS。
2）。从两头做traversal，然后看有没有重复的node. |
r******3
发帖数: 221 | 4 另外回答楼主的问题，既然你的recuiter告诉你要二面就好好准备吧，不要去想一面了
，二面能拿下也能拿到on-site。 |
j******2
发帖数: 362 | 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****A
发帖数: 4160 | 6 信息不全，可能的情况很多啊
【在 E*****D 的大作中提到】
: 刚收到信说还要一轮电面。是不是因为第一轮表现不够好所以还要在电面一下？
: 附第一轮面经（班上有人面过的题目）：
: 给一个大文件每一行是：
: parentId:childId
: parentId 和 childId 都是string.
: 1. 定义自己的数据结构，写一个函数预处理数据。
: 2. 写一个函数能够快速判断两个给定的id有没有关系，即有没有共同祖先。
|
p*****2
发帖数: 21240 | 7 hashmap＋tree with parent pointer
findAncestor logn
any better solution? |
f*********m
发帖数: 726 | 8 hashtable of ParentID)
找intersection of 两个vector of ParentID，就得到共同祖先？ |
j******2
发帖数: 362 | |
E*****D
发帖数: 3 | 10 对的，每个child有两个parents. 也存在有一个parent的可能: 另外一个parent为null.
【在 j******2 的大作中提到】
: 一个child可能有两个parent吗？
|
|
|
j******2
发帖数: 362 | 11 这个跟平时做那个LCA不大一样啊，有两个parent所以无法从根结点开始。
【在 p*****2 的大作中提到】
: hashmap＋tree with parent pointer
: findAncestor logn
: any better solution?
|
E*****D
发帖数: 3 | 12 可以看作是一个upside down的二叉树。从当前节点往上遍历所有parents,存到hashmap
. 然后遍历另外一节点的parents, 查看是否已在hashmap中。
【在 j******2 的大作中提到】
: 这个跟平时做那个LCA不大一样啊，有两个parent所以无法从根结点开始。
|
p*****2
发帖数: 21240 | 13 这样就不是树了是有向图 shortest path可结吧 n3
【在 j******2 的大作中提到】
: 这个跟平时做那个LCA不大一样啊，有两个parent所以无法从根结点开始。
|
j******2
发帖数: 362 | 14 bfs，用个queue把父母孩子们都放进去，再用个set记录visited，是这样的干活？ |
c********t
发帖数: 5706 | 15 虽然是个图结构，但解这道题感觉就是这么简单
【在 f*********m 的大作中提到】
: hashtable of ParentID)
: 找intersection of 两个vector of ParentID，就得到共同祖先？
|
l**b
发帖数: 457 | |
c***s
发帖数: 192 | 17 这种方法很慢吧。
如果数据很大，比如几百年的人类数据库，那个hashmap会很大。
hashmap
【在 E*****D 的大作中提到】
: 可以看作是一个upside down的二叉树。从当前节点往上遍历所有parents,存到hashmap
: . 然后遍历另外一节点的parents, 查看是否已在hashmap中。
|
Y**Y
发帖数: 66 | 18 那这就是个DAG了
从两个节点同时做BFS，看有没有overlap. 最坏的是两个没关系的。
要快一些的话， 预处理，每个节点存他最早的祖先们 （sorted), 也就是DAG的
starting nodes, zero in-degree。 对所给的两个nodes, 取两个sorted lists的交集
。
null.
【在 E*****D 的大作中提到】
: 对的，每个child有两个parents. 也存在有一个parent的可能: 另外一个parent为null.
|
r*****e
发帖数: 146 | 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?
|
h*****7
发帖数: 60 | 20 原来二面是一面不理想吗 我囧了
【在 r******3 的大作中提到】
: 另外回答楼主的问题，既然你的recuiter告诉你要二面就好好准备吧，不要去想一面了
: ，二面能拿下也能拿到on-site。
|
