m家面经+求分析# JobHunting - 待字闺中
t*e
1 楼
很幸运，全程没有遇到一个烙印，上周二onsite,现在还没回复，求分析。 fresh
phd, 手头有些offer.没有签任何协定，说题目应该没问题吧。。
Update: Onsite居然拖了一周回复，磕磕盼盼总算拿下了，具体package还没谈
——————————————————————————————————————
0.店面：台湾人 rsde还是applied researcher来着
0a. 一个数组里面找中位数， 复杂度
0b. 如果有m台机器，每个机器有n个数据，怎么找nm个数据的中位数，复杂度
就是个quickselect, 后面一问没怎么答好，我居然想到的是每台机器先排序，再找中
位数。。。
应该是答得很不好，在店面后两周才通知onsite.....还以为挂了呢
——————————————————————————————————————
上周2 onsite, 9:30am开始，先跟hr小聊了一下，然后等10:30的lunch interview
1. 老美，典型geek, 97年就到西雅图上班了，级别不知。 先做题目再到公司cafe吃饭
，吃饭时看窗外，从来不知怎么开始话题，基本我说一句他答一句，典型的不会聊天，
目测泡妞都困难。
1a. 给定一组区间,找重叠的区间。。
1b. 设计一个储存任意树的方法，要求在disk上空间最小，而且当重建这个数
时所需内存最少
1a很简单， 1b就是按照dfs遍历，每个节点储存给节点的子链接个数。这样存储额
外需要O(n)空间， 重建需要o(log n)内存。 一开始我用bfs遍历，但重建就需要o(n
）内存，在提示下答出dst, 不需要写production code,意思意思就行
2. 老中，目测senior/principal级别。 前面半小时问我research的东西，不得不说他
真的不懂我的东西，还爱乱提意见，还一上来就说我的做法不对。。。。。别人phd课
题经过多少peer review了,没想清楚就乱提意见不怕打脸么。。。 后来问一个非典型
题目，比求直方图最大面积还难的那种，没见过，给了个解法，然后说我那个是非最优
解。你妹半小时这题我能给最优解就神了。
3. 老白，名字像罗刹国人。
3a. 先一个智力题，有r,g,b三个宝石，放在三个盒子里面。盒子上分别贴有非r
,非g,非b, 问怎么知道盒子里面放的是什么。 我直接说我智商低，最怕这种题目。就
随便开一个盒子看看呗，问我能不能不开盒子看， 我就把所有组合排列一遍说不能，
他反问你确定吗。 我听了一慌，不得不重新再排列一遍，再答不能。
3b. 把二叉树每层节点连接起来，节点有个next指针。 我给了个用queue的解法
。他问能不能不用queue,不迭代的解法。我说我尽力， 捣鼓了半天说了个大概解法。
后来时间到了，我该走了， 只留下了满黑板潦草的不能编译的有错的代码，
4. 见了传说中的老板， principal级别, 先大谈自己的team，聊天，一起骂google,
骂amazon（我先违心主动骂，他附和）。做题
4a. a1a2a3b1b2b3 给成 a1b1a2b2a3b3 写code,潦草写完说我看到你个bug, 要求不
能给bug， 看到一个bug扣一分，吓得我全部擦掉重写，最后还是有个bug.....
4b. 实现memmove(*a,*b,length), 把a数组的内容移动到b数组，b指针在任意位置
4c. BFS的一个应用。
然后带我到一个地方， 让我休息一个小时，再跟他老板谈。赶紧到他家冰柜里喝免费
饮料，因为带了书包，还偷偷藏了两瓶带走。屌丝本质啊。。。
5. 老板的老板， linkedin上发现是个partner, 先做题再聊天。 先让我画个二叉树，
问我preorder什么样的，in order什么样的，然后让我根据这两个数列重建树，还问我
做过没？我违心的回答没做过，但做过In order重建bst。 然后飙演技了。 做完后觉
得挺满意就跟我谈笑风生，讲述他当年失足博士后的心路历程，鼓励我不要往火坑里跳
，最后我们就nosql等热点问题交换了意见，时间到走人。
出来后一阵倒车才见到美丽的hr美眉，恍如隔世，时间已经6:00pm了,真是漫长的一天.
she says she will call，可惜到现在还没有
phd, 手头有些offer.没有签任何协定，说题目应该没问题吧。。
Update: Onsite居然拖了一周回复，磕磕盼盼总算拿下了，具体package还没谈
——————————————————————————————————————
0.店面：台湾人 rsde还是applied researcher来着
0a. 一个数组里面找中位数， 复杂度
0b. 如果有m台机器，每个机器有n个数据，怎么找nm个数据的中位数，复杂度
就是个quickselect, 后面一问没怎么答好，我居然想到的是每台机器先排序，再找中
位数。。。
应该是答得很不好，在店面后两周才通知onsite.....还以为挂了呢
——————————————————————————————————————
上周2 onsite, 9:30am开始，先跟hr小聊了一下，然后等10:30的lunch interview
1. 老美，典型geek, 97年就到西雅图上班了，级别不知。 先做题目再到公司cafe吃饭
，吃饭时看窗外，从来不知怎么开始话题，基本我说一句他答一句，典型的不会聊天，
目测泡妞都困难。
1a. 给定一组区间,找重叠的区间。。
1b. 设计一个储存任意树的方法，要求在disk上空间最小，而且当重建这个数
时所需内存最少
1a很简单， 1b就是按照dfs遍历，每个节点储存给节点的子链接个数。这样存储额
外需要O(n)空间， 重建需要o(log n)内存。 一开始我用bfs遍历，但重建就需要o(n
）内存，在提示下答出dst, 不需要写production code,意思意思就行
2. 老中，目测senior/principal级别。 前面半小时问我research的东西，不得不说他
真的不懂我的东西，还爱乱提意见，还一上来就说我的做法不对。。。。。别人phd课
题经过多少peer review了,没想清楚就乱提意见不怕打脸么。。。 后来问一个非典型
题目，比求直方图最大面积还难的那种，没见过，给了个解法，然后说我那个是非最优
解。你妹半小时这题我能给最优解就神了。
3. 老白，名字像罗刹国人。
3a. 先一个智力题，有r,g,b三个宝石，放在三个盒子里面。盒子上分别贴有非r
,非g,非b, 问怎么知道盒子里面放的是什么。 我直接说我智商低，最怕这种题目。就
随便开一个盒子看看呗，问我能不能不开盒子看， 我就把所有组合排列一遍说不能，
他反问你确定吗。 我听了一慌，不得不重新再排列一遍，再答不能。
3b. 把二叉树每层节点连接起来，节点有个next指针。 我给了个用queue的解法
。他问能不能不用queue,不迭代的解法。我说我尽力， 捣鼓了半天说了个大概解法。
后来时间到了，我该走了， 只留下了满黑板潦草的不能编译的有错的代码，
4. 见了传说中的老板， principal级别, 先大谈自己的team，聊天，一起骂google,
骂amazon（我先违心主动骂，他附和）。做题
4a. a1a2a3b1b2b3 给成 a1b1a2b2a3b3 写code,潦草写完说我看到你个bug, 要求不
能给bug， 看到一个bug扣一分，吓得我全部擦掉重写，最后还是有个bug.....
4b. 实现memmove(*a,*b,length), 把a数组的内容移动到b数组，b指针在任意位置
4c. BFS的一个应用。
然后带我到一个地方， 让我休息一个小时，再跟他老板谈。赶紧到他家冰柜里喝免费
饮料，因为带了书包，还偷偷藏了两瓶带走。屌丝本质啊。。。
5. 老板的老板， linkedin上发现是个partner, 先做题再聊天。 先让我画个二叉树，
问我preorder什么样的，in order什么样的，然后让我根据这两个数列重建树，还问我
做过没？我违心的回答没做过，但做过In order重建bst。 然后飙演技了。 做完后觉
得挺满意就跟我谈笑风生，讲述他当年失足博士后的心路历程，鼓励我不要往火坑里跳
，最后我们就nosql等热点问题交换了意见，时间到走人。
出来后一阵倒车才见到美丽的hr美眉，恍如隔世，时间已经6:00pm了,真是漫长的一天.
she says she will call，可惜到现在还没有
