i******s
发帖数: 301 | 1 一面
一图，找出所有connected component
e.g. A->B->C-> D
|
--> E
F -> G
输出就是 [(A, B, C, D, E), (F, G)]
二面
lowest common ancestor
中间有很多聊天。第一题很简单，找出没有dependency的node, 然后dfs; 第二题是烂
题了，用了hashtable的做法，最简单。不过做之前讨论了多种做法之间的优劣。
本来题目应该是onsite的，可惜onsite都是聊天，没什么有价值的新题。对了，组是数
据分析组
FYI, twitter食堂真心赞，感觉应该秒杀99.99%的码工公司 |
P*******b
发帖数: 1001 | 2 真不知道hashtable怎么做这道题，指点一下？
【在 i******s 的大作中提到】
: 一面
: 一图，找出所有connected component
: e.g. A->B->C-> D
: |
: --> E
: F -> G
: 输出就是 [(A, B, C, D, E), (F, G)]
: 二面
: lowest common ancestor
: 中间有很多聊天。第一题很简单，找出没有dependency的node, 然后dfs; 第二题是烂
|
i******s
发帖数: 301 | 3 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
recursion的做法有点绕。
【在 P*******b 的大作中提到】
: 真不知道hashtable怎么做这道题，指点一下？
|
P*******b
发帖数: 1001 | 4 明白了，从来没有这么想过这个题.
不过我觉得代码量其实比recursion的多很多阿
thanks
【在 i******s 的大作中提到】
: 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
: 对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
: 。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
: recursion的做法有点绕。
|
p*****p
发帖数: 379 | 5 能贴下code么？我怎么感觉还是recursion好解……
TreeNode *findLCA(TreeNode *root, TreeNode *n1, TreeNode *n2) {
if (!root) return NULL;
if (root == n1 || root == n2) return root;
TreeNode *left = findLCA(root->left, n1, n2);
TreeNode *right = findLCA(root->right, n1, n2);
if (left && right) return root;
else if (!left && !right) return NULL;
return left ? left : right;
}
【在 i******s 的大作中提到】
: 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
: 对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
: 。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
: recursion的做法有点绕。
|
p*****p
发帖数: 379 | 6 我知道你啥意思了……你的是有parent指针的吧
【在 i******s 的大作中提到】
: 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
: 对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
: 。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
: recursion的做法有点绕。
|
P*******b
发帖数: 1001 | 7 不用parent指针，我觉得他的意思是先做一个level order吧。
【在 p*****p 的大作中提到】
: 我知道你啥意思了……你的是有parent指针的吧
|
p*****p
发帖数: 379 | 8 那样的话，在hashmap里怎么跟踪parent呢？我就是这个不知道怎么弄的
【在 P*******b 的大作中提到】
: 不用parent指针，我觉得他的意思是先做一个level order吧。
|
i******s
发帖数: 301 | 9 好吧，那是因为你练过吧。否则最后那个if else确定返回值的时候不容易想对吧，而
且解释正确性也要花点时间。hashtable代码是略长，不过简单直接啊，而且多次查询
有优势。我是问了interviewer他想要那种，他说那你用hashtable吧
【在 p*****p 的大作中提到】
: 能贴下code么？我怎么感觉还是recursion好解……
: TreeNode *findLCA(TreeNode *root, TreeNode *n1, TreeNode *n2) {
: if (!root) return NULL;
: if (root == n1 || root == n2) return root;
: TreeNode *left = findLCA(root->left, n1, n2);
: TreeNode *right = findLCA(root->right, n1, n2);
: if (left && right) return root;
: else if (!left && !right) return NULL;
: return left ? left : right;
: }
|
t*********h
发帖数: 941 | 10 connected component的输入什么格式阿
【在 i******s 的大作中提到】
: 一面
: 一图，找出所有connected component
: e.g. A->B->C-> D
: |
: --> E
: F -> G
: 输出就是 [(A, B, C, D, E), (F, G)]
: 二面
: lowest common ancestor
: 中间有很多聊天。第一题很简单，找出没有dependency的node, 然后dfs; 第二题是烂
|
|
|
w****x
发帖数: 2483 | 11
同问图的表示方式
【在 t*********h 的大作中提到】
: connected component的输入什么格式阿
|
r*****e
发帖数: 146 | 12 标答啊，如果面试官是老中的话，这种答案是否算个暗号？ 大家都是做过看过leet
code滴。。。
【在 p*****p 的大作中提到】
: 能贴下code么？我怎么感觉还是recursion好解……
: TreeNode *findLCA(TreeNode *root, TreeNode *n1, TreeNode *n2) {
: if (!root) return NULL;
: if (root == n1 || root == n2) return root;
: TreeNode *left = findLCA(root->left, n1, n2);
: TreeNode *right = findLCA(root->right, n1, n2);
: if (left && right) return root;
: else if (!left && !right) return NULL;
: return left ? left : right;
: }
|
c********t
发帖数: 5706 | 13 hashtable key是node, value是parent和level ?
【在 i******s 的大作中提到】
: 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
: 对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
: 。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
: recursion的做法有点绕。
|
w****a
发帖数: 710 | |
d**********x
发帖数: 4083 | 15 第一题要是全都是圈，怎么找没有dependency的node。。。
直接dfs，并查集即可
【在 i******s 的大作中提到】
: 一面
: 一图，找出所有connected component
: e.g. A->B->C-> D
: |
: --> E
: F -> G
: 输出就是 [(A, B, C, D, E), (F, G)]
: 二面
: lowest common ancestor
: 中间有很多聊天。第一题很简单，找出没有dependency的node, 然后dfs; 第二题是烂
|
i******s
发帖数: 301 | 16 我就是这么做的
【在 c********t 的大作中提到】
: hashtable key是node, value是parent和level ?
|
i******s
发帖数: 301 | 17 那就直接返回所有node。并查集不是要额外O(n)空间么，再说也没必要啊这里
【在 d**********x 的大作中提到】
: 第一题要是全都是圈，怎么找没有dependency的node。。。
: 直接dfs，并查集即可
|
d**********x
发帖数: 4083 | 18 hashtable 也需要额外 O(n)空间吧？我没仔细看那个实现。。
【在 i******s 的大作中提到】
: 那就直接返回所有node。并查集不是要额外O(n)空间么，再说也没必要啊这里
|
i******s
发帖数: 301 | 19 我错了，我以为你在说第一题。不过第二题的话，如果用并查集，只能对特定的两个
node求ancestor吧，那样O(n)空间还不如直接用递归。我没想出来弄出一个并查集后，
怎么对任意两个node都能快速求出ancestor。hashtable是费O(n)空间，唯一好处就是
对任意两个node，最坏log(n)就能出结果，当然假设tree is balanced
【在 d**********x 的大作中提到】
: hashtable 也需要额外 O(n)空间吧？我没仔细看那个实现。。
|
d**********x
发帖数: 4083 | 20 我错了。。。
我以为他说的是第二题。。。
是这样的，有向图中dfs求单连通子集（虽然不太严谨）的一个问题是每次接触到一个
新的集合的时候，要回溯并update当前的子集，比如：
8->9-|
-> 1->2->3->4->5->6->7
c->d-|
这样，假如开始的时候是从8开始的，一路搜到7，全部标记为A
然后从c开始搜索，搜到3之后还要回溯到c去标记，这样可能会略慢
但是无所谓了，反正复杂度都一样。。
【在 i******s 的大作中提到】
: 我错了，我以为你在说第一题。不过第二题的话，如果用并查集，只能对特定的两个
: node求ancestor吧，那样O(n)空间还不如直接用递归。我没想出来弄出一个并查集后，
: 怎么对任意两个node都能快速求出ancestor。hashtable是费O(n)空间，唯一好处就是
: 对任意两个node，最坏log(n)就能出结果，当然假设tree is balanced
|
|
|
c*********e
发帖数: 644 | 21 What is T??????
【在 i******s 的大作中提到】
: 一面
: 一图，找出所有connected component
: e.g. A->B->C-> D
: |
: --> E
: F -> G
: 输出就是 [(A, B, C, D, E), (F, G)]
: 二面
: lowest common ancestor
: 中间有很多聊天。第一题很简单，找出没有dependency的node, 然后dfs; 第二题是烂
|
e***s
发帖数: 799 | |
x*****0
发帖数: 452 | |
