W***u
发帖数: 81 | 1 PS1
一个华裔，一个烙印mm，面试过程很nice
Pow(x,n)
Insert Intervals
Leetcode 原题
PS2
一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
1. string matching的题，具体忘了，很简单；
2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
common ancestor. 就栽在这道题上，感觉
被黑了。
A
/ \
B C
/ \
D E
/ \
G F
commonAncestor(D, F) = B
commonAncestor(C, G) = A
题目出来马上问烙印面试官是不是，如果是 输入是 B F 输出是不是B。 回答：
不是，应该是 Ｂ的parent A。 额 给雷到了。 然后马上说思路，用一个hashset，
保持一个node从自身到root的路径，然后第二节点往上traverse，遇到在hashset中的
节点，就找到了最深的parent。 复杂度 O(n), n 是深度。 面试官马上制止我这个思
路说，如果树很大，traverse到root的话，很费时间。要我想其他的方法。
然后就说到了一个 往上traverse的方法， 思路就是 例如 D F 的最深公共parent
，就是D 和F的parent E 的公共parent。后面的问题就变成了哪一个该往上 traverse
， commonAncestor(one, two.parent) 还是 commonAncestor(one.parent, two)。烙
印面试官也说，close close 了。 感觉是这个方向没错。 然后我提到了这个需要知道
one two 的深度，然后深的一个往上走。 面试官没发言。 但是这样子的话，算法时间
复杂度就跟之前提出的方法一样了。 所以接下来没这样想，然后时间到了。。
跟后面那个烙印gg交流很困难。。 最后给recruiter的feedback也是这个是
negative的。面试完后回来想想，感觉那样的话，必须要知道树的深度。 感慨自己哪
一种方法都没有坚持到底给出一个完整的solution。
求版上各位大神帮忙分析下这个题到底该如何做，然后是不是被黑了。
谢谢！ |
s**********e
发帖数: 29 | 2 你的第一种解法是比较浪费空间，不知是不是交流有点偏差听错了？这题肯定要计算深
度的 |
o********t
发帖数: 1655 | 3 你和前面那位交流一下看看是不是被同一个烙印黑了。觉得被黑了就要投诉，利人利己
【在 W***u 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
|
l*********8
发帖数: 4642 | 4 两个节点同时往root走， 经过的节点放hashmap里， 出现重复的时候， 就找到共同祖
先了。 |
g*********e
发帖数: 14401 | 5 linkedin的店面问什么都是两个人一起面，一个是shadow吗？ |
W***u
发帖数: 81 | 6 赞！！ 咋就没想到呢。。
【在 l*********8 的大作中提到】
: 两个节点同时往root走， 经过的节点放hashmap里， 出现重复的时候， 就找到共同祖
: 先了。
|
W***u
发帖数: 81 | 7 后面是问了好多次，那个code都写出来了的，然后烙印说是这样的， close 了。只
是看哪一个往上走。 后来细想，知道这样子的话，肯定要计算深度。还是题目不熟，
给这样的题目跪了..
【在 s**********e 的大作中提到】
: 你的第一种解法是比较浪费空间，不知是不是交流有点偏差听错了？这题肯定要计算深
: 度的
|
s**********e
发帖数: 29 | 8 恩其实这题的本质是链表求交点
【在 W***u 的大作中提到】
: 后面是问了好多次，那个code都写出来了的，然后烙印说是这样的， close 了。只
: 是看哪一个往上走。 后来细想，知道这样子的话，肯定要计算深度。还是题目不熟，
: 给这样的题目跪了..
|
W***u
发帖数: 81 | 9 第一次是的，只是一个问问题，另外一个基本没说话，就之前之后说些。第二次面试
，是一个提一个问题。
【在 g*********e 的大作中提到】
: linkedin的店面问什么都是两个人一起面，一个是shadow吗？
|
s*******z
发帖数: 83 | 10 这个题目不知道他要考的比较深一点, 但是给了parent指针一般都会去向上回溯.
这个是可以有O(NlogN)预处理加O(1)的查询时间的.
LCA least common ancester问题经过一次DFS转化以后, 这种问题可以变成RMQ问题.
你可以看看这个: http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static |
|
|
q********c
发帖数: 1774 | 11 bst的话不是很简单吗？
Node *LCA(Node *root, Node *p, Node *q) {
if (!root || !p || !q) return NULL;
if (max(p->data, q->data) < root->data)
return LCA(root->left, p, q);
else if (min(p->data, q->data) > root->data)
return LCA(root->right, p, q);
else
return root;
}
【在 W***u 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
|
m*****n
发帖数: 2152 | 12 你可以问，如果输入A C，是不是要输出 溢出 啊。
烙印简直就是害群之马啊。
【在 W***u 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
|
f******n
发帖数: 279 | |
S********e
发帖数: 74 | 14 第二轮第二题binary search tree找LCA应该比普通binary tree的解法简单一些阿，从
根往下走，要利用bst的性质。
【在 W***u 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
|
r****7
发帖数: 2282 | 15 没有被黑，所有回答中除了一个ID用了BST的属性，其他的都只用了binary tree。
不过BST的那位需要找深度，不满足要求。
【在 W***u 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
|
l****i
发帖数: 2772 | 16 我觉得LZ被黑了，烙印给parent的连接的BST，然后输入不给你root node。这题出的，
就是让你怎么回答，都给差评。
【在 r****7 的大作中提到】
: 没有被黑，所有回答中除了一个ID用了BST的属性，其他的都只用了binary tree。
: 不过BST的那位需要找深度，不满足要求。
|
l*********8
发帖数: 4642 | 17 请问common ancestor那道题是Binary Tree还是BST？
【在 W***u 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
|
W***u
发帖数: 81 | 18 Sorry 手一抖 写错了。 是Binary tree， 不是 BST 。 不好意思，误导大家了。 |
W***u
发帖数: 81 | 19 mark 谢谢！
【在 s*******z 的大作中提到】
: 这个题目不知道他要考的比较深一点, 但是给了parent指针一般都会去向上回溯.
: 这个是可以有O(NlogN)预处理加O(1)的查询时间的.
: LCA least common ancester问题经过一次DFS转化以后, 这种问题可以变成RMQ问题.
: 你可以看看这个: http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
|
r****7
发帖数: 2282 | 20 靠，左转右转的想了一晚上，还是觉得离不开root节点。。。
【在 W***u 的大作中提到】
: Sorry 手一抖 写错了。 是Binary tree， 不是 BST 。 不好意思，误导大家了。
|
|
|
m*****l
发帖数: 95 | 21 其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
吗。。。时间复杂度Log(n) |
m*****l
发帖数: 95 | 22 很多时候其实真心不是被黑，没给最优解可能就不给你onsite了，毕竟onsite一次成本
也要1000刀多了。
【在 m*****l 的大作中提到】
: 其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
: 吗。。。时间复杂度Log(n)
|
l****i
发帖数: 2772 | 23 复杂度应该是O（h）
【在 m*****l 的大作中提到】
: 其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
: 吗。。。时间复杂度Log(n)
|
m*****l
发帖数: 95 | 24 哈哈，补充的好，条件反射平衡树了。 所以说这些小小的问题都可以是挂人的理由，
看要求了。
【在 l****i 的大作中提到】
: 复杂度应该是O（h）
|
W***u
发帖数: 81 | 25 恩恩 是这样的，还是自己需要继续修炼。自己水平还不到家，继续继续。
【在 m*****l 的大作中提到】
: 很多时候其实真心不是被黑，没给最优解可能就不给你onsite了，毕竟onsite一次成本
: 也要1000刀多了。
|
c***8
发帖数: 188 | 26 CC 150里有类似的题
【在 W***u 的大作中提到】
: 恩恩 是这样的，还是自己需要继续修炼。自己水平还不到家，继续继续。
|
l****h
发帖数: 1189 | 27 书里的原题。用hash,复杂度 O(delta(d))。本身不需要root。
但你也知道root->parent=NULL, 可以作为输入的两个Nodes不属于一颗树的错误判别。 |
