有没有修爆浆电容的？ - 未名空间MITBBS历史存档

z*s2014-03-18 07:03

1 楼

在网上申请的SDE职位。一共两轮电话面试，一轮onsite。
第一轮电话面试：
1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
good hash function”，“什么是load factor”。
2、算法：删除一个给定数列中重复的元素。
3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
，让我写好以后发到他邮箱里。
4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。
第二轮电话面试：
1、Favorite project。
2、你最喜欢的排序算法，它是怎么工作的，有什么优点和缺点。我说的是选择排序，
他又问有什么排序算法比它的时间复杂度小，并且同样要描述一下它们是怎么工作的。
3、算法、写代码：
给了两个数组，要求找出他们之中相同的元素，并且将相同的元素存储在一个新的数组
里，再输出。如果数组里有重复的元素，比如array1中有四个5，array2中有两个5，那
么新数组里只存储两个5。要求我写代码，再念给他听。
4、OOD：设计restaurant reservation系统。
5、好像是一个开放性问题，我没有完全理解：log file中存储了很多order的信息，每
个order都有一个oid，字符串格式（xxx-xxxxxxx-xxxxxxx）。要求从log file中把所
有的oid都提取出来，问我怎么做。
on-site：
一、给定一篇文章，用户想要搜索一个单词，要求给出搜索单词的建议（就像一般的搜
索引擎的那种功能）。要求描述算法、复杂度并写代码。
二、先问了几个行为问题。然后问了两个简单的链表问题，单链表中查找倒数第n个数
和判断链表中是否有环。编程题问的是boggle游戏的问题：给定一个4*4的矩阵，每个
位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
http://en.wikipedia.org/wiki/Boggle
三、午餐，一个经理问了一些简历上的projects和实习的经历，然后又介绍了一下他们
组的工作。他说这次面试我的主要是Kindle组的。
四、不是Kindle组的，我估计是传说中的bar raiser。第一个问题是给了一个很大的文
件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
复。然后是一个开放性问题：一台服务器每过三天就要挂一次，需要重启才能再次使用
，每次重启需要一分钟的时间；问有什么方法能解决这个问题。
五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
商。

B*g2014-03-18 07:03

2 楼

我没去刺激他们

s*h2014-03-18 07:03

3 楼

最受领导喜欢的排行榜top5
一、白浅。家世好，能力强，人又很幽默，关键是没架子，很好相处，美而不自知是美
人界的高境界，总之都是优点。但是最受领导欢迎的一大优点就是忠诚度高啊，司音对
于墨渊的忠诚七万年如一日，从可爱小萝莉一直追随到职场御姐，这样的员工，哪个领
导不喜欢？
二，夜华。勤奋、能力强。从小就努力学习，当上太子之后就开始处理政务，有战事的
时候就能出战，一出战就能马到成功。关键的一点是，他没野心。尽管做了很多，但是
从来不觊觎天君的位子。这样的员工，哪个领导不喜欢？
三，凤九。虽然电视剧里凤九的人设最后崩了，但是最初的时候敢说敢做雷厉风行的小
凤九，为了报恩上天下地的追随着东华，这样的执行力多么难能可贵。
四，团子。团子可以说是助理界的一哥了，永远能跟领导想到一起，能急领导之所急，
想领导之所想，该出现的时候出现，不该出现的时候就消失，这样的神助攻选手，肯定
受领导喜欢啊。
五，折颜。几万年的研究酿酒和医术这两项。专业领域做到第一，虽然究竟他和墨渊谁
酿的酒更好喝这个问题有点难以判断，书上说墨渊更胜一筹。但是能做到酿酒天下第二
，医术天下第一，确实也是人才。
最不受领导喜欢的排行榜top5
一，素锦。能力不足，搞事挺多。没事传传八卦，搞些宫斗，这样的人不管是领导还是
同事都不会喜欢。
二，擎苍。时时刻刻想着造反，不管能力有多强，肯定不会领导喜欢啊。
三，天君。作为leader，能力不足，偏听偏信，关键时候还比较武断。
四，玄女。背叛，这一点不值得原谅，不会受职场欢迎。
五，缪清。不务正业，还排错队。
最近好迷，完全沉浸无法自拔，就想这么多了。欢迎补充。

L*d2014-03-18 07:03

4 楼

几年前买的一个Sans Digital 4 bay eSATA enclosure, 用着用着变成1 bay了，最后0
bay了，打开一看, 一排电容都爆浆了。出了保修期，奈何？

