为什么大盘是DOW不是S&P500?# Stock
j*r
1 楼
用塑料布抱上的，但是不可能包的密实。车库和房子不是连在一起，单独的。夏天天热
，车库屋顶没有隔热的东西，关上门的话每次进去都会想要昏倒，于是从不管车库门。
这样的话，床垫放了一年，会不会生bed bug?还能用吗？
，车库屋顶没有隔热的东西，关上门的话每次进去都会想要昏倒，于是从不管车库门。
这样的话，床垫放了一年，会不会生bed bug?还能用吗？
W*u
2 楼
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。
求版上各位大神帮忙分析下这个题到底该如何做，然后是不是被黑了。
谢谢！
一个华裔，一个烙印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。
求版上各位大神帮忙分析下这个题到底该如何做，然后是不是被黑了。
谢谢！
N*O
3 楼
对赌博采里面那个大盘。
谢谢~
谢谢~
s*e
4 楼
你的第一种解法是比较浪费空间，不知是不是交流有点偏差听错了？这题肯定要计算深
度的
度的
r*e
5 楼
领导决定的
o*t
6 楼
你和前面那位交流一下看看是不是被同一个烙印黑了。觉得被黑了就要投诉，利人利己
【在 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 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
N*O
7 楼
可是一般说market risk是说的S&P500啊。。。
【在 r*****e 的大作中提到】
: 领导决定的
【在 r*****e 的大作中提到】
: 领导决定的
l*8
8 楼
两个节点同时往root走， 经过的节点放hashmap里， 出现重复的时候， 就找到共同祖
先了。
先了。
g*e
9 楼
linkedin的店面问什么都是两个人一起面，一个是shadow吗？
W*u
10 楼
赞！！ 咋就没想到呢。。
【在 l*********8 的大作中提到】
: 两个节点同时往root走， 经过的节点放hashmap里， 出现重复的时候， 就找到共同祖
: 先了。
【在 l*********8 的大作中提到】
: 两个节点同时往root走， 经过的节点放hashmap里， 出现重复的时候， 就找到共同祖
: 先了。
W*u
11 楼
后面是问了好多次，那个code都写出来了的，然后烙印说是这样的， close 了。只
是看哪一个往上走。 后来细想，知道这样子的话，肯定要计算深度。还是题目不熟，
给这样的题目跪了..
【在 s**********e 的大作中提到】
: 你的第一种解法是比较浪费空间，不知是不是交流有点偏差听错了？这题肯定要计算深
: 度的
是看哪一个往上走。 后来细想，知道这样子的话，肯定要计算深度。还是题目不熟，
给这样的题目跪了..
【在 s**********e 的大作中提到】
: 你的第一种解法是比较浪费空间，不知是不是交流有点偏差听错了？这题肯定要计算深
: 度的
s*e
12 楼
恩其实这题的本质是链表求交点
【在 W***u 的大作中提到】
: 后面是问了好多次，那个code都写出来了的，然后烙印说是这样的， close 了。只
: 是看哪一个往上走。 后来细想，知道这样子的话，肯定要计算深度。还是题目不熟，
: 给这样的题目跪了..
【在 W***u 的大作中提到】
: 后面是问了好多次，那个code都写出来了的，然后烙印说是这样的， close 了。只
: 是看哪一个往上走。 后来细想，知道这样子的话，肯定要计算深度。还是题目不熟，
: 给这样的题目跪了..
W*u
13 楼
第一次是的，只是一个问问题，另外一个基本没说话，就之前之后说些。第二次面试
，是一个提一个问题。
【在 g*********e 的大作中提到】
: linkedin的店面问什么都是两个人一起面，一个是shadow吗？
，是一个提一个问题。
【在 g*********e 的大作中提到】
: linkedin的店面问什么都是两个人一起面，一个是shadow吗？
s*z
14 楼
这个题目不知道他要考的比较深一点, 但是给了parent指针一般都会去向上回溯.
这个是可以有O(NlogN)预处理加O(1)的查询时间的.
LCA least common ancester问题经过一次DFS转化以后, 这种问题可以变成RMQ问题.
你可以看看这个: http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
这个是可以有O(NlogN)预处理加O(1)的查询时间的.
LCA least common ancester问题经过一次DFS转化以后, 这种问题可以变成RMQ问题.
你可以看看这个: http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
q*c
15 楼
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. 就栽在这道题上，感觉
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
16 楼
你可以问，如果输入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. 就栽在这道题上，感觉
烙印简直就是害群之马啊。
【在 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
17 楼
mark
S*e
18 楼
第二轮第二题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. 就栽在这道题上，感觉
根往下走，要利用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
19 楼
没有被黑，所有回答中除了一个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. 就栽在这道题上，感觉
不过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
20 楼
我觉得LZ被黑了，烙印给parent的连接的BST，然后输入不给你root node。这题出的，
就是让你怎么回答，都给差评。
【在 r****7 的大作中提到】
: 没有被黑，所有回答中除了一个ID用了BST的属性，其他的都只用了binary tree。
: 不过BST的那位需要找深度，不满足要求。
就是让你怎么回答，都给差评。
【在 r****7 的大作中提到】
: 没有被黑，所有回答中除了一个ID用了BST的属性，其他的都只用了binary tree。
: 不过BST的那位需要找深度，不满足要求。
l*8
21 楼
请问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 的大作中提到】
: PS1
: 一个华裔，一个烙印mm，面试过程很nice
: Pow(x,n)
: Insert Intervals
: Leetcode 原题
: PS2
: 一个乌克兰gg，也感觉不错，然后烙印..一上来就感觉阴深深的。
: 1. string matching的题，具体忘了，很简单；
: 2. 带 parent member 的binary tree (更正一下，之前手抖写成bst了），找最深的
: common ancestor. 就栽在这道题上，感觉
W*u
22 楼
Sorry 手一抖 写错了。 是Binary tree， 不是 BST 。 不好意思，误导大家了。
W*u
23 楼
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
【在 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
24 楼
靠，左转右转的想了一晚上，还是觉得离不开root节点。。。
【在 W***u 的大作中提到】
: Sorry 手一抖 写错了。 是Binary tree， 不是 BST 。 不好意思，误导大家了。
【在 W***u 的大作中提到】
: Sorry 手一抖 写错了。 是Binary tree， 不是 BST 。 不好意思，误导大家了。
m*l
25 楼
其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
吗。。。时间复杂度Log(n)
吗。。。时间复杂度Log(n)
m*l
26 楼
很多时候其实真心不是被黑，没给最优解可能就不给你onsite了，毕竟onsite一次成本
也要1000刀多了。
【在 m*****l 的大作中提到】
: 其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
: 吗。。。时间复杂度Log(n)
也要1000刀多了。
【在 m*****l 的大作中提到】
: 其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
: 吗。。。时间复杂度Log(n)
l*i
27 楼
复杂度应该是O（h）
【在 m*****l 的大作中提到】
: 其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
: 吗。。。时间复杂度Log(n)
【在 m*****l 的大作中提到】
: 其实呢，两个节点每个走一步，把访问过的节点放在Set里，第一个重复的不就是LCA了
: 吗。。。时间复杂度Log(n)
m*l
28 楼
哈哈，补充的好，条件反射平衡树了。 所以说这些小小的问题都可以是挂人的理由，
看要求了。
【在 l****i 的大作中提到】
: 复杂度应该是O（h）
看要求了。
【在 l****i 的大作中提到】
: 复杂度应该是O（h）
W*u
29 楼
恩恩 是这样的，还是自己需要继续修炼。自己水平还不到家，继续继续。
【在 m*****l 的大作中提到】
: 很多时候其实真心不是被黑，没给最优解可能就不给你onsite了，毕竟onsite一次成本
: 也要1000刀多了。
【在 m*****l 的大作中提到】
: 很多时候其实真心不是被黑，没给最优解可能就不给你onsite了，毕竟onsite一次成本
: 也要1000刀多了。
c*8
30 楼
CC 150里有类似的题
【在 W***u 的大作中提到】
: 恩恩 是这样的，还是自己需要继续修炼。自己水平还不到家，继续继续。
【在 W***u 的大作中提到】
: 恩恩 是这样的，还是自己需要继续修炼。自己水平还不到家，继续继续。
l*h
31 楼
书里的原题。用hash,复杂度 O(delta(d))。本身不需要root。
但你也知道root->parent=NULL, 可以作为输入的两个Nodes不属于一颗树的错误判别。
但你也知道root->parent=NULL, 可以作为输入的两个Nodes不属于一颗树的错误判别。
相关阅读