攒人品，Amazon 二面面经 - 未名空间MITBBS历史存档

f*z2011-12-14 08:12

1 楼

2nd phone interview之后悲剧。下面是面经
1st phone:
Question about the project I listed on my resume
Basic questions on Java, what I can remember includes
(1) difference between stack and heap
(2) inheritance in java
(3) multi-threading
(4) difference between abstract class and interface
Open question, find which 三连击 on Amazon's website is the most popular.
2nd phone:
Question on web application I've developed. How to scale up? How to handle
concurrent requests etc.
Coding question:
(1) implement spell checking function
(2) there are two BSTs, write a program to determine whether they have the
same set of values.
感觉跟amazon的面试官交流的时候气氛很dry，第一个面试官，答完了也没有反馈，接
着问下一道；第二个面试官写完程序也不告诉你他认为怎么样，有没有错什么的。

x*i2011-12-14 08:12

2 楼

有包子才有人品啊。。。

p*22011-12-14 08:12

3 楼

(2) there are two BSTs, write a program to determine whether they have the
same set of values.
就是return true or false吗？

f*z2011-12-14 08:12

4 楼

我所有的包子都在某年某月某日给了别人了。。

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

: 有包子才有人品啊。。。

f*z2011-12-14 08:12

5 楼

是嗒。

【在 p*****2 的大作中提到】

: (2) there are two BSTs, write a program to determine whether they have the
: same set of values.
: 就是return true or false吗？

q*x2011-12-14 08:12

6 楼

how to do spell checking?

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

: 2nd phone interview之后悲剧。下面是面经
: 1st phone:
: Question about the project I listed on my resume
: Basic questions on Java, what I can remember includes
: (1) difference between stack and heap
: (2) inheritance in java
: (3) multi-threading
: (4) difference between abstract class and interface
: Open question, find which 三连击 on Amazon's website is the most popular.
: 2nd phone:

c*z2011-12-14 08:12

7 楼

how to do spell checking

f*z2011-12-14 08:12

8 楼

我的做法是用一个字典，把字典的词按字母排序，然后建一个hashtable,排过序的字母
序列作为key，所有具有相同entry的词组成一个链表，作为value。当输入一个拼错的
单词时，就可以look up hashtable给出recommendation了。

【在 q****x 的大作中提到】

: how to do spell checking?

q*x2011-12-14 08:12

9 楼

没看懂。每个链表都是key的一个排列吗？那你假定拼写错误都是次序错，忽略多输、
少输、输错的情况？

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

: 我的做法是用一个字典，把字典的词按字母排序，然后建一个hashtable,排过序的字母
: 序列作为key，所有具有相同entry的词组成一个链表，作为value。当输入一个拼错的
: 单词时，就可以look up hashtable给出recommendation了。

s*n2011-12-14 08:12

10 楼

有现成的代码
PYTHON的马上就可以用，很好懂
http://norvig.com/spell-correct.html

【在 q****x 的大作中提到】

: 没看懂。每个链表都是key的一个排列吗？那你假定拼写错误都是次序错，忽略多输、
: 少输、输错的情况？

c*e2011-12-14 08:12

11 楼

bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
if(!one && !two) return true;
else if(!one && two) return false;
else if(one && !two) return false;
else return (one->data).equal(two->data)
&& equal(one->left,two->left) && equal(one->right,two->right);
}

【在 p*****2 的大作中提到】

: (2) there are two BSTs, write a program to determine whether they have the
: same set of values.
: 就是return true or false吗？

q*x2011-12-14 08:12

12 楼

wrong. they can have same data set but different topologies.

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

: bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
: if(!one && !two) return true;
: else if(!one && two) return false;
: else if(one && !two) return false;
: else return (one->data).equal(two->data)
: && equal(one->left,two->left) && equal(one->right,two->right);
: }

f*z2011-12-14 08:12

13 楼

what I did is inorder traverse and then compared the two sorted array.

【在 q****x 的大作中提到】