g*s2014-03-18 07:03

5 楼

2、你最喜欢的排序算法，它是怎么工作的，有什么优点和缺点。我说的是选择排序，
他又问有什么排
序算法比它的时间复杂度小，并且同样要描述一下它们是怎么工作的。
什么是选择排序？
5、好像是一个开放性问题，我没有完全理解：log file中存储了很多order的信息，每
个order
都有一个oid，字符串格式（xxx-xxxxxxx-xxxxxxx）。要求从log file中把所有的oid
都提取
出来，问我怎么做。
grep?

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

: 在网上申请的SDE职位。一共两轮电话面试，一轮onsite。
: 第一轮电话面试：
: 1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
: good hash function”，“什么是load factor”。
: 2、算法：删除一个给定数列中重复的元素。
: 3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
: ，让我写好以后发到他邮箱里。
: 4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
: vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
: 果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。

n*s2014-03-18 07:03

6 楼

http://www.mitbbs.com/article_t/EB23/31803013.html
你拿啥刺激烙印？烙印都靠老中eb2c安慰自己呢
还有比eb2c更窝囊的吗

【在 B*****g 的大作中提到】

: 我没去刺激他们

e*i2014-03-18 07:03

7 楼

Buy parts from ebay.
Very difficult to remove the bad ones. :P

s*t2014-03-18 07:03

8 楼

Thanks for sharing!
on site 第一轮，写个trie？
on site 第四轮，那个开放性问题如何回答呢，没有思路。

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

: 在网上申请的SDE职位。一共两轮电话面试，一轮onsite。
: 第一轮电话面试：
: 1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
: good hash function”，“什么是load factor”。
: 2、算法：删除一个给定数列中重复的元素。
: 3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
: ，让我写好以后发到他邮箱里。
: 4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
: vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
: 果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。

B*g2014-03-18 07:03

9 楼

没有比EB2I更窝囊的，没赶上这波，2020年都交不了485。

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

: http://www.mitbbs.com/article_t/EB23/31803013.html
: 你拿啥刺激烙印？烙印都靠老中eb2c安慰自己呢
: 还有比eb2c更窝囊的吗

a*o2014-03-18 07:03

10 楼

一排电容都爆浆说明设计有问题吧，不是电压不对就是散热不好。
山寨货经常设计很不讲究，基本也就能保证个短期使用。
自己找找容量差不多的电容焊上去。

M72014-03-18 07:03

11 楼

selection sort
grep不愧为Amazon的最爱问题。
两次电面都问OOD...不容易。

oid

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

: 2、你最喜欢的排序算法，它是怎么工作的，有什么优点和缺点。我说的是选择排序，
: 他又问有什么排
: 序算法比它的时间复杂度小，并且同样要描述一下它们是怎么工作的。
: 什么是选择排序？
: 5、好像是一个开放性问题，我没有完全理解：log file中存储了很多order的信息，每
: 个order
: 都有一个oid，字符串格式（xxx-xxxxxxx-xxxxxxx）。要求从log file中把所有的oid
: 都提取
: 出来，问我怎么做。
: grep?

o*a2014-03-18 07:03

12 楼

早点生孩子是王道。
估计孩子给办绿卡，比等EB2i要快。

【在 B*****g 的大作中提到】

: 没有比EB2I更窝囊的，没赶上这波，2020年都交不了485。

t*t2014-03-18 07:03

13 楼

当年，主板电容爆浆是常事，现在少见了。

后0

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

: 几年前买的一个Sans Digital 4 bay eSATA enclosure, 用着用着变成1 bay了，最后0
: bay了，打开一看, 一排电容都爆浆了。出了保修期，奈何？

g*s2014-03-18 07:03

14 楼

i've totally forgotten this one...

【在 M7 的大作中提到】

: selection sort
: grep不愧为Amazon的最爱问题。
: 两次电面都问OOD...不容易。
:
: oid

B*g2014-03-18 07:03

15 楼

哈哈

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

: 早点生孩子是王道。
: 估计孩子给办绿卡，比等EB2i要快。

a*o2014-03-18 07:03

16 楼

现在稍微加个块儿八毛就能升级成固体电容，无浆可爆，呵呵。

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

: 当年，主板电容爆浆是常事，现在少见了。
:
: 后0

R*i2014-03-18 07:03

