Amazon电面纪实 - 未名空间MITBBS历史存档

i*r2012-11-01 07:11

1 楼

在网上申的Amazon
本来想申请社招岗位，HR非把我放到campus hire里面
第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
两次电面之后，HR说要追加一次电面。
第三次电面，两题：
如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
问的点，就改成用类似Floyd算法来做，但是效率就不高了。
第三次电面结束后几分钟，HR就发信把我拒了，难过了半天：（
回忆起来，第一次电面没做好，因为当时在路上，没法用电脑写程序，只能口述。
第三次电面，想来是最后一个图论题目没做好。
以后有机会再试试A家，不拿到onsite不甘心啊。

f*e2012-11-01 07:11

2 楼

第三次面试最后一题，是不是check每个vertex的neighbours，看是否有label相同的？
复杂度O(|E|)？binary tree里有环是什么意思?

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

i*r2012-11-01 07:11

3 楼

嗯，应该是这样的
check所有某点相邻的点
有什么高效的办法check么？

【在 f*****e 的大作中提到】

: 第三次面试最后一题，是不是check每个vertex的neighbours，看是否有label相同的？
: 复杂度O(|E|)？binary tree里有环是什么意思?

f*e2012-11-01 07:11

4 楼

可以用hash，或者label是1到n的话，就用一个size为n的数组当bucket。

【在 i******r 的大作中提到】

: 嗯，应该是这样的
: check所有某点相邻的点
: 有什么高效的办法check么？

r*e2012-11-01 07:11

5 楼

Question about 判断一个binary tree里面是否有环:
I think we can do it by hashtable to check whether we visited it or not.
However, it takes extra space. Is there any way we can do it without extra
space? Thanks!

e*s2012-11-01 07:11

6 楼

请问ｂｉｎａｒｙ　ｔｒｅｅ是否有环怎么做？
我觉得Hashtable也不能check是否有环，只能check是否有node不只一个parent

s*s2012-11-01 07:11

7 楼

Tree的节点允许标记是否visited吗？遍历树，经过的就标记为visited或者visiting。
如果再次遇到visited或visiting的node就认为是个环吧。
环是需要方向也正确，还是只要是个circle就行了呢?

r*e2012-11-01 07:11

8 楼

How about pre-order visit the tree and keep a record for those already
visited, if current node is in the table, it means it is already visited,
therefore, there is a loop.
here, we can use stl::map to simulate hash table.
//cpp code
bool is_loop(Node* node, map& dict){
if(!node)
return false;
if(dict.find(node) == dict.end()){
dict[node] = false;
bool left = is_loop(node->left, dict);
if(left)
return true;
return is_loop(node->right, dict);
}else{
return true;
}
}

【在 e***s 的大作中提到】

: 请问ｂｉｎａｒｙ　ｔｒｅｅ是否有环怎么做？
: 我觉得Hashtable也不能check是否有环，只能check是否有node不只一个parent

e*s2012-11-01 07:11

9 楼

我的问题是，一个node有两个parents，不考虑方向的话可以视为有环，但是如果考虑
方向的话，就不能算了，因为这个Tree是可以遍历完的。如果考虑方向有环的话，tree
是不能遍历完的，不标记visited 的情况下。

【在 r*****e 的大作中提到】