: wrong. they can have same data set but different topologies.

f*z2011-12-14 08:12

14 楼

assume不会有多输，少输，输错的情况。。

【在 q****x 的大作中提到】

: 没看懂。每个链表都是key的一个排列吗？那你假定拼写错误都是次序错，忽略多输、
: 少输、输错的情况？

c*e2011-12-14 08:12

15 楼

How about this one?
void inorder(vector& v, BinaryTreeNode* node) {
if(node) {
inorder(v, node->left);
v.push_back(node->data);
inorder(v, node->right);
}
}
bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
vector v1, v2;
inorder(v1, one);
inorder(v2, two);
return v1.equal(v2);
}

【在 q****x 的大作中提到】

: wrong. they can have same data set but different topologies.

q*x2011-12-14 08:12

16 楼

那您应该加到题目里啊。这假设很重要。

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

: assume不会有多输，少输，输错的情况。。

q*x2011-12-14 08:12

17 楼

yes, this is good.

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

: How about this one?
: void inorder(vector& v, BinaryTreeNode* node) {
: if(node) {
: inorder(v, node->left);
: v.push_back(node->data);
: inorder(v, node->right);
: }
: }
: bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
: vector v1, v2;

p*42011-12-14 08:12

18 楼

顶!

s*n2011-12-14 08:12

19 楼

using too many spaces if the tree is huge.

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

: How about this one?
: void inorder(vector& v, BinaryTreeNode* node) {
: if(node) {
: inorder(v, node->left);
: v.push_back(node->data);
: inorder(v, node->right);
: }
: }
: bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
: vector v1, v2;

q*x2011-12-14 08:12

20 楼

then traverse tree x and query tree b.

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

: using too many spaces if the tree is huge.

s*n2011-12-14 08:12

21 楼

依然大，最好的办法是用2个stack同时in-order traverse，当然对写代码要求就比递
归高了

【在 q****x 的大作中提到】

: then traverse tree x and query tree b.

q*x2011-12-14 08:12

22 楼

怎么会大？那样可以O(1)。
用stack worst case也是O(N)开销吧。

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

: 依然大，最好的办法是用2个stack同时in-order traverse，当然对写代码要求就比递
: 归高了

b*32011-12-14 08:12

23 楼

a)遍历第一棵树，建一个hashtable，每个数字对应出现次数
b)遍历第二棵树，递减hashtable里相应数字的出现次数。如果hashtable里没有，就返
回false。当一个数字出现次数为0就remove。最后如果hashtable空，就表示一样。

【在 q****x 的大作中提到】

: 怎么会大？那样可以O(1)。
: 用stack worst case也是O(N)开销吧。

g*n2011-12-14 08:12

24 楼

amazon jobs:
http://jobguiding.com/it-jobs/it-companies/amazon.html

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

: 2nd phone interview之后悲剧。下面是面经
: 1st phone:
: Question about the project I listed on my resume
: Basic questions on Java, what I can remember includes
: (1) difference between stack and heap
: (2) inheritance in java
: (3) multi-threading
: (4) difference between abstract class and interface
: Open question, find which 三连击 on Amazon's website is the most popular.
: 2nd phone:

p*22011-12-14 08:12

25 楼

三连击这题有人说说吗？

H*e2011-12-14 08:12

26 楼

This is not inorder traversal

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

: what I did is inorder traverse and then compared the two sorted array.

c*e2011-12-14 08:12

27 楼

Why? Do not understand it.

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

: This is not inorder traversal

l*a2011-12-14 08:12

28 楼

are there duplicate in binary tree?

【在 b*********3 的大作中提到】

: a)遍历第一棵树，建一个hashtable，每个数字对应出现次数
: b)遍历第二棵树，递减hashtable里相应数字的出现次数。如果hashtable里没有，就返
: 回false。当一个数字出现次数为0就remove。最后如果hashtable空，就表示一样。

f*z2011-12-14 08:12

29 楼

