报M家卧佛+onsite面经 - 未名空间MITBBS历史存档

b*s2012-11-26 08:11

1 楼

我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
的master的package。
onsite面经如下：
一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
behavior问题作为开场白。
被问到的算法题如下：
1. 一个string当中，求出现多于一次的最长的substring。
eg: "abcabcaacb" -> "abc"
eg: "aababa" -> "aba"
这题我没有想到最优解，代码也没有写完，也被面试官认可。
2. 整数乘法：multiply(int x, int y)
这题本身虽然简单，但是考虑所有情况bug-free还是不容易
3. 老题：reverse words in a sentence
4. string edit distance的递归解法，我以前只写过DP解法的，经提示写出递归解法
感想&建议：
1. 我被5个人面了8个小时，从早上9点到下午5点，包括45分钟午饭。面到下午的时候
体力严重透支，一共喝了4个中杯咖啡，午饭时候还喝了一瓶16oz的红牛。最后一轮
string edit distance白板题的时候我实在太累，跟面试官说能否给我多一点时间仔细
考虑一下，面试官很nice地给了我很多hint避免了我犯一些低级错误。面试全部结束的
时候，已经要瘫倒在地了。我强烈建议头一天晚上要休息好，如果需要倒时差的话，第
二天早上不要起得太早。
2. 从我的经历来看，他家onsite题算法不一定会很难，但是对考虑全面和bugfree有一
定要求。码完code之后最好自己检查一遍，尽量在面试官发现bug之前自己改过来。

C*y2012-11-26 08:11

2 楼

cong

b*m2012-11-26 08:11

3 楼

不错。恭喜！

h*n2012-11-26 08:11

4 楼

恭喜楼主！前几天刚跟你聊过，今天就有好消息了

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

j*62012-11-26 08:11

5 楼

恭喜LZ
第一题求解释，aababa中最多的substring不是a吗？有4次呢

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

b*s2012-11-26 08:11

6 楼

不好意思，刚才我把题目写错了，已经改过来了。应该是“一个string当中，求出现多
于一次的最长的substring。”

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

: 恭喜LZ
: 第一题求解释，aababa中最多的substring不是a吗？有4次呢

b*s2012-11-26 08:11

7 楼

哈哈，多谢，也祝你面试好运！！

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

: 恭喜楼主！前几天刚跟你聊过，今天就有好消息了

l*a2012-11-26 08:11

8 楼

130K的offer ah
M里很多干了４－５年的phd都没你挣的多

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

C*y2012-11-26 08:11

9 楼

这些PhD为啥年薪这么低？

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

: 130K的offer ah
: M里很多干了４－５年的phd都没你挣的多

l*a2012-11-26 08:11

10 楼

因为他们去的早，８－９万起薪，然后一点一点涨
还没有这么多sign-on
make sense?

【在 C****y 的大作中提到】

: 这些PhD为啥年薪这么低？

g*e2012-11-26 08:11

11 楼

aababa 为啥是aba? 如果字符可以算重复的，为啥不是abab?

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

: 不好意思，刚才我把题目写错了，已经改过来了。应该是“一个string当中，求出现多
: 于一次的最长的substring。”

C*y2012-11-26 08:11

12 楼

他们的现在，就是我们的未来？
看来过几年，我们的年薪，也会低于刚入职的新人了？
M家每年涨薪能有多少啊

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

: 因为他们去的早，８－９万起薪，然后一点一点涨
: 还没有这么多sign-on
: make sense?

t*h2012-11-26 08:11

13 楼

for first Q:
for each char:
find all its occurrence.
expand it to its righthand side and and if <=1 instance left, stop
result: return the longest which appears more than once?

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

h*62012-11-26 08:11

14 楼

Cong
lz的offer里有没有一笔5k的acceptance fee（不是5k的sign-on）?

f*e2012-11-26 08:11

15 楼

你是搞生物的吗？第一题可以用suffix tree做吗？

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

b*s2012-11-26 08:11

16 楼

"aababa"中substring必须出现多于一次，"aba"和“ab”都出现了2次，所以结果是“
aba”。

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

: aababa 为啥是aba? 如果字符可以算重复的，为啥不是abab?

p*22012-11-26 08:11

17 楼

eg: "abcabcaacb"中"abc" -> 2次
这个最多的不应该是"a"吗？

f*e2012-11-26 08:11

18 楼

最长重复字串，建suffix tree的时候，最长重复字串就是增长点的起始点。

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

: eg: "abcabcaacb"中"abc" -> 2次
: 这个最多的不应该是"a"吗？

r*m2012-11-26 08:11

19 楼

一般来说，5k的acceptance fee就是大家俗称的signon,这个是人人有的default的，如
果你还有一笔，那就是额外给你的，它们叫on-hire bonus,这个因人而异

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

: Cong
: lz的offer里有没有一笔5k的acceptance fee（不是5k的sign-on）?

h*62012-11-26 08:11

20 楼

终于解惑了，谢谢彩虹mm！

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

:
: 一般来说，5k的acceptance fee就是大家俗称的signon,这个是人人有的default的，如
: 果你还有一笔，那就是额外给你的，它们叫on-hire bonus,这个因人而异

p*22012-11-26 08:11

21 楼

感觉第一题trie应该是最优吧。

g*r2012-11-26 08:11

22 楼

这个整数乘法的啥意思？用位运算实现吗？

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

y*n2012-11-26 08:11

23 楼

eg: "abcabcaacb" -> "abc"
why not "abca" ? It appeared twice too.

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

T*s2012-11-26 08:11

24 楼

cong~~~

r*e2012-11-26 08:11

25 楼

8小时，5轮，只有4个算法题？还是说，只有4道要求白板？LZ还面了什么只说思路的算
法题了么？

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

l*i2012-11-26 08:11

26 楼

suffix array, look for longest comment prefix.

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

: 我是fresh cs master，一周前面的M家，今天收到口头offer，应该算是标准
: 的master的package。
: onsite面经如下：
: 一共5轮见了3个engineer2个dev manager，每一轮都有一道白板code题，其中有3轮都
: 被详细的问到简历上的project经历和若干followup问题，其中有一个人问了我几个
: behavior问题作为开场白。
: 被问到的算法题如下：
: 1. 一个string当中，求出现多于一次的最长的substring。
: eg: "abcabcaacb" -> "abc"
: eg: "aababa" -> "aba"

l*a2012-11-26 08:11

27 楼

int minDistance(string a, string b){
if(a.length() == 0){
return b.length();
}
if(b.length() == 0){
return a.length();
}
if(a[0] == b[0]){
return minDistance(a.substr(1), b.substr(1));
}else{
return min(minDistance(a.substr(1), b), min(minDistance(a, b.substr(
1)), minDistance(a.substr(1), b.substr(1)))) + 1;
}
}

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

: "aababa"中substring必须出现多于一次，"aba"和“ab”都出现了2次，所以结果是“
: aba”。