17 楼

2、算法：删除一个给定数列中重复的元素。
这道题看起来简单但是还是很多陷阱啊。。。
比如删除是什么意思？只是把array element mark为一个不可能的值（比如-1），还是
输出一个崭新的没有重复的数列。

t*j2014-03-18 07:03

18 楼

以后财年没有新版的3012的通过，老印eb2只能被eb3i拖得很无路可走。

[发表自未名空间手机版 - m.mitbbs.com]

【在 B*****g 的大作中提到】

: 没有比EB2I更窝囊的，没赶上这波，2020年都交不了485。

y*i2014-03-18 07:03

19 楼

修比买新的怕是还贵吧。

g*s2014-03-18 07:03

20 楼

usually it means in-place remove.

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

: 2、算法：删除一个给定数列中重复的元素。
: 这道题看起来简单但是还是很多陷阱啊。。。
: 比如删除是什么意思？只是把array element mark为一个不可能的值（比如-1），还是
: 输出一个崭新的没有重复的数列。

a*d2014-03-18 07:03

21 楼

烙印一点也不窝囊，EB移民印度作为一个族裔，是最大的受益者。EB123被他
们搞了个遍。真正窝囊的是EB2C，上面够不着ROW，下边被烙印挤兑。

【在 B*****g 的大作中提到】

: 没有比EB2I更窝囊的，没赶上这波，2020年都交不了485。

g*s2014-03-18 07:03

22 楼

3、算法、写代码：
给了两个数组，要求找出他们之中相同的元素，并且将相同的元素存储在一个新的数组
里，再输出。
如果数组里有重复的元素，比如array1中有四个5，array2中有两个5，那么新数组里只
存储两个
5。要求我写代码，再念给他听。
this one also confusing. if array1 has 1 "5" and array2 has 1 "5" too.
then new array has 2 "5" or 1 "5"?
looks like it's trying to implement set union. but why allow the
duplicates...

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

: 在网上申请的SDE职位。一共两轮电话面试，一轮onsite。
: 第一轮电话面试：
: 1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
: good hash function”，“什么是load factor”。
: 2、算法：删除一个给定数列中重复的元素。
: 3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
: ，让我写好以后发到他邮箱里。
: 4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
: vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
: 果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。

B*g2014-03-18 07:03

23 楼

反对搞分裂，我们EB2C和EB1，3C，以及亲属移民，政治庇护，投资移民是一体的，欧
耶！

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

: 烙印一点也不窝囊，EB移民印度作为一个族裔，是最大的受益者。EB123被他
: 们搞了个遍。真正窝囊的是EB2C，上面够不着ROW，下边被烙印挤兑。

i*92014-03-18 07:03

24 楼

是啊，难道要写个 trie吗

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

: Thanks for sharing!
: on site 第一轮，写个trie？
: on site 第四轮，那个开放性问题如何回答呢，没有思路。

B*g2014-03-18 07:03

25 楼

反正和我一块的小印估计比我晚2年，另2个还没交485的140刚批，询问哪天能交485就
。虽然得知可能要等8年，但是人家心里是高兴的，因为EB13I都拿到了更多名额。要向
烙印学习呀，lol

【在 t***j 的大作中提到】

: 以后财年没有新版的3012的通过，老印eb2只能被eb3i拖得很无路可走。
:
: [发表自未名空间手机版 - m.mitbbs.com]

R*i2014-03-18 07:03

26 楼

请问array怎么实现in-place remove? duplicate的值的空格会被填掉，但array最后几
格还是
都是多出来的空格啊，最后直接return这个array的话也不对啊。。。真心求教

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

: usually it means in-place remove.

g*d2014-03-18 07:03

27 楼

烙印比我们更能吃苦啊，两家挤在一个房子里，有父母还各有两小孩，一样过的乐呵呵
的。聊起来，对印度的信心比我们对中国的信心不知道差哪里去了，所以destruction
可能老中比烙印贡献的还多。

【在 B*****g 的大作中提到】

: 反正和我一块的小印估计比我晚2年，另2个还没交485的140刚批，询问哪天能交485就
: 。虽然得知可能要等8年，但是人家心里是高兴的，因为EB13I都拿到了更多名额。要向
: 烙印学习呀，lol

g*s2014-03-18 07:03

28 楼

u can return the index of the ending element, like stl does.

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