2nd phone interview之后悲剧。下面是面经
1st phone:
Question about the project I listed on my resume
Basic questions on Java, what I can remember includes
(1) difference between stack and heap
(2) inheritance in java
(3) multi-threading
(4) difference between abstract class and interface
Open question, find which 三连击 on Amazon's website is the most popular.
2nd phone:
Question on web application I've developed. How to scale up? How to handle
concurrent requests etc.
Coding question:
(1) implement spell checking function
(2) there are two BSTs, write a program to determine whether they have the
same set of values.
感觉跟amazon的面试官交流的时候气氛很dry，第一个面试官，答完了也没有反馈，接
着问下一道；第二个面试官写完程序也不告诉你他认为怎么样，有没有错什么的。

x*i2011-12-14 08:12

30 楼

有包子才有人品啊。。。

p*22011-12-14 08:12

31 楼

(2) there are two BSTs, write a program to determine whether they have the
same set of values.
就是return true or false吗？

f*z2011-12-14 08:12

32 楼

我所有的包子都在某年某月某日给了别人了。。

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

: 有包子才有人品啊。。。

f*z2011-12-14 08:12

33 楼

是嗒。

【在 p*****2 的大作中提到】

: (2) there are two BSTs, write a program to determine whether they have the
: same set of values.
: 就是return true or false吗？

q*x2011-12-14 08:12

34 楼

how to do spell checking?

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

: 2nd phone interview之后悲剧。下面是面经
: 1st phone:
: Question about the project I listed on my resume
: Basic questions on Java, what I can remember includes
: (1) difference between stack and heap
: (2) inheritance in java
: (3) multi-threading
: (4) difference between abstract class and interface
: Open question, find which 三连击 on Amazon's website is the most popular.
: 2nd phone:

c*z2011-12-14 08:12

35 楼

how to do spell checking

f*z2011-12-14 08:12

36 楼

我的做法是用一个字典，把字典的词按字母排序，然后建一个hashtable,排过序的字母
序列作为key，所有具有相同entry的词组成一个链表，作为value。当输入一个拼错的
单词时，就可以look up hashtable给出recommendation了。

【在 q****x 的大作中提到】

: how to do spell checking?

q*x2011-12-14 08:12

37 楼

没看懂。每个链表都是key的一个排列吗？那你假定拼写错误都是次序错，忽略多输、
少输、输错的情况？

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

: 我的做法是用一个字典，把字典的词按字母排序，然后建一个hashtable,排过序的字母
: 序列作为key，所有具有相同entry的词组成一个链表，作为value。当输入一个拼错的
: 单词时，就可以look up hashtable给出recommendation了。

s*n2011-12-14 08:12

38 楼

有现成的代码
PYTHON的马上就可以用，很好懂
http://norvig.com/spell-correct.html

【在 q****x 的大作中提到】

: 没看懂。每个链表都是key的一个排列吗？那你假定拼写错误都是次序错，忽略多输、
: 少输、输错的情况？

c*e2011-12-14 08:12

39 楼

bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
if(!one && !two) return true;
else if(!one && two) return false;
else if(one && !two) return false;
else return (one->data).equal(two->data)
&& equal(one->left,two->left) && equal(one->right,two->right);
}

【在 p*****2 的大作中提到】

: (2) there are two BSTs, write a program to determine whether they have the
: same set of values.
: 就是return true or false吗？

q*x2011-12-14 08:12

40 楼

wrong. they can have same data set but different topologies.

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

: bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
: if(!one && !two) return true;
: else if(!one && two) return false;
: else if(one && !two) return false;
: else return (one->data).equal(two->data)
: && equal(one->left,two->left) && equal(one->right,two->right);
: }

f*z2011-12-14 08:12

41 楼

what I did is inorder traverse and then compared the two sorted array.

【在 q****x 的大作中提到】

: wrong. they can have same data set but different topologies.

f*z2011-12-14 08:12

42 楼

assume不会有多输，少输，输错的情况。。

【在 q****x 的大作中提到】

