logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
前总统小布什
avatar
前总统小布什# Joke - 肚皮舞运动
i*s
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%的码工公司
avatar
x*3
2 楼
投票的时候被搞糊涂了
于是投了奥巴马
avatar
P*b
3 楼
真不知道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; 第二题是烂
avatar
r*e
4 楼
难怪共和党fail了

【在 x*******3 的大作中提到】
: 投票的时候被搞糊涂了
: 于是投了奥巴马
avatar
i*s
5 楼
你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
recursion的做法有点绕。

【在 P*******b 的大作中提到】
: 真不知道hashtable怎么做这道题，指点一下？
avatar
c*h
6 楼
其实内讧了
小步：哼，魔门的

【在 r*********e 的大作中提到】
: 难怪共和党fail了
avatar
P*b
7 楼
明白了，从来没有这么想过这个题.
不过我觉得代码量其实比recursion的多很多阿
thanks

【在 i******s 的大作中提到】
: 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
: 对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
: 。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
: recursion的做法有点绕。
avatar
s*l
8 楼
前总统的是不是不想去投票也得做做样子去投？
avatar
p*p
9 楼
能贴下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的做法有点绕。
avatar
wy
10 楼
他算德州的吧。德州不差他一票

【在 r*********e 的大作中提到】
: 难怪共和党fail了
avatar
p*p
11 楼
我知道你啥意思了……你的是有parent指针的吧

【在 i******s 的大作中提到】
: 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
: 对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
: 。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
: recursion的做法有点绕。
avatar
M*n
12 楼
蝴蝶效应

【在 wy 的大作中提到】
: 他算德州的吧。德州不差他一票
avatar
P*b
13 楼
不用parent指针，我觉得他的意思是先做一个level order吧。

【在 p*****p 的大作中提到】
: 我知道你啥意思了……你的是有parent指针的吧
avatar
p*p
14 楼
那样的话，在hashmap里怎么跟踪parent呢？我就是这个不知道怎么弄的

【在 P*******b 的大作中提到】
: 不用parent指针，我觉得他的意思是先做一个level order吧。
avatar
i*s
15 楼
好吧，那是因为你练过吧。否则最后那个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;
: }
avatar
t*h
16 楼
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; 第二题是烂
avatar
w*x
17 楼

同问图的表示方式

【在 t*********h 的大作中提到】
: connected component的输入什么格式阿
avatar
r*e
18 楼
标答啊，如果面试官是老中的话，这种答案是否算个暗号？ 大家都是做过看过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;
: }
avatar
c*t
19 楼
hashtable key是node, value是parent和level ?

【在 i******s 的大作中提到】
: 你用hashtable扫一边tree, 记录下每个node的parent和所在的level。然后就简单啦，
: 对于给定的两个node, 让他们到同一层，然后一同往上走，所有信息都在hashtable里
: 。虽然占space，但好处是多次查询可以很快，而且code很简单，思路也直接。
: recursion的做法有点绕。
avatar
w*a
20 楼
bless！
楼主拿到offer了？
avatar
d*x
21 楼
第一题要是全都是圈，怎么找没有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; 第二题是烂
avatar
i*s
22 楼
我就是这么做的

【在 c********t 的大作中提到】
: hashtable key是node, value是parent和level ?
avatar
i*s
23 楼
那就直接返回所有node。并查集不是要额外O(n)空间么，再说也没必要啊这里

【在 d**********x 的大作中提到】
: 第一题要是全都是圈，怎么找没有dependency的node。。。
: 直接dfs，并查集即可
avatar
d*x
24 楼
hashtable 也需要额外 O(n)空间吧？我没仔细看那个实现。。

【在 i******s 的大作中提到】
: 那就直接返回所有node。并查集不是要额外O(n)空间么，再说也没必要啊这里
avatar
i*s
25 楼
我错了，我以为你在说第一题。不过第二题的话，如果用并查集，只能对特定的两个
node求ancestor吧，那样O(n)空间还不如直接用递归。我没想出来弄出一个并查集后，
怎么对任意两个node都能快速求出ancestor。hashtable是费O(n)空间，唯一好处就是
对任意两个node，最坏log(n)就能出结果，当然假设tree is balanced

【在 d**********x 的大作中提到】
: hashtable 也需要额外 O(n)空间吧？我没仔细看那个实现。。
avatar
d*x
26 楼
我错了。。。
我以为他说的是第二题。。。
是这样的，有向图中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
avatar
c*e
27 楼
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; 第二题是烂
avatar
e*s
28 楼
楼主，第二题能不能贴个CODE 看看？
avatar
x*0
29 楼
mark
相关阅读
女士手包考刚看来的笑话Re: 唉...为什么导师一般都不回我email的? (转载)甲午大戏剧预告 一个年迈的老佛爷 一个修补的中堂 一个没落的帝国 一支衰退的海军 一群如狼似虎的列强 一帮整天分裂的叛党 九一八正式公映：苏格兰独立公投去超市买头猪去中华书局唐诗排行榜 (转载)不锈钢链表带吐槽说说跟几个老板的事 (转载)战斗民族宁静的夜晚生活中的天雷滚滚 （zz)告诉你 我今天家里没人喔刚宣布：明年起小学一年级古诗词由6篇增加到22篇 (转载)女子疑丈夫在外乱搞男女关系 半年7次艾滋检查哈市有AUSTIN附近的，求帮个忙，＄１００ GIFT CARD 感谢！ (转载)自行菊擦，我老正在考虑升级到ip5Re: 为啥整个儒家文化圈，就中国人有比较重的处女情结？ (转载)女子与网友果园偷情 (转载)浙江大学研究出了隐身衣 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。