:
: 请问array怎么实现in-place remove? duplicate的值的空格会被填掉，但array最后几
: 格还是
: 都是多出来的空格啊，最后直接return这个array的话也不对啊。。。真心求教

i*t2014-03-18 07:03

29 楼

老印的问题是印度很多地方实在跟美国差远了，就算10年排期他们也愿意来。
中国的毛病就是家里实在发展得太快了，还得眼红海龟板动不动就上百万的海龟的年薪
心理极度不平衡。
所以老印看上去乐观多了。

destruction

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

: 烙印比我们更能吃苦啊，两家挤在一个房子里，有父母还各有两小孩，一样过的乐呵呵
: 的。聊起来，对印度的信心比我们对中国的信心不知道差哪里去了，所以destruction
: 可能老中比烙印贡献的还多。

R*i2014-03-18 07:03

30 楼

o...知道了。。。我一直用java，没有stl的概念，多谢

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

: u can return the index of the ending element, like stl does.

t*j2014-03-18 07:03

31 楼

其实去年抽风的排期老印老中才能真正抢到点名额，从row哪里，现在这样p都没有。
老中没水喝，老印也是没有的。

[发表自未名空间手机版 - m.mitbbs.com]

【在 B*****g 的大作中提到】

: 反正和我一块的小印估计比我晚2年，另2个还没交485的140刚批，询问哪天能交485就
: 。虽然得知可能要等8年，但是人家心里是高兴的，因为EB13I都拿到了更多名额。要向
: 烙印学习呀，lol

f*g2014-03-18 07:03

32 楼

4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。
麻烦楼主说说你怎么答得，谢谢

g*d2014-03-18 07:03

33 楼

他们等得起十年，我们这里有几个等得起那么久的？所以最后觉得渴的还是我们？

【在 t***j 的大作中提到】

: 其实去年抽风的排期老印老中才能真正抢到点名额，从row哪里，现在这样p都没有。
: 老中没水喝，老印也是没有的。
:
: [发表自未名空间手机版 - m.mitbbs.com]

l*o2014-03-18 07:03

34 楼

int removeDuplicateInt(int A[], int n)
return the new element number.

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

: 2、算法：删除一个给定数列中重复的元素。
: 这道题看起来简单但是还是很多陷阱啊。。。
: 比如删除是什么意思？只是把array element mark为一个不可能的值（比如-1），还是
: 输出一个崭新的没有重复的数列。

t*j2014-03-18 07:03

35 楼

老中不需要等10年，3-5年而已，老印也不一定等得起10年，09年被轰回去的老印也很
多的。
07的大潮真的是救了很多人，特别是eb3的老印。
不过eb3i后面的不一定有这个luck了。

[发表自未名空间手机版 - m.mitbbs.com]

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

: 他们等得起十年，我们这里有几个等得起那么久的？所以最后觉得渴的还是我们？

h*d2014-03-18 07:03

36 楼

谢谢楼主分享~ 祝福一下
那个服务器老挂那题，怎么回答？
还有这题，用hashmap?
第一个问题是给了一个很大的文
件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
复。

t*j2014-03-18 07:03

37 楼

14万的名额从1990年到现在，其实名额不增加的话，队伍只会越来越长
[发表自未名空间手机版 - m.mitbbs.com]

d*t2014-03-18 07:03

38 楼

我觉得应该用类似histogram的作法，累计每一个整数出现的次数。

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

: 谢谢楼主分享~ 祝福一下
: 那个服务器老挂那题，怎么回答？
: 还有这题，用hashmap?
: 第一个问题是给了一个很大的文
: 件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
: 复。

g*s2014-03-18 07:03

39 楼

i doubt hash would work. it requires O(N) space while the file itself is
too big to fit in mem.

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

: 谢谢楼主分享~ 祝福一下
: 那个服务器老挂那题，怎么回答？
: 还有这题，用hashmap?
: 第一个问题是给了一个很大的文
: 件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
: 复。

z*s2014-03-18 07:03

40 楼

对，是in place remove。

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

: usually it means in-place remove.

z*s2014-03-18 07:03

41 楼

如果array1有一个5，array2也有一个5，新的数组应该只有一个5。应该是取同一数字
的个数较小的那个。

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