: 没看懂。每个链表都是key的一个排列吗？那你假定拼写错误都是次序错，忽略多输、
: 少输、输错的情况？

c*e2011-12-14 08:12

43 楼

How about this one?
void inorder(vector& v, BinaryTreeNode* node) {
if(node) {
inorder(v, node->left);
v.push_back(node->data);
inorder(v, node->right);
}
}
bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
vector v1, v2;
inorder(v1, one);
inorder(v2, two);
return v1.equal(v2);
}

【在 q****x 的大作中提到】

: wrong. they can have same data set but different topologies.

q*x2011-12-14 08:12

44 楼

那您应该加到题目里啊。这假设很重要。

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

: assume不会有多输，少输，输错的情况。。

q*x2011-12-14 08:12

45 楼

yes, this is good.

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

: How about this one?
: void inorder(vector& v, BinaryTreeNode* node) {
: if(node) {
: inorder(v, node->left);
: v.push_back(node->data);
: inorder(v, node->right);
: }
: }
: bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
: vector v1, v2;

p*42011-12-14 08:12

46 楼

顶!

s*n2011-12-14 08:12

47 楼

using too many spaces if the tree is huge.

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

: How about this one?
: void inorder(vector& v, BinaryTreeNode* node) {
: if(node) {
: inorder(v, node->left);
: v.push_back(node->data);
: inorder(v, node->right);
: }
: }
: bool equal(BinaryTreeNode* one, BinaryTreeNode* two) {
: vector v1, v2;

q*x2011-12-14 08:12

48 楼

then traverse tree x and query tree b.

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

: using too many spaces if the tree is huge.

s*n2011-12-14 08:12

49 楼

依然大，最好的办法是用2个stack同时in-order traverse，当然对写代码要求就比递
归高了

【在 q****x 的大作中提到】

: then traverse tree x and query tree b.

q*x2011-12-14 08:12

50 楼

怎么会大？那样可以O(1)。
用stack worst case也是O(N)开销吧。

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

: 依然大，最好的办法是用2个stack同时in-order traverse，当然对写代码要求就比递
: 归高了

b*32011-12-14 08:12

51 楼

a)遍历第一棵树，建一个hashtable，每个数字对应出现次数
b)遍历第二棵树，递减hashtable里相应数字的出现次数。如果hashtable里没有，就返
回false。当一个数字出现次数为0就remove。最后如果hashtable空，就表示一样。

【在 q****x 的大作中提到】

: 怎么会大？那样可以O(1)。
: 用stack worst case也是O(N)开销吧。

g*n2011-12-14 08:12

52 楼

amazon jobs:
http://jobguiding.com/it-jobs/it-companies/amazon.html

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

: 2nd phone interview之后悲剧。下面是面经
: 1st phone:
: Question about the project I listed on my resume
: Basic questions on Java, what I can remember includes
: (1) difference between stack and heap
: (2) inheritance in java
: (3) multi-threading
: (4) difference between abstract class and interface
: Open question, find which 三连击 on Amazon's website is the most popular.
: 2nd phone:

p*22011-12-14 08:12

53 楼

三连击这题有人说说吗？

H*e2011-12-14 08:12

54 楼

This is not inorder traversal

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

: what I did is inorder traverse and then compared the two sorted array.

c*e2011-12-14 08:12

55 楼

Why? Do not understand it.

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

: This is not inorder traversal

l*a2011-12-14 08:12

56 楼

are there duplicate in binary tree?

【在 b*********3 的大作中提到】

: a)遍历第一棵树，建一个hashtable，每个数字对应出现次数
: b)遍历第二棵树，递减hashtable里相应数字的出现次数。如果hashtable里没有，就返
: 回false。当一个数字出现次数为0就remove。最后如果hashtable空，就表示一样。

s*52011-12-14 08:12

57 楼

最后一道题也问我了，就是in-order写两个数组，然后比一遍。
对方夸我code is clear, easy to follow, 反而对是否最优化space不是很care