A家面经 - 未名空间MITBBS历史存档

n*r2013-02-23 08:02

1 楼

国内fresh master，英语不好，有时交流是个问题。
电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
面。
第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
近15分钟，面试官开始让我问问题，随便聊了聊。
第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有
些模糊。很艰难的交流着，不停让对方repeat，我都不好意思了。题是设计题，连蒙带
猜的做，最后也没写出个啥名堂，时间就到了。
第三面：HM，基本就聊天，research，project，然后behavior问题，比如why amazon
等～最后问了个查询的题：就讲了hash，hash函数，冲突处理等等都讲了，最后又讲了
内存不够如何处理等等。
第四面：这次倒好，没有问我project，几句之后开始编程，第一问是反转matrix，
CC150原题。给她讲了半天思路，在collabedit上描述真是又慢又痛苦，最后很快写完
程序。第二问是找一个given string的longest common substring：我用了后缀数组排
序后找longest common prefix。
第五面：HR，问了20分钟左右general的问题，第6个面试官就来了～
第六面：设计题，设计一个家具系统，要求能模拟比如加多少力，用多少时间一个塑料
椅子会坏；用火烧一个木桌子多少时间桌子会坏等等。没能很好的catch到他的point，
也做得不好。最后结束。
总的来说编程题都比较顺利，写完code也没说我有bug，但设计题都做得不好，交流也
比较不顺畅。
两天后如愿收到据信～feedback也不给。更悲剧的是，今天接到手机电信公司电话，说
我前几天打了很多国际长途，问我手机是不是被别人用了和我确认一下。我才知道原来
我打电话去建立连接也是收费的，780块～最终收费还要月底结帐才知道。当是一个教
训吧，自己想当然以为这种conference call是免费的。
最后，再求版上大牛内推Twitter，eBay，Yahoo，以及那些愿意从美国之外招人的
startup，感激不尽～

w*t2013-02-23 08:02

2 楼

多谢分享~
跟你情况类似，也是在国内准备找美国工作的。

x*02013-02-23 08:02

3 楼

mark

p*22013-02-23 08:02

4 楼

我用了后缀数组排
序后找longest common prefix。
这个时间复杂度多少呢？

n*r2013-02-23 08:02

5 楼