: 3、算法、写代码：
: 给了两个数组，要求找出他们之中相同的元素，并且将相同的元素存储在一个新的数组
: 里，再输出。
: 如果数组里有重复的元素，比如array1中有四个5，array2中有两个5，那么新数组里只
: 存储两个
: 5。要求我写代码，再念给他听。
: this one also confusing. if array1 has 1 "5" and array2 has 1 "5" too.
: then new array has 2 "5" or 1 "5"?
: looks like it's trying to implement set union. but why allow the
: duplicates...

h*d2014-03-18 07:03

42 楼

详细讲讲？和hashtable不同吗

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

: 我觉得应该用类似histogram的作法，累计每一个整数出现的次数。

z*s2014-03-18 07:03

43 楼

服务器那个题我答的不好，因为老是不知道他在问什么，他想要的答案是什么。反正他
给了我很多提示，比如可以用交替使用两台机器，还需要一个load balancer，这样可
以在一台服务器挂的时候正好用上另一台正常工作的服务器，再重启挂的这个机器。
文件找重复的那道题我觉得可以用hashtable，也可以external sorting。hashtable有
个问题是如果内存中放不下这个哈希表的话怎么办？我说可以使用多台机器，每台存放
一定范围内的数字（类似于MapReduce中map的过程），然后再分别对每个机器处理。

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

: 谢谢楼主分享~ 祝福一下
: 那个服务器老挂那题，怎么回答？
: 还有这题，用hashmap?
: 第一个问题是给了一个很大的文
: 件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
: 复。

z*s2014-03-18 07:03

44 楼

很惭愧，我对OOD非常不熟悉。我说的是定义car类，user类和rental类，其中一个
rental对象表示一个租车的交易，要记录用户和车的信息。如果要向用户发送提醒邮件
的话，我说可以定义一个链表，或者直接用一个数组，数组中的每一项是一条租车记录
，它们是按交车时间从早到晚排序的；然后根据当前时间向这个表中的靠前的几条记录
的用户发送提醒邮件。

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

: 4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
: vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
: 果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。
: 麻烦楼主说说你怎么答得，谢谢

d*t2014-03-18 07:03

45 楼

我说说看哦，我非CS专业，不晓得hashtable是啥，不对的话见笑。
建一个数组vector count，够大，所有的entry都清零。
然后开始读那个文件，读到任意一个整数，假设为i，就在count的第i个位置加一：
count[i]++;
直到把文件读完，如果这个文件里没有重复出现的数，那么count里的值要么是零要么
是一，如果有大于一的值，说明这个值出现了不止一次。

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

: 详细讲讲？和hashtable不同吗

g*s2014-03-18 07:03

46 楼

this is called direct addressing. impractical as u have to assume the
input is in a range.

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

: 我说说看哦，我非CS专业，不晓得hashtable是啥，不对的话见笑。
: 建一个数组vector count，够大，所有的entry都清零。
: 然后开始读那个文件，读到任意一个整数，假设为i，就在count的第i个位置加一：
: count[i]++;
: 直到把文件读完，如果这个文件里没有重复出现的数，那么count里的值要么是零要么
: 是一，如果有大于一的值，说明这个值出现了不止一次。

g*s2014-03-18 07:03

47 楼

it's a weird problem. i can't figure out any real scenario we need such
kind of union.

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

: 如果array1有一个5，array2也有一个5，新的数组应该只有一个5。应该是取同一数字
: 的个数较小的那个。

d*t2014-03-18 07:03

48 楼

哦那能不能请教一下hashtable是怎么做的

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

: this is called direct addressing. impractical as u have to assume the
: input is in a range.

f*g2014-03-18 07:03

49 楼

是一个方法，不过很显然，这题的初衷并不是让用hashtable，毕竟是bar raiser嘛。
面试官可以说是int 64或者改变为其他类型。
这种题大概有几种方式
bloom filter (会有误差)
external sort
bucket分组
map reduce

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

: 我说说看哦，我非CS专业，不晓得hashtable是啥，不对的话见笑。
: 建一个数组vector count，够大，所有的entry都清零。
: 然后开始读那个文件，读到任意一个整数，假设为i，就在count的第i个位置加一：
: count[i]++;
: 直到把文件读完，如果这个文件里没有重复出现的数，那么count里的值要么是零要么
: 是一，如果有大于一的值，说明这个值出现了不止一次。

f*g2014-03-18 07:03

50 楼

已经不错了。
这种预定类型的，大概都是这么个结构吧
那二面中的OOD，其实也差不多了，对吗？
不过，那几个要求有点绕，比如search car 什么的。
并祝楼主拿到Offer

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

