Amazon电面面经（1面和2面） - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Amazon电面面经（1面和2面）

Amazon电面面经（1面和2面）# JobHunting - 待字闺中

Z*Z2010-05-28 07:05

1 楼

1面：
1、introduce yourself
2、why amazon
3、BST和Hashtable的比较，有什么区别
4、一个integer array，找sum为1给定值的pair（这个题有2种做法，sort和hashtable
，2个都提了一下，就跳过了）
5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
存，我用了个list，被指出这样影响复杂度。
2面：
1、一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。问
了3种解法。
解法1：XOR。问复杂度，O（N）
解法2：hashtable。问hashtable 的size。（N-1）/2+1。他说对，同时N/2+1也是对的
，为什么？答：因为N永远为奇数。
解法3：sorting，复杂度
2、详细比较ArrayList和LinkedList的实现，优缺点。
3、设计parking lot。（这个不是OOD问题）
3.1 只有1个valet，这个系统如

r*o2010-05-28 07:05

2 楼

多谢。想问两个问题:
1. 像字符串索引这样的题目什么时候用prefix tree好，什么时候用suffix tree好呢?
2. 一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。
为什么hashtable大小是(N-1)/2+1呢? 如果array里面的数可以任意，不局限于[1..n]
，这个hashtable的大小还是(N-1)/2+1吗？
[在 ZhangBZ (向日葵) 的大作中提到: 】
hashtable
array

h*k2010-05-28 07:05

3 楼

prefix 一定是要从头开始匹配，而suffix允许从字符串的任何一个位置开始匹配。
所以prefix相当于generalized suffix tree的边的一个子集。

呢?

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

: 多谢。想问两个问题:
: 1. 像字符串索引这样的题目什么时候用prefix tree好，什么时候用suffix tree好呢?
: 2. 一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。
: 为什么hashtable大小是(N-1)/2+1呢? 如果array里面的数可以任意，不局限于[1..n]
: ，这个hashtable的大小还是(N-1)/2+1吗？
: [在 ZhangBZ (向日葵) 的大作中提到: 】
: hashtable
: array

a*d2010-05-28 07:05

4 楼

I think the "upper limit" of the size of hashtable is N/2 +1.
Because duplicate keys appear exactly twice, when looking up, there is hit,
I can delete the item from hash.
Therefore, depends on the order of items, my hashtable could be smaller that
N/2 + 1.
Also depends on the hash function, not all slots may be used.

hashtable
array

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

: 1面：
: 1、introduce yourself
: 2、why amazon
: 3、BST和Hashtable的比较，有什么区别
: 4、一个integer array，找sum为1给定值的pair（这个题有2种做法，sort和hashtable
: ，2个都提了一下，就跳过了）
: 5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
: 小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
: 存，我用了个list，被指出这样影响复杂度。
: 2面：

r*o2010-05-28 07:05

5 楼

我觉得hash function的选择是一个问题。
如果这1到N个数是随机分布的话，怎么把这些数map到大小为N/2+1的hashtable里面去
呢？

,
that

【在 a*d 的大作中提到】

: I think the "upper limit" of the size of hashtable is N/2 +1.
: Because duplicate keys appear exactly twice, when looking up, there is hit,
: I can delete the item from hash.
: Therefore, depends on the order of items, my hashtable could be smaller that
: N/2 + 1.
: Also depends on the hash function, not all slots may be used.
:
: hashtable
: array

s*l2010-05-28 07:05

6 楼

5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
存，我用了个list，被指出这样影响复杂度。
请问一下
你这个prefix tree是对电话号码做的？
在这个tree的每个叶子上连着人名？

hashtable
array

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

s*i2010-05-28 07:05

7 楼

bless... 我觉得还是有希望的

Z*Z2010-05-28 07:05

8 楼

嗯，我的每个节点都有个data字段，只不过叶子上是人名，非叶子上是null

array

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

: 5、手机上给了电话号码求人名索引，提了hashtable，不满意，提示说手机上，空间很
: 小。又提prefix tree，满意，coding。犯了个小错误，每个树节点的孩子应该用array
: 存，我用了个list，被指出这样影响复杂度。
: 请问一下
: 你这个prefix tree是对电话号码做的？
: 在这个tree的每个叶子上连着人名？
:
: hashtable
: array

Z*Z2010-05-28 07:05

9 楼

借你吉言，现在还在等消息，呵呵

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

: bless... 我觉得还是有希望的

s*l2010-05-28 07:05

10 楼

你这data存的是到目前为止的数字？
如果定义root为0层那么
比如第三层的某个节点data存的是808
这样子？
“非叶子上是null”？
你这是说每个节点还有个char * ?

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

: 嗯，我的每个节点都有个data字段，只不过叶子上是人名，非叶子上是null
:
: array

s*l2010-05-28 07:05

11 楼

bless lz~ //刚才忘说了:P
你的parking lot的设计不就是ood嘛？

f*52010-05-28 07:05

12 楼

i want to confirm that whether the request of this issue is as below:
要求每输入一个数字，显示出所有可能的人名，
接着输入下一个，更新所有可能的人名。。

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

: 嗯，我的每个节点都有个data字段，只不过叶子上是人名，非叶子上是null
:
: array

f*52010-05-28 07:05

13 楼

关于你这个design题的回答，我看得还是很困惑的。。。
3.2 有多个valet，有什么最简单的优化方案？
关于什么的优化方案，关于空位search算法？

hashtable
array

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

z*n2010-05-28 07:05

14 楼

应该是打一个c，就输出所有名字c开头的record，打一个ca，就输出所有名字ca开头的
record，record里当然包括电话号码，换句话说，用人名做索引（key），这个跟真实手
机contact里的查找功能一样。
我关心的是它让你coding是写怎么建prefix树，还是建好了怎么用？

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

: i want to confirm that whether the request of this issue is as below:
: 要求每输入一个数字，显示出所有可能的人名，
: 接着输入下一个，更新所有可能的人名。。

Z*Z2010-05-28 07:05

15 楼

是这样的，每个节点有个char digit成员，还有个String data成员，digit存的是数字
，data存的是数据：）

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

: 你这data存的是到目前为止的数字？
: 如果定义root为0层那么
: 比如第三层的某个节点data存的是808
: 这样子？
: “非叶子上是null”？
: 你这是说每个节点还有个char * ?

Z*Z2010-05-28 07:05

16 楼

没有没有，要是这样的话，那个hashtable也不work吧。他就是想，给了个phone numbe
r，求人名

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

: i want to confirm that whether the request of this issue is as below:
: 要求每输入一个数字，显示出所有可能的人名，
: 接着输入下一个，更新所有可能的人名。。

Z*Z2010-05-28 07:05

17 楼

他要找的优化方案很简单，就是选最近的停车位。这样一个valet可以尽快的完成停车任
务，回到入口，服务下一个人。
至于空车位搜寻算法，在这个问题里不是重点。因为停车位是个常数，用brute force算
法也是常数时间。
btw：我遇到的这个parking lot问题看起来很open，说什么都可以。但是他有明确的想
要听的东西。

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

: 关于你这个design题的回答，我看得还是很困惑的。。。
: 3.2 有多个valet，有什么最简单的优化方案？
: 关于什么的优化方案，关于空位search算法？
:
: hashtable
: array

Z*Z2010-05-28 07:05

18 楼

两个函数，一个建树，一个查询，都写了。

实手

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

: 应该是打一个c，就输出所有名字c开头的record，打一个ca，就输出所有名字ca开头的
: record，record里当然包括电话号码，换句话说，用人名做索引（key），这个跟真实手
: 机contact里的查找功能一样。
: 我关心的是它让你coding是写怎么建prefix树，还是建好了怎么用？

w*12010-05-28 07:05

19 楼

建树好像挺复杂的, 有什么好的学习资源吗?

Z*Z2010-05-28 07:05

20 楼

强烈建议你自己练习一下。核心代码就是一个loop，6、7行就能搞定

【在 w*****1 的大作中提到】

: 建树好像挺复杂的, 有什么好的学习资源吗?

z*n2010-05-28 07:05

21 楼

实现trie的方法太多了，其实关键就是选什么结构表示trie的每个节点
比较常规的就是用个Node[]表示所有可能的children（如果key是小写字母string这个数
组大小就是26，如果key是数字串这个数组大小就是10).再用一个field表示这个这个节
点是不是表示了某个key的结束;还需要一个field存与key对应的value
节点的数据结构想好了，建树时候无非就是递归调用addNode函数，填好节点的每一个f
ield，就比较容易了，跟普通建树差不多

【在 w*****1 的大作中提到】

: 建树好像挺复杂的, 有什么好的学习资源吗?

y*c2010-05-28 07:05

22 楼

请给一个reference好么？那里可以找到这个核心代码，谢谢

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

: 强烈建议你自己练习一下。核心代码就是一个loop，6、7行就能搞定

h*62010-05-28 07:05

23 楼

电面考prefix tree啊，这种东西我只懂理论，从未实践，看来还是需要练习一下的了
。

c*f2010-05-28 07:05

24 楼

多谢分享！

Z*Z2010-05-28 07:05

25 楼

玩儿code jam的，这个是小case :D

【在 h**6 的大作中提到】

: 电面考prefix tree啊，这种东西我只懂理论，从未实践，看来还是需要练习一下的了
: 。