假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
(n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
(nmlg(n))～

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

: 我用了后缀数组排
: 序后找longest common prefix。
: 这个时间复杂度多少呢？

l*a2013-02-23 08:02

6 楼

why not use n instead of m?

nmlg
是O

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

: 假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
: (n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
: (nmlg(n))～

B*t2013-02-23 08:02

7 楼

找一个given string的longest common substring
是什么意思啊。。。就一个string怎么common

quick
call

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

: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有

l*a2013-02-23 08:02

8 楼

感觉是最long重复子串

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

: 找一个given string的longest common substring
: 是什么意思啊。。。就一个string怎么common
:
: quick
: call

p*p2013-02-23 08:02

9 楼

我记得这个是错的，但是一时想不出反例了

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

: 我用了后缀数组排
: 序后找longest common prefix。
: 这个时间复杂度多少呢？

P*b2013-02-23 08:02

10 楼

这个设计题比较恶心啊

quick
call

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

: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有

p*22013-02-23 08:02

11 楼

nmlg
是O
这样的话是不是不如trie好使？

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

: 假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
: (n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
: (nmlg(n))～

A*82013-02-23 08:02

12 楼

这跟买彩票有啥区别？老美应聘中国移动，你们要不？什么文化背景都不了解，就这样
找工作，阿三直接在印度找都比国人在国内找要容易些，别人交流没有问题，又是软
件大国，老美又招多少？

quick
call

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

: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有

p*22013-02-23 08:02

13 楼

不过感觉LZ水平还不错

【在 A*********8 的大作中提到】

: 这跟买彩票有啥区别？老美应聘中国移动，你们要不？什么文化背景都不了解，就这样
: 找工作，阿三直接在印度找都比国人在国内找要容易些，别人交流没有问题，又是软
: 件大国，老美又招多少？
:
: quick
: call

A*82013-02-23 08:02

14 楼

水平是次要的，你觉得一个懂中文的老美应聘电信，你觉得是他的专业水平重要？还是
文化交流重要？最关键的在工作中与同事的交流，做事风格，文化氛围，想的也太容易
啦，你想一个维族，或哈萨克族，汉语无任何交流，国内一本大学，软件编程水平中上
，比如去个重庆这种地方语言文化比较重的地方进当地名企工作，你要是总经理，或是
人事部的，你感觉怎么样？要吗？维族软件工程师，重庆华为想要不？搞研发。。。

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

:
: 不过感觉LZ水平还不错

p*22013-02-23 08:02

15 楼

你这话说的。

【在 A*********8 的大作中提到】

: 水平是次要的，你觉得一个懂中文的老美应聘电信，你觉得是他的专业水平重要？还是
: 文化交流重要？最关键的在工作中与同事的交流，做事风格，文化氛围，想的也太容易
: 啦，你想一个维族，或哈萨克族，汉语无任何交流，国内一本大学，软件编程水平中上
: ，比如去个重庆这种地方语言文化比较重的地方进当地名企工作，你要是总经理，或是
: 人事部的，你感觉怎么样？要吗？维族软件工程师，重庆华为想要不？搞研发。。。

A*82013-02-23 08:02

16 楼

想的太容易啦，文化语言的障碍，你们太小瞧了，连当年的所谓的“北大四君子”之一
的乌尔凯西，汉语那么好，英文也不错，为什么在台湾带着，怎么不在美国生活？好歹
汉语是他的半个母语。。。

quick
call

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

: 国内fresh master，英语不好，有时交流是个问题。
: 电面1：寒暄，聊project和reseach。接下来编程题是找数组中最大的k个数：用quick
: partition。写没费啥时间，讲思路耗费大部分时间～又聊了些别的结束。
: 两周后发邮件叫到西雅图onsite，但是几封邮件之后说嫌我远，改成conference call
: ，让我每次面试前拨通一个OCS的号码建立好连接等他们。好吧，那就相当于两天6个电
: 面。
: 第一面：先聊research和project。编程题是给两个链表，找出第一个链表中不在第二
: 个链表中的元素，不能有重复：用hash做。很快写完，接下来让写test cases。还有接
: 近15分钟，面试官开始让我问问题，随便聊了聊。
: 第二面：悲剧的开始。听不懂对方在说什么，一来英语不好，二来对方声音在电话里有

l*t2013-02-23 08:02

17 楼

除了民主他会啥

【在 A*********8 的大作中提到】

: 想的太容易啦，文化语言的障碍，你们太小瞧了，连当年的所谓的“北大四君子”之一
: 的乌尔凯西，汉语那么好，英文也不错，为什么在台湾带着，怎么不在美国生活？好歹
: 汉语是他的半个母语。。。
:
: quick
: call

d*x2013-02-23 08:02

18 楼

要是真会这个可以去教书啊，写书啊，只要不在大陆哪都能混

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

:
: 除了民主他会啥

g*n2013-02-23 08:02

19 楼

This uses O(n) space. trie 需要更多的空间.

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

:
: 你这话说的。

p*22013-02-23 08:02

20 楼

n是什么呀？

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

: This uses O(n) space. trie 需要更多的空间.

g*n2013-02-23 08:02

21 楼

n is length of the string

s*x2013-02-23 08:02

22 楼

Right. 这个应该是programming pearl 上的一道题，用一个长度为n 的指针数组分别
指到string 的每个字符的位置，这样就得到了 n 个substring, 然后 quick sort,
然后相近的两两比较。

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

: n is length of the string

p*22013-02-23 08:02

23 楼

quick sort (n^2logn)吧？

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

:
: Right. 这个应该是programming pearl 上的一道题，用一个长度为n 的指针数组分别
: 指到string 的每个字符的位置，这样就得到了 n 个substring, 然后 quick sort,
: 然后相近的两两比较。

d*x2013-02-23 08:02

24 楼

suffix array的标准做法 :)

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

:
: Right. 这个应该是programming pearl 上的一道题，用一个长度为n 的指针数组分别
: 指到string 的每个字符的位置，这样就得到了 n 个substring, 然后 quick sort,
: 然后相近的两两比较。

g*n2013-02-23 08:02

25 楼

Right. I think this is a space/time tradeoff. Trie uses more space but is
faster. Suffix array uses less space but is slower.

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

:
: quick sort (n^2logn)吧？

j*y2013-02-23 08:02

26 楼

trie (prefix tree) 不是用来处理多个 string 的 common prefix 用的吗？
这里是一个 string, 找这个string 里面重复出现的最长的 substring, 看不出来
如何使用 trie来解决这个问题阿

nmlg
是O
这样的话是不是不如trie好使

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

:
: quick sort (n^2logn)吧？

n*r2013-02-23 08:02

27 楼

嗯，就是这样的，相对于trie会更节省空间，时间复杂度为O(n^2lgn).

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

:
: Right. 这个应该是programming pearl 上的一道题，用一个长度为n 的指针数组分别
: 指到string 的每个字符的位置，这样就得到了 n 个substring, 然后 quick sort,
: 然后相近的两两比较。

n*r2013-02-23 08:02

28 楼

想起第一个设计题了，是说一个系统会不停接收query（每个query有一个唯一的ID，
query总数也不确定），然后run这个query得到一些结果并记录running time。不同
query可能会被运行很多次。要求系统在任意时刻能返回平均运行时间最快的5个query
和平均运行时间最慢的5个query。设计数据结构和算法～题大概可能就是这个意思，因
为当时交流起来真的很费劲。
当时说用hashmap来map query ID和一个pair，pair是query运行次数和当前平均运行时
间，这样每次更新很快，但是求最快的5个和最慢的5个比较费时，也想用最大堆和最小
堆，但每个query的平均运行时间是动态的～也不好弄。在纠结中时间就到了～

t*e2013-02-23 08:02

29 楼

现在有哪些公司可以直接从中国招人？

p*22013-02-23 08:02

30 楼

query
HashMap+TreeMap是不是就行了？

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

: 想起第一个设计题了，是说一个系统会不停接收query（每个query有一个唯一的ID，
: query总数也不确定），然后run这个query得到一些结果并记录running time。不同
: query可能会被运行很多次。要求系统在任意时刻能返回平均运行时间最快的5个query
: 和平均运行时间最慢的5个query。设计数据结构和算法～题大概可能就是这个意思，因
: 为当时交流起来真的很费劲。
: 当时说用hashmap来map query ID和一个pair，pair是query运行次数和当前平均运行时
: 间，这样每次更新很快，但是求最快的5个和最慢的5个比较费时，也想用最大堆和最小
: 堆，但每个query的平均运行时间是动态的～也不好弄。在纠结中时间就到了～

n*r2013-02-23 08:02

31 楼

TreeMap的key和vaule是什么呢？

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

:
: query
: HashMap+TreeMap是不是就行了？

n*r2013-02-23 08:02

32 楼

基本是大公司比如G，F，A愿意从国内直接招吧

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

: 现在有哪些公司可以直接从中国招人？

p*22013-02-23 08:02

33 楼

TreeSet就行了吧。key就是放query的信息，平均和次数。用平均做hash

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

:
: 基本是大公司比如G，F，A愿意从国内直接招吧

c*t2013-02-23 08:02

34 楼

把这个string看成2个，用dp解,i!=j 似乎容易很多, O(n^2)

nmlg
是O

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

: 假设这个string longest common substring的长度为m，则排序的时间复杂度是O(nmlg
: (n))。排好序后找最长prefix需要遍历数组两两挨着的找，时间为O(nm)。所以总的是O
: (nmlg(n))～

c*t2013-02-23 08:02

35 楼

二爷，一直没弄懂一件事情。
我知道treeset add,remove,search都是lg(n).但api里就是没提update. 比如当一个
query avg被update的时候，treeset是不是也能自动作排序调整？然后也是O(lgn)?
treemap一样问题。

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

:
: TreeSet就行了吧。key就是放query的信息，平均和次数。用平均做hash

p*22013-02-23 08:02

36 楼

不能要remove and add

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

: 二爷，一直没弄懂一件事情。
: 我知道treeset add,remove,search都是lg(n).但api里就是没提update. 比如当一个
: query avg被update的时候，treeset是不是也能自动作排序调整？然后也是O(lgn)?
: treemap一样问题。

a*n2013-02-23 08:02

37 楼

query那题可以用hash map结合max/min heap. hash map记录每个查询ID的平均时间，
每次来了一个query,更新hash map，并使用新的平均值更新max/min heap

j*y2013-02-23 08:02

38 楼

nice

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

: 把这个string看成2个，用dp解,i!=j 似乎容易很多, O(n^2)
:
: nmlg
: 是O

p*22013-02-23 08:02

39 楼

这个貌似时空最优吧。

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

: 把这个string看成2个，用dp解,i!=j 似乎容易很多, O(n^2)
:
: nmlg
: 是O

c*t2013-02-23 08:02

40 楼

多谢！

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

: 不能要remove and add