: 很惭愧，我对OOD非常不熟悉。我说的是定义car类，user类和rental类，其中一个
: rental对象表示一个租车的交易，要记录用户和车的信息。如果要向用户发送提醒邮件
: 的话，我说可以定义一个链表，或者直接用一个数组，数组中的每一项是一条租车记录
: ，它们是按交车时间从早到晚排序的；然后根据当前时间向这个表中的靠前的几条记录
: 的用户发送提醒邮件。

h*d2014-03-18 07:03

51 楼

我以为是让你查挂掉的原因，这种题是不大好答，没这种经验
我也是想每台机寸不同范围的数字，每次多一步比较一下属于哪个范围

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

: 服务器那个题我答的不好，因为老是不知道他在问什么，他想要的答案是什么。反正他
: 给了我很多提示，比如可以用交替使用两台机器，还需要一个load balancer，这样可
: 以在一台服务器挂的时候正好用上另一台正常工作的服务器，再重启挂的这个机器。
: 文件找重复的那道题我觉得可以用hashtable，也可以external sorting。hashtable有
: 个问题是如果内存中放不下这个哈希表的话怎么办？我说可以使用多台机器，每台存放
: 一定范围内的数字（类似于MapReduce中map的过程），然后再分别对每个机器处理。

h*d2014-03-18 07:03

52 楼

我只是猜，虽然文件大，但说不定只有3个数值呢... O_O

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

: it's a weird problem. i can't figure out any real scenario we need such
: kind of union.

z*s2014-03-18 07:03

53 楼

我一开始也是说查原因，比如说将当时的系统信息和寄存器的状态打印到一个日志什么
的，但是他反问我如果查了半年都不知道是什么错误怎么办，直接否定了这个方法。

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

: 我以为是让你查挂掉的原因，这种题是不大好答，没这种经验
: 我也是想每台机寸不同范围的数字，每次多一步比较一下属于哪个范围

p*a2014-03-18 07:03

54 楼

如果不是查原因，可不可以找个server最不忙的时段定时重启，或者搞个load
balancing之类的。

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

: 我一开始也是说查原因，比如说将当时的系统信息和寄存器的状态打印到一个日志什么
: 的，但是他反问我如果查了半年都不知道是什么错误怎么办，直接否定了这个方法。

E*R2014-03-18 07:03

55 楼

第一个问题是给了一个很大的文
件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
复。
这个可以用bitmap，10^7个整数之需要1.25M内存就可以了。这是Programming Pearls
第一章的例题。

c*m2014-03-18 07:03

56 楼

LZ店面的题目大部分都很经典啊，看来是OOD打得很好，要不那个amazon经典的grep没
答好都给onsite了。
onsite第一题有没有什么快捷的方法？我想的是根据文章build一个trie，然后用户边
输边遍历子树输出所有可能。当然这个是不考虑最优编码了（word frequency做加权的
）。
虽然trie的build和search比较straightforward，但是写code细节比较多，不知道他家
当时是要求你全写出来了？还是部分coding？

z*s2014-03-18 07:03

57 楼

假设trie已经建立好了，只用写出字符串搜索和匹配的代码。这部分代码我但是也没写
完，因为时间不够了。这道题确实很经典，可惜平时缺少相应的练习。

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

: LZ店面的题目大部分都很经典啊，看来是OOD打得很好，要不那个amazon经典的grep没
: 答好都给onsite了。
: onsite第一题有没有什么快捷的方法？我想的是根据文章build一个trie，然后用户边
: 输边遍历子树输出所有可能。当然这个是不考虑最优编码了（word frequency做加权的
: ）。
: 虽然trie的build和search比较straightforward，但是写code细节比较多，不知道他家
: 当时是要求你全写出来了？还是部分coding？

i*92014-03-18 07:03

58 楼

这个是从每个node都dfs一遍整个 matrix，然后删除重复吗?

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

: 在网上申请的SDE职位。一共两轮电话面试，一轮onsite。
: 第一轮电话面试：
: 1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
: good hash function”，“什么是load factor”。
: 2、算法：删除一个给定数列中重复的元素。
: 3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
: ，让我写好以后发到他邮箱里。
: 4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
: vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
: 果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。

y*m2014-03-18 07:03

59 楼

可以么？