: How about pre-order visit the tree and keep a record for those already
: visited, if current node is in the table, it means it is already visited,
: therefore, there is a loop.
: here, we can use stl::map to simulate hash table.
: //cpp code
: bool is_loop(Node* node, map& dict){
: if(!node)
: return false;
: if(dict.find(node) == dict.end()){
: dict[node] = false;

C*U2012-11-01 07:11

10 楼

他们家这么多电面啊

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

K*i2012-11-01 07:11

11 楼

四次电面被拒的都有听说过的。其实次数越多，很可能几个面试官意见不一致，一般发
挥好，两次就够用了。

d*x2012-11-01 07:11

12 楼

就是标记
其实问的是判断是否DAG的一个特例。。。按照CLRS上面说的DFS就出来了呗。如果不好
理解的话，BFS也很直观。。。

【在 s*********s 的大作中提到】

: Tree的节点允许标记是否visited吗？遍历树，经过的就标记为visited或者visiting。
: 如果再次遇到visited或visiting的node就认为是个环吧。
: 环是需要方向也正确，还是只要是个circle就行了呢?

f*t2012-11-01 07:11

13 楼

大哥...你居然在路上电话面试....

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

z*i2012-11-01 07:11

14 楼

赞一个，详细。

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

h*u2012-11-01 07:11

15 楼

Bless

i*r2012-11-01 07:11

16 楼

大家都在讨论这题啊
这题我说的不够详细，其实是一个rooted binary tree
可以标记visited
我当时的做法就是搜索

【在 s*********s 的大作中提到】

: Tree的节点允许标记是否visited吗？遍历树，经过的就标记为visited或者visiting。
: 如果再次遇到visited或visiting的node就认为是个环吧。
: 环是需要方向也正确，还是只要是个circle就行了呢?

f*42012-11-01 07:11

17 楼

环有无方向？
不是比较非空边和结点的数量么

【在 i******r 的大作中提到】

: 大家都在讨论这题啊
: 这题我说的不够详细，其实是一个rooted binary tree
: 可以标记visited
: 我当时的做法就是搜索

h*n2012-11-01 07:11

18 楼

现在都开始考图了郁闷。。看来还是得多练习练习。。。

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

i*r2012-11-01 07:11

19 楼

在网上申的Amazon
本来想申请社招岗位，HR非把我放到campus hire里面
第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
两次电面之后，HR说要追加一次电面。
第三次电面，两题：
如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
问的点，就改成用类似Floyd算法来做，但是效率就不高了。
第三次电面结束后几分钟，HR就发信把我拒了，难过了半天：（
回忆起来，第一次电面没做好，因为当时在路上，没法用电脑写程序，只能口述。
第三次电面，想来是最后一个图论题目没做好。
以后有机会再试试A家，不拿到onsite不甘心啊。

f*e2012-11-01 07:11

20 楼

第三次面试最后一题，是不是check每个vertex的neighbours，看是否有label相同的？
复杂度O(|E|)？binary tree里有环是什么意思?

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

i*r2012-11-01 07:11

21 楼

嗯，应该是这样的
check所有某点相邻的点
有什么高效的办法check么？

【在 f*****e 的大作中提到】

: 第三次面试最后一题，是不是check每个vertex的neighbours，看是否有label相同的？
: 复杂度O(|E|)？binary tree里有环是什么意思?

f*e2012-11-01 07:11

22 楼

可以用hash，或者label是1到n的话，就用一个size为n的数组当bucket。

【在 i******r 的大作中提到】

: 嗯，应该是这样的
: check所有某点相邻的点
: 有什么高效的办法check么？

r*e2012-11-01 07:11

23 楼

Question about 判断一个binary tree里面是否有环:
I think we can do it by hashtable to check whether we visited it or not.
However, it takes extra space. Is there any way we can do it without extra
space? Thanks!

e*s2012-11-01 07:11

24 楼

请问ｂｉｎａｒｙ　ｔｒｅｅ是否有环怎么做？
我觉得Hashtable也不能check是否有环，只能check是否有node不只一个parent

s*s2012-11-01 07:11

25 楼

Tree的节点允许标记是否visited吗？遍历树，经过的就标记为visited或者visiting。
如果再次遇到visited或visiting的node就认为是个环吧。
环是需要方向也正确，还是只要是个circle就行了呢?

r*e2012-11-01 07:11

26 楼

How about pre-order visit the tree and keep a record for those already
visited, if current node is in the table, it means it is already visited,
therefore, there is a loop.
here, we can use stl::map to simulate hash table.
//cpp code
bool is_loop(Node* node, map& dict){
if(!node)
return false;
if(dict.find(node) == dict.end()){
dict[node] = false;
bool left = is_loop(node->left, dict);
if(left)
return true;
return is_loop(node->right, dict);
}else{
return true;
}
}

【在 e***s 的大作中提到】

: 请问ｂｉｎａｒｙ　ｔｒｅｅ是否有环怎么做？
: 我觉得Hashtable也不能check是否有环，只能check是否有node不只一个parent

e*s2012-11-01 07:11

27 楼

我的问题是，一个node有两个parents，不考虑方向的话可以视为有环，但是如果考虑
方向的话，就不能算了，因为这个Tree是可以遍历完的。如果考虑方向有环的话，tree
是不能遍历完的，不标记visited 的情况下。

【在 r*****e 的大作中提到】

: How about pre-order visit the tree and keep a record for those already
: visited, if current node is in the table, it means it is already visited,
: therefore, there is a loop.
: here, we can use stl::map to simulate hash table.
: //cpp code
: bool is_loop(Node* node, map& dict){
: if(!node)
: return false;
: if(dict.find(node) == dict.end()){
: dict[node] = false;

C*U2012-11-01 07:11

28 楼

他们家这么多电面啊

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

K*i2012-11-01 07:11

29 楼

四次电面被拒的都有听说过的。其实次数越多，很可能几个面试官意见不一致，一般发
挥好，两次就够用了。

d*x2012-11-01 07:11

30 楼

就是标记
其实问的是判断是否DAG的一个特例。。。按照CLRS上面说的DFS就出来了呗。如果不好
理解的话，BFS也很直观。。。

【在 s*********s 的大作中提到】

: Tree的节点允许标记是否visited吗？遍历树，经过的就标记为visited或者visiting。
: 如果再次遇到visited或visiting的node就认为是个环吧。
: 环是需要方向也正确，还是只要是个circle就行了呢?

f*t2012-11-01 07:11

31 楼

大哥...你居然在路上电话面试....

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

z*i2012-11-01 07:11

32 楼

赞一个，详细。

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

h*u2012-11-01 07:11

33 楼

Bless

i*r2012-11-01 07:11

34 楼

大家都在讨论这题啊
这题我说的不够详细，其实是一个rooted binary tree
可以标记visited
我当时的做法就是搜索

【在 s*********s 的大作中提到】

: Tree的节点允许标记是否visited吗？遍历树，经过的就标记为visited或者visiting。
: 如果再次遇到visited或visiting的node就认为是个环吧。
: 环是需要方向也正确，还是只要是个circle就行了呢?

f*42012-11-01 07:11

35 楼

环有无方向？
不是比较非空边和结点的数量么

【在 i******r 的大作中提到】

: 大家都在讨论这题啊
: 这题我说的不够详细，其实是一个rooted binary tree
: 可以标记visited
: 我当时的做法就是搜索

h*n2012-11-01 07:11

36 楼

现在都开始考图了郁闷。。看来还是得多练习练习。。。

【在 i******r 的大作中提到】

: 在网上申的Amazon
: 本来想申请社招岗位，HR非把我放到campus hire里面
: 第一次电面，问了两题：2sum和判断一个binary tree里面是否有环
: 第二次电面，也是两题：判断两数相加的结果是否会溢出，以及求N以内的素数
: 两次电面之后，HR说要追加一次电面。
: 第三次电面，两题：
: 如何取出linkedlist从尾端开始的第n个node，这题没啥好说的，线性做法。
: 从一个无向图里面，找出两个label相同的vertex，它们必须同时关联另一个vertex（
: 就是距离为2）。这题我开始想用DFS，对每个vertex搜一次。后来发现不好记录已经访
: 问的点，就改成用类似Floyd算法来做，但是效率就不高了。

i*e2012-11-01 07:11

37 楼

邻接点存在adjacency list中，只要依次遍历所有节点的adjacency list应该就行了吧？

【在 i******r 的大作中提到】

: 嗯，应该是这样的
: check所有某点相邻的点
: 有什么高效的办法check么？

l*b2012-11-01 07:11

38 楼

Mark, 继续加油。

r*i2012-11-01 07:11

39 楼

楼主加油，我就一轮店面就没消息了。