Quantcast悲剧面经# JobHunting - 待字闺中
B*2
1 楼
首先感谢microleo，给我推荐
电话两轮，一个聊天，一个简单的电面。
Coding Test 一轮，题目为Spread Sheet，大家可以自行Google
得到Positive Feedback
5月8号 On site
分别两个工程师两个项目经理
鉴于每个人多聊了一会我以前的Project，所以每个人问1到3个问题不等。
----------------- 割割割割割割割割 -----------------------------
Q: Spread Sheet 如果太大，不能整个Load进内存来处理。但是可以有多个
机器按照一定的信息读本机文件。假设Spread Sheet每个连通片的计算量
一个机器能够处理
A: Virtually的建立无向连通图，用DFS获得连通片，每个连通片交给一个主机来计算
----------------- 割割割割割割割割 -----------------------------
Q: 给一个森林和已知两个节点，求最近公共祖先，如果没有，返回NULL
A: 我说啥语言没有什么区别，先上伪码，MIT Press Algorithm notation
CommonAncestor(A, B)
1. A' 2. B' 3. a 4. b 5. while(A') do
6. a 7. A' 8. while(B') do
9. b 10. B' 11. d 12. for i 13. if (a > b) A 14. else B 15. while ( A.parnet and B.parent and A.parent != B.parent )
16. A 17. B 18. return A.parent
问他需要什么语言，C/C++或者Python，他说Python
def commonAncestor(A, B):
_A, _B, a, b = A, B, 0, 0
while _A is not none:
a += 1
_A = _A.parent
while _B is not none:
b += 1
_B = _B.parent
d = a - b
for i in range(fabs(d)):
if a > b: A = A.parent
else: B = B.parent
while A.parnet is not B.parent:
A, B = A.parnet, B.parent
return A.parent
----------------- 割割割割割割割割 -----------------------------
Q: 给一个结构，（面试官）叫他Tree,但是跟树的概念有些冲突。就是有些结点
可以有多个父结点，且不一定在同一层。但是没有环。对于任何一个Node，
就各有一个父结点list和子结点list
现在要求实现一个delete操作，删除一个结点不仅仅删除它所关联的所有边
并且，如果子结点无法再连到root，子结点也要被删除。
A: 这实际是个Rooted DAG，那么删除操作，我们用递归来做。删除一个结点的
时候，通过parent关系，找到对应的parent并删除连到这个结点的边。找到
子结点，并删除子节点parent list里连到这个结点的边。当子结点失去所有
父结点时候，对子结点进行此删除操作。
Comment: 这个题想得慢了点，一开始想维护一个队列的。在提示下改成这样的
----------------- 割割割割割割割割 -----------------------------
Q: 给一个数组，其中有一个数是unique的，只出现一次，其他的数都出现两次
问如何求这个数
A: 用Xor操作把数组直接全抑或一遍，就只剩下一个unique的值，因为相同的
抑或等于0。时间复杂度O(n)，in place
Q: 如果非unique的数不是出现两次，而是两次或两次以上且不一定为偶数次
上述问题如何解决？
A: In place的话，先Sort一遍，然后从头往后scan，看谁和自己邻居都不等
Sort时间O(N logN)，scan时间O(n)，一共O(N logN)
Q: 如果已经是Sorted Order，且每个非unique的数出现两次。你的算法能优化么？
A: 用类似Binary Search, 每次找到中点，如果它和邻居都不同，则就是它
否则，找到相同的邻居（左或者右）。以他俩为分界，看两遍区间哪个区间
长度为奇数，就在哪个子区间找。对于每次查看，时间为O(1)，然后把问题
规模变为1/2原问题。所以总的时间复杂度为
T(n) = T(n/2) + O(1) = O(logN)
Q: Code out
A: Let first do it by notations in Introduction of Algorithm of MIT Press
unique(A, i, j)
1. if ( i = j ) return A[i]
2. mid 3. if ( A[mid] != A[mid-1] and A[mid] != A[mid+1] ) return A[mid]
4. if ( A[mid] = A[mid-1] )
5. then if ( (mid - i) % 2 )
6. then return unique(A, i, mid-2)
7. else return unique(A, i+1, j)
8. else if ( (j - mid) % 2 )
9. then return unique(A, mid+2, j)
10. else return unique(A, i, mid-1)
A: Check for bug-free and which language do you prefer I use?
Q: Let's do it in python
def unique(A, i, j):
if i == j: return A[i]
mid = （i+j)/2
if A[mid] != A[mid-1] and A[mid] != A[mid+1]: return A[mid]
if A[mid] == A[mid-1]:
if (mid - 1) % 2 != 0: return unique(A, i, mid-2)
else: return return unique(A, i+1, j)
else:
if (j - mid) % 2 != 0: return unique(A, mid+2, j)
else: return unique(A, i, mid-1)
----------------- 割割割割割割割割 -----------------------------
Q: 给一个Magic function uni5(), 它可以等概率的返回0,1,2,3,4
请只调用uni5()，完成一个uni8()
A: 这里uni5的值域空间大小为5，肯定无法提供一个值域空间为8的随机
所以，我要扩大它的空间，且让每个值都概率均等，然后assign给不同
的返回值。
uni8():
1.magic 2.if ( magic != 24 ) return magic % 8
3.else return uni8()
就是给一个25个值的等概率空间，前24个值的话，每3个值分配一个返回值
如果不在这个范围（magic等于24了），则重做一遍。
这是个由多个Monte-Carlo算法叠加的Las-Vegas算法。单个Monte-Carlo
不fail的概率为24/25。所以Las-Vegas算法执行的期望次数为25/24
所以这是一个O(1)期望时间的概率算法
----------------- 割割割割割割割割 -----------------------------
Q: 给定一个Triple，为三个单词（其实就是纯字母组成的字符串），判断
第三个可不可以由前两个拼装出来，拼装规则是每个字母都要用到，且
同一个词里的相对顺序不能颠倒
如: CATS, CHOEG, CHCAOTEGS是可行的
CD, DC, CCDD是不行的（顺序问题）
AT, ME, ATM是不行的（剩余字母）
A: 对于三个单词从头开始scan，第三个单词的当前字母为期待，从前两个
单词那里拿，如果没有，则返回失败。这在字母都不相同的情况下，是
linear的，但是如果有相同的。采用回溯法，就是来探测子问题的解。
任意一个分支走通，则整体有解。只有所有分支都走不通，才返回失败
Q: 分析时间复杂度
这个是最后一个题，当时面了一天，所以累得没啥状态了。还没分析完，
HR进来了，表示先谈到这里吧。
之前午饭的时候听说最近他们要人必须所有人feedback都是impressive的
前三个面试官，除了Tree删除那道题需要Hint了一下，其余题基本都是秒
最后一个人就是分析复杂度的时候有点跟不上了
总之，从头再来吧，当然，也欢迎各位帮内推。不胜感激
电话两轮，一个聊天，一个简单的电面。
Coding Test 一轮，题目为Spread Sheet，大家可以自行Google
得到Positive Feedback
5月8号 On site
分别两个工程师两个项目经理
鉴于每个人多聊了一会我以前的Project，所以每个人问1到3个问题不等。
----------------- 割割割割割割割割 -----------------------------
Q: Spread Sheet 如果太大，不能整个Load进内存来处理。但是可以有多个
机器按照一定的信息读本机文件。假设Spread Sheet每个连通片的计算量
一个机器能够处理
A: Virtually的建立无向连通图，用DFS获得连通片，每个连通片交给一个主机来计算
----------------- 割割割割割割割割 -----------------------------
Q: 给一个森林和已知两个节点，求最近公共祖先，如果没有，返回NULL
A: 我说啥语言没有什么区别，先上伪码，MIT Press Algorithm notation
CommonAncestor(A, B)
1. A' 2. B' 3. a 4. b 5. while(A') do
6. a 7. A' 8. while(B') do
9. b 10. B' 11. d 12. for i 13. if (a > b) A 14. else B 15. while ( A.parnet and B.parent and A.parent != B.parent )
16. A 17. B 18. return A.parent
问他需要什么语言，C/C++或者Python，他说Python
def commonAncestor(A, B):
_A, _B, a, b = A, B, 0, 0
while _A is not none:
a += 1
_A = _A.parent
while _B is not none:
b += 1
_B = _B.parent
d = a - b
for i in range(fabs(d)):
if a > b: A = A.parent
else: B = B.parent
while A.parnet is not B.parent:
A, B = A.parnet, B.parent
return A.parent
----------------- 割割割割割割割割 -----------------------------
Q: 给一个结构，（面试官）叫他Tree,但是跟树的概念有些冲突。就是有些结点
可以有多个父结点，且不一定在同一层。但是没有环。对于任何一个Node，
就各有一个父结点list和子结点list
现在要求实现一个delete操作，删除一个结点不仅仅删除它所关联的所有边
并且，如果子结点无法再连到root，子结点也要被删除。
A: 这实际是个Rooted DAG，那么删除操作，我们用递归来做。删除一个结点的
时候，通过parent关系，找到对应的parent并删除连到这个结点的边。找到
子结点，并删除子节点parent list里连到这个结点的边。当子结点失去所有
父结点时候，对子结点进行此删除操作。
Comment: 这个题想得慢了点，一开始想维护一个队列的。在提示下改成这样的
----------------- 割割割割割割割割 -----------------------------
Q: 给一个数组，其中有一个数是unique的，只出现一次，其他的数都出现两次
问如何求这个数
A: 用Xor操作把数组直接全抑或一遍，就只剩下一个unique的值，因为相同的
抑或等于0。时间复杂度O(n)，in place
Q: 如果非unique的数不是出现两次，而是两次或两次以上且不一定为偶数次
上述问题如何解决？
A: In place的话，先Sort一遍，然后从头往后scan，看谁和自己邻居都不等
Sort时间O(N logN)，scan时间O(n)，一共O(N logN)
Q: 如果已经是Sorted Order，且每个非unique的数出现两次。你的算法能优化么？
A: 用类似Binary Search, 每次找到中点，如果它和邻居都不同，则就是它
否则，找到相同的邻居（左或者右）。以他俩为分界，看两遍区间哪个区间
长度为奇数，就在哪个子区间找。对于每次查看，时间为O(1)，然后把问题
规模变为1/2原问题。所以总的时间复杂度为
T(n) = T(n/2) + O(1) = O(logN)
Q: Code out
A: Let first do it by notations in Introduction of Algorithm of MIT Press
unique(A, i, j)
1. if ( i = j ) return A[i]
2. mid 3. if ( A[mid] != A[mid-1] and A[mid] != A[mid+1] ) return A[mid]
4. if ( A[mid] = A[mid-1] )
5. then if ( (mid - i) % 2 )
6. then return unique(A, i, mid-2)
7. else return unique(A, i+1, j)
8. else if ( (j - mid) % 2 )
9. then return unique(A, mid+2, j)
10. else return unique(A, i, mid-1)
A: Check for bug-free and which language do you prefer I use?
Q: Let's do it in python
def unique(A, i, j):
if i == j: return A[i]
mid = （i+j)/2
if A[mid] != A[mid-1] and A[mid] != A[mid+1]: return A[mid]
if A[mid] == A[mid-1]:
if (mid - 1) % 2 != 0: return unique(A, i, mid-2)
else: return return unique(A, i+1, j)
else:
if (j - mid) % 2 != 0: return unique(A, mid+2, j)
else: return unique(A, i, mid-1)
----------------- 割割割割割割割割 -----------------------------
Q: 给一个Magic function uni5(), 它可以等概率的返回0,1,2,3,4
请只调用uni5()，完成一个uni8()
A: 这里uni5的值域空间大小为5，肯定无法提供一个值域空间为8的随机
所以，我要扩大它的空间，且让每个值都概率均等，然后assign给不同
的返回值。
uni8():
1.magic 2.if ( magic != 24 ) return magic % 8
3.else return uni8()
就是给一个25个值的等概率空间，前24个值的话，每3个值分配一个返回值
如果不在这个范围（magic等于24了），则重做一遍。
这是个由多个Monte-Carlo算法叠加的Las-Vegas算法。单个Monte-Carlo
不fail的概率为24/25。所以Las-Vegas算法执行的期望次数为25/24
所以这是一个O(1)期望时间的概率算法
----------------- 割割割割割割割割 -----------------------------
Q: 给定一个Triple，为三个单词（其实就是纯字母组成的字符串），判断
第三个可不可以由前两个拼装出来，拼装规则是每个字母都要用到，且
同一个词里的相对顺序不能颠倒
如: CATS, CHOEG, CHCAOTEGS是可行的
CD, DC, CCDD是不行的（顺序问题）
AT, ME, ATM是不行的（剩余字母）
A: 对于三个单词从头开始scan，第三个单词的当前字母为期待，从前两个
单词那里拿，如果没有，则返回失败。这在字母都不相同的情况下，是
linear的，但是如果有相同的。采用回溯法，就是来探测子问题的解。
任意一个分支走通，则整体有解。只有所有分支都走不通，才返回失败
Q: 分析时间复杂度
这个是最后一个题，当时面了一天，所以累得没啥状态了。还没分析完，
HR进来了，表示先谈到这里吧。
之前午饭的时候听说最近他们要人必须所有人feedback都是impressive的
前三个面试官，除了Tree删除那道题需要Hint了一下，其余题基本都是秒
最后一个人就是分析复杂度的时候有点跟不上了
总之，从头再来吧，当然，也欢迎各位帮内推。不胜感激