在网上申请的SDE职位。一共两轮电话面试，一轮onsite。
第一轮电话面试：
1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
good hash function”，“什么是load factor”。
2、算法：删除一个给定数列中重复的元素。
hashmap 记录，++，删除 2的
3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
，让我写好以后发到他邮箱里。
k=i+j
a[i],b[j],c[k]
int ii=jj=kk=0;
while(kkif(a[ii]>b[jj]){
c[kk]=b[jj];
jj++;
} else {
c[kk]=a[ii];
ii++;
}
kk++;
}
4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。
abstract calss car
calss BMW extends car
calss Honda extends car
....
interface CarManager
class CarManagerImpl {
List T search(Class clazz){

}
T search(Class clazz){

}

}
class User {
List usercarList;
User();

boolean Rent(T entry){
usercarList.add
}
}
class UserCar {
List usercarList;

}
class Monitor implement Runnable {
public boolean doMonitor{
List usercarList = UserCar.getUsercarList(String
condition)
for(User user : usercarList){
sendEmail(getUser().getEmail());
}
}
第二轮电话面试：
1、Favorite project。
2、你最喜欢的排序算法，它是怎么工作的，有什么优点和缺点。我说的是选择排序，
他又问有什么排序算法比它的时间复杂度小，并且同样要描述一下它们是怎么工作的。
3、算法、写代码：
给了两个数组，要求找出他们之中相同的元素，并且将相同的元素存储在一个新的数组
里，再输出。如果数组里有重复的元素，比如array1中有四个5，array2中有两个5，那
么新数组里只存储两个5。要求我写代码，再念给他听。
4、OOD：设计restaurant reservation系统。
5、好像是一个开放性问题，我没有完全理解：log file中存储了很多order的信息，每
个order都有一个oid，字符串格式（xxx-xxxxxxx-xxxxxxx）。要求从log file中把所
有的oid都提取出来，问我怎么做。
on-site：
一、给定一篇文章，用户想要搜索一个单词，要求给出搜索单词的建议（就像一般的搜
索引擎的那种功能）。要求描述算法、复杂度并写代码。
二、先问了几个行为问题。然后问了两个简单的链表问题，单链表中查找倒数第n个数
和判断链表中是否有环。编程题问的是boggle游戏的问题：给定一个4*4的矩阵，每个
位置有一个字母，可以从一个位置跳转到周围八个相邻位置中的任何一个，但不能跳到
已经访问过的位置，要求找出所有的单词（假设给定了一个词典）。
http://en.wikipedia.org/wiki/Boggle
三、午餐，一个经理问了一些简历上的projects和实习的经历，然后又介绍了一下他们
组的工作。他说这次面试我的主要是Kindle组的。
四、不是Kindle组的，我估计是传说中的bar raiser。第一个问题是给了一个很大的文
件（不能完全放入内存），其中每一行存一个整数，要求判断这个文件中的数有没有重
复。然后是一个开放性问题：一台服务器每过三天就要挂一次，需要重启才能再次使用
，每次重启需要一分钟的时间；问有什么方法能解决这个问题。
五、实现一个整数除法的函数，不使用除号，可以使用加号、减号和乘号，函数只返回
商。

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

: 在网上申请的SDE职位。一共两轮电话面试，一轮onsite。
: 第一轮电话面试：
: 1、解释Hash Table，包括“可以用什么数据结构实现hash table”，“what is a
: good hash function”，“什么是load factor”。
: 2、算法：删除一个给定数列中重复的元素。
: 3、merge两个有序数组。要求先给他解释算法，再写代码。他当时给了我十分钟的时间
: ，让我写好以后发到他邮箱里。
: 4、OOD：设计一个汽车出租（Car Rental Agency）的系统。他先问我如果要实现
: vehicle search，需要哪些类；然后又问要实现rent a car，又需要哪些类；最后问如
: 果快到了交车截至时间，需要向用户发送提醒的邮件，应该怎么做。

T*g2014-03-18 07:03

60 楼

他是不是想问observer模式

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

: 很惭愧，我对OOD非常不熟悉。我说的是定义car类，user类和rental类，其中一个
: rental对象表示一个租车的交易，要记录用户和车的信息。如果要向用户发送提醒邮件
: 的话，我说可以定义一个链表，或者直接用一个数组，数组中的每一项是一条租车记录
: ，它们是按交车时间从早到晚排序的；然后根据当前时间向这个表中的靠前的几条记录
: 的用户发送提醒邮件。