发信人: geniusxsy (小尾羊), 信区: JobHunting
标 题: [bssd]糖一下骑马找独角兽的过程
发信站: BBS 未名空间站 (Sun Feb 7 04:28:51 2016, 美东)
干货不多，大家有兴趣打发时间的话就看看吧。这贴也许对fresh grad没啥意义吧，对
experienced或许更有用些。
＊＊＊＊＊＊＊ 我是小广告的分割线 ＊＊＊＊＊＊＊＊＊＊
帮ld求好心朋友帮忙内推下三番或者中半岛的轻松养老型的马工职位，ld在某软某办公
软件里呆了若干年，现在才发现没有积累到什么流行的技术，现在想找工作背景上比较
吃亏。不过ld底子和学习能力都很好的。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
背景是在西雅图地区的G干了五年多主要做backend。最近一两年前，身边朋友纷纷跳槽
，现在比较后悔的就是，早知道两年前刚拿到卡就该挪一挪，拖到现在算有点晚了。另
外一方面，在G干的活，现在也越来越提不起兴趣。朋友的怂恿和激励下，去年10月终
于下决心要跳了。
==> take away: 要跳趁早，时机不等人。
当时也没想要跳湾区，差不多就是一心想去打车公司的西雅图分店。其实去年夏天就有
些蠢蠢欲动了，刷了几道题后懒了又不了了之。10月份开始认真刷lc，刷的也不快，到
12月才勉强刷一遍。后来回想，浪费很多时间，其实各个种类挑着做50~100道应该就差
不多了。然后花了很多时间精力去复习系统相关的知识。G家自己的用过的infra复习下
，spanner没用过，正好跟新project沾点边就看了个大概。有些东西像chubby, pubsub
用过但是内部完全不懂，趁这个机会也翻翻人家的design doc有点大致的了解。当然最
后我觉得也没有真正派上太大的用，不过做为知识积淀也挺好。然后就是市面上的技术
我是完全没接触过，起初还很担心，不过学了一圈下来也觉得没啥高大上的，大多能在
G里面找到类似的，而且比起G做的更简化。这些花的时候不必刷题少，而且design doc
/tech report/paper这些读起来可没有做题那么有趣。
==> take away: experienced hire，刷题到一定程度就够了，其他的知识积淀还是更
重要。
废话一堆之后，来聊聊面试经历吧。如果你是来找算法题，可能要失望了。忘了有没有
签nda，不过遇上很多国人interviewer，慎重起见我尽量模糊化具体的面试题。其实我
说了也没用，真的，更重要的东西其实是在交流上。
12月朋友催我说打车公司又要融了以后pay的越来越少要来赶快啊，我总觉得没准备充
分犹豫了一阵，月底才鼓起勇气让朋友递了简历。对拼趣一直也挺感兴趣，也让朋友帮
递了，不过说实话，当时也就是想试试而已。然后顺手找人帮投了个脸书家，想拿来练
手。听说facebook考刷题比较多，我自以为擅长做题。加上我背景里面social graph,
infra, product都沾点边，去面之前有种offer手到擒来的感觉。结果就悲剧了，怎么
说呢，也不算是被黑，发挥的也不好，有些很弱的失误回家路上就意识到了。算法题基
本上都是lc上的，有一道是hard但是那种非常经典大家都会做的，其他都是medium水平
的题，一共涉及了binary tree, stack, backtracking, prefix tree这些知识点。系
统题是让设计一个code search系统，基本上就是先装模作样分析估算下，然后画画大
的框架，反正差不多就是凭着经验和感觉走，然后接下来就是interviewer提问，对某
些component或者某些具体的情况zoom in进去讨论。虽然search我没做过，indexing系
统还是稍微接触过的，但是时间久了忘了不少，回家后又正好补了下知识。
==> take away: 面最心仪的公司前练练手也很有必要。
等脸书结果期间面了两轮u的店面，两轮都是很nice的中国人，跟第一位大哥中文聊天
也聊得非常愉快，coding题目也不难，用queue就能解决，大概也是放水吧。第二位系
统设计也是国人，问的google map，当时也没怎么准备过geospatial方面的话题，我觉
得磕磕碰碰的，结果还是承蒙面试官放水给过了。P家店面又是中国人，运气很好，问
了中等难度的lc题，就给水过了。不过有意思的是，这两家的coding都是online写完编
译调试，像我这样经常犯些typo或者弱智失误的，调试能力就可以弥补一些粗心，啪啪
啪的很快改完跑通，大概也给interviewer留下确实能干活的印象吧。不过坏处是如果
一两分钟没调出来，压力瞬间爆棚，只能扛着了。
==> take away: 其实大部分国人还是很nice的，遇上是缘分和运气！
这个时候fb悲剧的消息到了，感觉信心很受挫，情绪比较低落，本来觉得十拿九稳的事
情都黄了。其实现在想想悲剧是好事，让我带着卑微的心态努力尽力的准备之后的面试。
打车公司的onsite是在三番，虽然我申的职位是在西雅图。第一轮是老美mgr，名义是
考behavior，其实就是聊天，没有什么奇怪的问题。我准备的也比较充分，比较放松，
吹吹自己做项目的经历，侃侃对他家美好前景的向往，大家聊的也很愉快。第二轮是设
计题，他家的几道经典设计题目之一，设计netflix。还是先需求功能分析，然后画大
框架结构，然后主要问了下，serve media file怎么做到high available, high
throughput，这方面其实不太懂，这个时候就只有借助知识储备开始瞎扯，一会儿瞎扯
些分布文件系统的东西，一会儿又瞎扯些backup requests，parallel read等方案，然
后上面的caching层再扯几句。接着又继续问了recommendation系统，时间不多，只能
大致提了下user-based/item-base CF这些。其实几年前粗略的看过一些netflix做推荐
的资料，马马虎虎应付一下还凑合。总的感觉还是聊的比较愉快，交流上基本上还是比
较合拍。接下来一轮，我现在还有点摸不着头脑的感觉，很open的problem solving，
说是design但又不是system design，大概就是主题公园排队时提供fast track，比如
，交5块钱，告诉你一个小时后回来，有点像scheduling系统。最后还让写code简单模
拟一下。我稀里糊涂的都忘了怎么答的，感觉答的如何心里很没谱，最后居然也还是给
过了，也许是我东扯西扯一堆，擦着边击中了面试官心里想听的点子上？接下来一轮是
coding，简单的有点莫名其妙，其实后来听了不少别人的面经，U家问简单coding题似
乎是很正常的！不过然后不停的followup，如果这个是正式的code，unit test你怎么
写，让你自己做code review，有哪些你会改的，怎么refactor？感觉是在考察实际工
作中写码的能力，其实也make sense，毕竟工作里面是没有机会写太fancy的算法。不
过我觉得这样面，有工作经验的人写码多的人，尤其是从像g这样code review严的地方
出来的，应该都能pass才对。最后一个人又是聊天，大概聊了一半时间后，顺带着引出
一个系统设计问题，也是经典的高频题，就是让设计他家的打车系统里面的一个
feature，轻松搞定，走人。
总的来说，一大半时间感觉都是聊天，扯，吹牛。他家也特别看重culture fit，就是
你要有passion，要有ownership，做事快，take risk。我觉得这些都是靠聊天里面慢
慢透露出来的信息，不是说简单直接了当的问。当然了，认真准备culture fit我觉得
是非常有必要的，其实技术上的水平和背景经历，面试之前基本上就是定下来了的，而
culture fit是可以通过认真准备更充分的体现自己的fit。对了，每个interviewer必
问一次为什么想来U家，我都快能背下我的答案了，最后一个人问的时候，我就明给他
说， 前面问过很多次了，I’ll try to answer this in a different way，然后就即
兴了。
==> take away: 面试中交流聊天非常重要，我觉得不亚于做题写码的重要性。
一个星期后就是拼趣的面试。这一个星期内主要的功夫是花时间用他家的产品，做功课
，产品功能，business model，并且想想哪些是做的很好的，哪些地方可以提高怎么提
高。然后拼趣家的四点文化，认真想下交谈中怎么结合自己的经历能体现出来，对于有
经验的人，我想这些下功夫都是能做好的。虽然我准备了这些，但是最后其实很多准备
的东西都没有机会用上，不过至少还是让我有足够的信心去和面试官交流。拼趣的中国
人非常多，更难得的是，中国人都很抱团很友善，有三轮都是中国人面试官。因为准备
加入拼趣，面试题就不详细写了。
==> take away: 有针对性准备充分，也许会胜过广撒网批发面
打车公司最先给offer的，但是包裹一开始压的非常低，base跟现在差不多持平还略低
一点，只有$43w股票，基本上包裹就是跟现在持平，很失望。直到我有了拼趣的offer
，才追上来，谈到68w也谈不动了。
拼趣很快给了口头offer但是各种原因数字拖了一周才出来，base还不错比现在高，但
考虑到州稅。。。股票最后给涨到1个米，整个过程非常爽快，我也很开心。我知道有
牛人能要到更大的包裹，不过我想自己满意了就好。朋友说他家每年给的refresher也
比较给力，想起来纸面上的数字还是很吸引人。当然，如果没上市，就是一堆废纸。这
次也是我第一次真正经历negotiation，最后效果也还满意，也从朋友那里学习了不少
讨工钱的经验，如果有人有兴趣可以私信我，或者下次有空写写。
最后选了P，钱给的满意是比较小的一个因素，其实U给的也算还不错了。其他很多个人
的考虑，这里就不多说了。至于公司前景的比较上，不用说U的吸引力非常大上市几乎
是必定的，P的风险相比更大，但是潜力也不错，团队也很强，我觉得拼趣的
monetization做的不错，感到有比较强的信心。有机缘跟很多p家的国人接触过，觉得
他家中国人多而且友善团结融洽，这点很喜欢。
Showing posts with label Uber. Show all posts
Showing posts with label Uber. Show all posts
[转载 from mitbbs] Uber On Site Interview
发信人: lusty (lusty), 信区: JobHunting
标 题: Uber 面经
发信站: BBS 未名空间站 (Fri Apr 15 01:33:31 2016, 美东)
Uber:
1. Merge Two Sorted Lists
2. Sparse Matrix Multiplication
3. 给一个n列类似俄罗期方块的盘, 往下掉方块. 方块定义如下:
class Block {
int left;
int right;
int height;
}
其中 0<= left < right < n , 像俄罗斯方块一样会叠起来. 求最高高度
class FallingBlock {
public FallingBlock(int width);
public void fallBlock(Block block);
public int getMaxHeight();
}
4. design whatsapp
标 题: Uber 面经
发信站: BBS 未名空间站 (Fri Apr 15 01:33:31 2016, 美东)
Uber:
1. Merge Two Sorted Lists
2. Sparse Matrix Multiplication
3. 给一个n列类似俄罗期方块的盘, 往下掉方块. 方块定义如下:
class Block {
int left;
int right;
int height;
}
其中 0<= left < right < n , 像俄罗斯方块一样会叠起来. 求最高高度
class FallingBlock {
public FallingBlock(int width);
public void fallBlock(Block block);
public int getMaxHeight();
}
4. design whatsapp
【转载 From MITBBS】Uber面经
U家的
其实主要是聊天, 聊快玩了才问题目, culture fit是他们最看重的.
1. Scramble Game, given some letters, and a big dictionary, how to get
all words that can be generated by combing these letters (use Trie)
2. Simulation game: 假设有一圈人(1 - N)成环状排列, 其中一个投出飞盘, 打到前
面一个, 于是前面一个倒下, 下一个接起来继续扔向前, 知道只剩下一个人为止, 求这
个人的id
3. Find min in rotated Array, design 分布式metrics 系统
5. Read4K problem, followup, how to make it work with multiple calls,
subsequent call should starts from where the last one ends
其实主要是聊天, 聊快玩了才问题目, culture fit是他们最看重的.
1. Scramble Game, given some letters, and a big dictionary, how to get
all words that can be generated by combing these letters (use Trie)
2. Simulation game: 假设有一圈人(1 - N)成环状排列, 其中一个投出飞盘, 打到前
面一个, 于是前面一个倒下, 下一个接起来继续扔向前, 知道只剩下一个人为止, 求这
个人的id
3. Find min in rotated Array, design 分布式metrics 系统
5. Read4K problem, followup, how to make it work with multiple calls,
subsequent call should starts from where the last one ends
【转载 From MITBBS】FLGU面经offer及杂谈
上点新鲜面经回馈版面
F家phone
中年亚裔，比较注重细节
3sum, 每个元素可用多次
ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
简单方法写了个recursive的
约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
L家
phone
两个老美都挺nice 一个主面一个shadow
第一题lowest common ancestor in binary tree with parent pointer
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
onsite
1.host manager面，国人大叔，主要是些背景和behavior question
2.technical communication，亚裔小哥，讲自己的project
这里一点个人的经验是如果面试官不熟悉你的领域的话不一定要讲自己亲手做的东西，
但一定要懂细节（因为不是每个人都有拿得出手又适合展示的project），我就是讲自
己组产品的框架。重点是不要让面试官觉得你做的东西很简单没挑战性，但是也不能太
晦涩要让他能听懂。所以最好先讲大的框架不要抠细节，他如果对那个具体细节感兴趣
自己会问，然后你再和他讨论效果会比较好。最好从他感兴趣的某个点上展开体现下你
的知识深度。另外如果面试官问哪块是你做的可以适当吹牛。
3.lunch interview
陪同你吃饭的人要提供feedback所以开始以为会吃得很不自在，结果碰到超nice的国人
大哥，直接和我中文聊让我放松，最后一路聊天加饭后散步水过，非常感谢！
4. system design，两位国女面试官，经典题url shortener。
开始上网上看过的一个做法，直接被shadow面试官全盘否定。主面试官大姐人很好帮我
打圆场，重新开始设计。这里一点个人经验是有些面试官喜欢否定面试者，这样的人往
往不是大牛但自傲，这种时候哪怕你知道自己是对的也千万不要与之硬扛，否则必死无
疑。最好顺着他来拍个马屁什么的，还有一线生机。
5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
warm up 如果两个linked list intersect的话如何找到merge point。
follow up 有环的情况
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。
6. coding interview two，白人小哥。
algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set<Integer> choosable，target）
判断一个数组里是否存在三个数可以组成一个三角形
lc原题all permutation of array，array 可以有重复元素，结果不允许重复
G家
内部哥们强推，跳过phone
onsite
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
能得话要多少次。
吐槽下，面试官是个三哥，全程非常严肃／黑脸，我说句话就用小本子记下搞得我很紧
张。我说用java写可以吗，曰可以，刚写了两行问我add是啥意思，不知道是想考我基
础知识还是不懂java。
2. 给定一个binary search tree，返回range内所有key，key可以有重复。
版上出现了多次的把一个数拆成任意个平方和的最小拆法。
面试官是中年国人大叔，除了告诉我题目是啥就在电脑上自顾自工作，问话要问两遍才
有反应。写完说我程序有问题，查了半天查不出bug，然后指出我漏了个尖括号，跪了
。。
3. 版上出现多次的longest consecutive sequence in tree
follow up 如何加速，memory放不下怎么办。
国人小哥比较nice，但是只要我不和他主动说话绝不主动和我说话，因为前两场心情略
糟糕写完题目在白板前发呆，哥们就望着我啥也不说，尴尬。。当然也不怪他我自己比
较紧张，回家发现有很弱智的bug但小哥没提不知道怎么回事，可能放我水了
4. 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
时间，
e.g. n＝0就只有0:0一种可能。
面试官是亚裔年轻mm，话不多人很cool，但是思路清晰会引导面试者，感觉碰到懂得引
导面试者或冷漠面试官对面试人表现会有很大影响，真的是看运气了。
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
强推。
之前发过了U的店面，最后签了offer，就不发onsite面筋了。
背景：phd1年多经验，非互联网养老公司
工作c/c++为主做软件性能优化比较多，为了面试专门去coursera上了java（之前有人
推荐的Princeton的算法课）和python的课，感觉多会几种语言后对水平帮助很大，准
备过程中有什么不懂就stackoverflow，
也很有帮助。之前没有任何互联网经验，唯一经验就是自己在aws上做一个小blog网站
，aws构架是scalability的经典教科书，值得学习一下
干货结束，之后是对各个公司和offer的看法，有很多主观因素，不喜勿喷。
G家
很多人觉得g家面试官总体素质很高，不过个人最近面试中的不愉快经历基本都是在g家
发生的，没有明显觉得g家面试官比别家水平高，可能是我运气不好或第一个面的太紧
张。
g家offer流程不确定性很大，快的一周内搞定，慢的要一个月也不稀奇（我自己亲身经
历没有team match还用了快一个月，中间recruiter换过一次，第一个面的g但别家
offer deadline都过了才出结果）。所以最好把g排在最早面试，但是坏处是拿g热身风
险太大，面专门的热身公司对骑驴找马的同学cost又比较高。
个人对g的看法比较neutral，觉得5年之内还是稳稳的业界老大，但是增长已经放缓，
暂时看不到第二春的迹象。坏处就是有明显的刷简历和养老公司的趋势，碰到许多ex－
googler对自由度低和没有存在感颇有微词。很多人升T5不久就走了。
g家默认发low ball offer，但是如果你有好的competing offer可以给的range比任何
一家都大，就看想不想抢你了。从我自己搜集的资料来看，T4的range大概是（括号我
自己的number做参考）
base ： 130-140K （130）
GSU：300-800 （670）
signon：0-50K （50）
基本原则就是没好的competing offer往下限看齐，否则往上限看齐，当然可以更多，
但那基本是极少数牛人，不在讨论范围内。base是HC定的，negotiate空间很小，GSU和
signon有很大空间，senior的recruiter给个几万signon完全可以自己决定。所以有
competing尽管开口要不会有问题。
g家刷题还是有些用处的，但不是决定性的。对非大牛来说g offer运气成分很大，g家
的挑人原则和别人不一样，有strong hire很重要，有个把not hire不影响大局，总体
是1 strong hire ＋ 1 not hire 》1 hire ＋ 1 hire。如果一个strong没有哪怕全是
hire也可能过不了HC。从我自己的base可以推断feedback平均分很一般，但有人力挺我
才拿到的offer，因为recruiter专门和我提到impress some interviewer，并且自己感
觉很有可能有一个面试官给了我not hire。
L家
个人对L家印象不错，recruiter很热情，感觉对面试人比狗家上心，面完后两天就告诉
过了HC可以有offer，专门找了hm和director和我约谈，感觉都不错，最后据offer的时
候很不好意思。
L家是我面过所有里面coding比重较小的，它家题库不大，career cup和论坛上把他家
题都刷熟再加leetcode过coding面一点问题都没有。L家的重头戏在design和
communication，一定要好好准备，我有认识acm大牛没拿到L offer估计就是栽在这些
上面。
L家感觉作为第一份工作非常好：entry level package高，不low ball；app track很
多职位做的事情类似full stack engineer，从mobile到后端都管，是学习的好机会；
总体氛围不错，worklife balance好。缺点是：senior拿的／refresh不如g； 烙印hm
多，干活的都是老中；在普通人群中牌子不如g硬。当然每个人感受不同，其中很多缺
点也算不上缺点。个人聊过的烙印hm感觉人还不错。最后拿的包裹：
base： 145K
RSU： 300K
signon： 50K
U家
对U家最深刻的印象是里面每个人都对公司有超乎寻常的热情。后来才知道对他家没热
情的面试就被刷了。他家很看重这个，如果有人面试中觉得你对他们公司没信心，基本
是一票否决。U家大概是近几十年争议最大的公司了，如果你去网上看新闻评论，各种
负面报道和谩骂基本是铺天盖地，看不见什么好评论，光看这些感觉这个公司分分钟要
倒闭的样子，但事实是它的business还在以惊人的速度增长，鲜明对比下的问题值得深
思。网上有很大的一部分负面评论和customer service有关，它家只有邮件没有电话客
服让很多人很抓狂，另外负面宣传让很多没怎么用过uber的民众觉得它就是个黑车公司
，根本不知道它后面的mission。还有一个很有意思的是我生活中认识的用过uber的人
基本都说好，没见过一个说不好的，但网上骂的那么多真的让人怀疑是不是出租车司机
或水军。
u家非senior面试主要还是coding加一点点design，题目感觉中等偏难。如果senior的
话design类问题比重大大增加，而且会有些很难回答的非算法问题，感觉比较考全方位
的软实力。u家基本是一票否决，所以不能弄砸某一轮。最近还在大量招人，不过面的
人也很多，所以还是比较挑剔的导致议价空间也很小。
u家面试很高效，onsite当天或第二天给offer，过两天没消息基本就是挂了，它家
经过5月最新50b估值后standard package慢慢开始low ball了，最近的2级（比senior
低一级）standard range大概是
base： 125-130K
rsu：12000-14000 unit 按39/unit来的
传说中它家基本不negotiate，但个人经验还是可以的，但是你要有比较好的competing
offer。它家现在和g抢人抢的挺凶，所以有好的GF之类的offer还是可以讲的但是操作
空间也不是很大，最后g家给的包裹基本快赶上u了而且全是cash（签uber的第二天g股
票就飙了），选他家主要是在养老公司呆怕了，希望能有点impact，但愿以后不会后悔。
F家phone
中年亚裔，比较注重细节
3sum, 每个元素可用多次
ksum, 讨论了下理论最优解法和复杂度，面试官说空间复杂度太大而且不好code，就用
简单方法写了个recursive的
约onsite时recruiter说entry level招满了，要把onsite推到10月，只能放弃了
L家
phone
两个老美都挺nice 一个主面一个shadow
第一题lowest common ancestor in binary tree with parent pointer
第二题find minimum distance between two words in a string array
e.g (“the”, “quick”, “brown”, “fox”, “quick”)
distance(“fox”,”the”) = 3
distance(“quick”, “fox”) = 1
onsite
1.host manager面，国人大叔，主要是些背景和behavior question
2.technical communication，亚裔小哥，讲自己的project
这里一点个人的经验是如果面试官不熟悉你的领域的话不一定要讲自己亲手做的东西，
但一定要懂细节（因为不是每个人都有拿得出手又适合展示的project），我就是讲自
己组产品的框架。重点是不要让面试官觉得你做的东西很简单没挑战性，但是也不能太
晦涩要让他能听懂。所以最好先讲大的框架不要抠细节，他如果对那个具体细节感兴趣
自己会问，然后你再和他讨论效果会比较好。最好从他感兴趣的某个点上展开体现下你
的知识深度。另外如果面试官问哪块是你做的可以适当吹牛。
3.lunch interview
陪同你吃饭的人要提供feedback所以开始以为会吃得很不自在，结果碰到超nice的国人
大哥，直接和我中文聊让我放松，最后一路聊天加饭后散步水过，非常感谢！
4. system design，两位国女面试官，经典题url shortener。
开始上网上看过的一个做法，直接被shadow面试官全盘否定。主面试官大姐人很好帮我
打圆场，重新开始设计。这里一点个人经验是有些面试官喜欢否定面试者，这样的人往
往不是大牛但自傲，这种时候哪怕你知道自己是对的也千万不要与之硬扛，否则必死无
疑。最好顺着他来拍个马屁什么的，还有一线生机。
5. coding interview one，面试官是酷酷的国人小哥和新来的印度小哥。
warm up 如果两个linked list intersect的话如何找到merge point。
follow up 有环的情况
假设给一排n个房子paint，有m种不同颜色可选，相邻房子不能同色，给定一个mxn的
cost matrix，求最小cost的染色方法。
6. coding interview two，白人小哥。
algorithm game，两个玩家从一组数里轮流取数，取过就从数组拿走，如果某个玩家取
数后所有已经取出的数和超过给定值则胜出，要求判断第一个拿是否能赢写函数
boolean isWin（Set<Integer> choosable，target）
判断一个数组里是否存在三个数可以组成一个三角形
lc原题all permutation of array，array 可以有重复元素，结果不允许重复
G家
内部哥们强推，跳过phone
onsite
1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡
片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的
话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，
能得话要多少次。
吐槽下，面试官是个三哥，全程非常严肃／黑脸，我说句话就用小本子记下搞得我很紧
张。我说用java写可以吗，曰可以，刚写了两行问我add是啥意思，不知道是想考我基
础知识还是不懂java。
2. 给定一个binary search tree，返回range内所有key，key可以有重复。
版上出现了多次的把一个数拆成任意个平方和的最小拆法。
面试官是中年国人大叔，除了告诉我题目是啥就在电脑上自顾自工作，问话要问两遍才
有反应。写完说我程序有问题，查了半天查不出bug，然后指出我漏了个尖括号，跪了
。。
3. 版上出现多次的longest consecutive sequence in tree
follow up 如何加速，memory放不下怎么办。
国人小哥比较nice，但是只要我不和他主动说话绝不主动和我说话，因为前两场心情略
糟糕写完题目在白板前发呆，哥们就望着我啥也不说，尴尬。。当然也不怪他我自己比
较紧张，回家发现有很弱智的bug但小哥没提不知道怎么回事，可能放我水了
4. 设计个用bit形式表示时间（小时：分钟）的clock，
e.g 10:15可以写作1010:1111，每个bit是一个小灯泡，打印所有有且仅有n盏灯亮着的
时间，
e.g. n＝0就只有0:0一种可能。
面试官是亚裔年轻mm，话不多人很cool，但是思路清晰会引导面试者，感觉碰到懂得引
导面试者或冷漠面试官对面试人表现会有很大影响，真的是看运气了。
5.算法游戏，给一个只有＋－两种字符的array，两个玩家，轮到某个玩家他可以任选
两个连续的－－将他们变成＋＋，如果某个玩家发现自己无法行动则赢得游戏，要求写
isWin（String s）判断先行动的玩家能否赢。
followup 如何优化，时间上和空间上。
面试官是做android前端的白人mm，非常活泼健谈，一路聊天愉快，面完就感觉她会给
强推。
之前发过了U的店面，最后签了offer，就不发onsite面筋了。
背景：phd1年多经验，非互联网养老公司
工作c/c++为主做软件性能优化比较多，为了面试专门去coursera上了java（之前有人
推荐的Princeton的算法课）和python的课，感觉多会几种语言后对水平帮助很大，准
备过程中有什么不懂就stackoverflow，
也很有帮助。之前没有任何互联网经验，唯一经验就是自己在aws上做一个小blog网站
，aws构架是scalability的经典教科书，值得学习一下
干货结束，之后是对各个公司和offer的看法，有很多主观因素，不喜勿喷。
G家
很多人觉得g家面试官总体素质很高，不过个人最近面试中的不愉快经历基本都是在g家
发生的，没有明显觉得g家面试官比别家水平高，可能是我运气不好或第一个面的太紧
张。
g家offer流程不确定性很大，快的一周内搞定，慢的要一个月也不稀奇（我自己亲身经
历没有team match还用了快一个月，中间recruiter换过一次，第一个面的g但别家
offer deadline都过了才出结果）。所以最好把g排在最早面试，但是坏处是拿g热身风
险太大，面专门的热身公司对骑驴找马的同学cost又比较高。
个人对g的看法比较neutral，觉得5年之内还是稳稳的业界老大，但是增长已经放缓，
暂时看不到第二春的迹象。坏处就是有明显的刷简历和养老公司的趋势，碰到许多ex－
googler对自由度低和没有存在感颇有微词。很多人升T5不久就走了。
g家默认发low ball offer，但是如果你有好的competing offer可以给的range比任何
一家都大，就看想不想抢你了。从我自己搜集的资料来看，T4的range大概是（括号我
自己的number做参考）
base ： 130-140K （130）
GSU：300-800 （670）
signon：0-50K （50）
基本原则就是没好的competing offer往下限看齐，否则往上限看齐，当然可以更多，
但那基本是极少数牛人，不在讨论范围内。base是HC定的，negotiate空间很小，GSU和
signon有很大空间，senior的recruiter给个几万signon完全可以自己决定。所以有
competing尽管开口要不会有问题。
g家刷题还是有些用处的，但不是决定性的。对非大牛来说g offer运气成分很大，g家
的挑人原则和别人不一样，有strong hire很重要，有个把not hire不影响大局，总体
是1 strong hire ＋ 1 not hire 》1 hire ＋ 1 hire。如果一个strong没有哪怕全是
hire也可能过不了HC。从我自己的base可以推断feedback平均分很一般，但有人力挺我
才拿到的offer，因为recruiter专门和我提到impress some interviewer，并且自己感
觉很有可能有一个面试官给了我not hire。
L家
个人对L家印象不错，recruiter很热情，感觉对面试人比狗家上心，面完后两天就告诉
过了HC可以有offer，专门找了hm和director和我约谈，感觉都不错，最后据offer的时
候很不好意思。
L家是我面过所有里面coding比重较小的，它家题库不大，career cup和论坛上把他家
题都刷熟再加leetcode过coding面一点问题都没有。L家的重头戏在design和
communication，一定要好好准备，我有认识acm大牛没拿到L offer估计就是栽在这些
上面。
L家感觉作为第一份工作非常好：entry level package高，不low ball；app track很
多职位做的事情类似full stack engineer，从mobile到后端都管，是学习的好机会；
总体氛围不错，worklife balance好。缺点是：senior拿的／refresh不如g； 烙印hm
多，干活的都是老中；在普通人群中牌子不如g硬。当然每个人感受不同，其中很多缺
点也算不上缺点。个人聊过的烙印hm感觉人还不错。最后拿的包裹：
base： 145K
RSU： 300K
signon： 50K
U家
对U家最深刻的印象是里面每个人都对公司有超乎寻常的热情。后来才知道对他家没热
情的面试就被刷了。他家很看重这个，如果有人面试中觉得你对他们公司没信心，基本
是一票否决。U家大概是近几十年争议最大的公司了，如果你去网上看新闻评论，各种
负面报道和谩骂基本是铺天盖地，看不见什么好评论，光看这些感觉这个公司分分钟要
倒闭的样子，但事实是它的business还在以惊人的速度增长，鲜明对比下的问题值得深
思。网上有很大的一部分负面评论和customer service有关，它家只有邮件没有电话客
服让很多人很抓狂，另外负面宣传让很多没怎么用过uber的民众觉得它就是个黑车公司
，根本不知道它后面的mission。还有一个很有意思的是我生活中认识的用过uber的人
基本都说好，没见过一个说不好的，但网上骂的那么多真的让人怀疑是不是出租车司机
或水军。
u家非senior面试主要还是coding加一点点design，题目感觉中等偏难。如果senior的
话design类问题比重大大增加，而且会有些很难回答的非算法问题，感觉比较考全方位
的软实力。u家基本是一票否决，所以不能弄砸某一轮。最近还在大量招人，不过面的
人也很多，所以还是比较挑剔的导致议价空间也很小。
u家面试很高效，onsite当天或第二天给offer，过两天没消息基本就是挂了，它家
经过5月最新50b估值后standard package慢慢开始low ball了，最近的2级（比senior
低一级）standard range大概是
base： 125-130K
rsu：12000-14000 unit 按39/unit来的
传说中它家基本不negotiate，但个人经验还是可以的，但是你要有比较好的competing
offer。它家现在和g抢人抢的挺凶，所以有好的GF之类的offer还是可以讲的但是操作
空间也不是很大，最后g家给的包裹基本快赶上u了而且全是cash（签uber的第二天g股
票就飙了），选他家主要是在养老公司呆怕了，希望能有点impact，但愿以后不会后悔。
[转载 From mitbbs] Uber新题
算圆周率。iterative and recursive. 谁会。怎么比较精确。
spark 给的example
https://github.com/apache/spark/blob/master/examples/src/main/scala/org/
apache/spark/examples/SparkPi.scala
http://www.mitbbs.com/article_t/JobHunting/33003595.html
spark 给的example
https://github.com/apache/spark/blob/master/examples/src/main/scala/org/
apache/spark/examples/SparkPi.scala
http://www.mitbbs.com/article_t/JobHunting/33003595.html
[转载 from mitbbs] 回报本版，前段时间骑驴找马FGU等公司offer面经总结
Amazon
·
Apple
·
Facebook
·
Google
·
Interview Preparation
·
Interview Questions
·
Sumo Logic
·
Uber
·
Yahoo
前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给）
再上各个公司的面经和感受：
Yahoo：
最早面的公司，面的是Flurry Team，Yahoo去年收购的一家在城里的小公司，所以不一
定有代表性。因为re-org我两个月之后才拿到offer，中间还给我match到其他team几次
，Yahoo比较动荡，个人也不看好。
电面：
和director聊了有两个小时，无coding，问了很多之前project内容和hadoop相关的内
容。
最后讨论了一道design，如何设计distributed key-value store，因为他们主要用
HBase。
Programming Test:
Validate Soduko Solution，从文件读solution，尽量用production标准写程序。
Onsite：
五轮Onsite没有coding，全是问实际问题怎么解决和design。
1. 如何设计一个priorityqueue service，client可以submit job request然后server
按照priority执行
2. 需要一个key-value store with 1M qps，most read，1ms 99% latency，如果用
HBase的话会有什么问题，怎么解决
3. 给很多整数，如何用mapreduce找median，如果是很多float数，可以有一定的误差
，如何找
4. Programming Test的扩展，如果soduku matrix非常之大怎么做
然后还有一大堆针对hadoop的各种情况下怎么optimize的问题
onsite完了之后他们director说very positive，然后就开始re-org两个月。Flurry做
的东西其实挺有意思，mobile analytics platform #1，我感觉他们engineer人很nice
，水准也非常不错，可惜没缘分。
############################################################################
###########
Apple：
练手公司1，Apple可以同时面很多组，每个组有各自的recruiter。我把简历递了之后
陆续有10个组联系我，然后每个组基本上都是onsite之前两轮phone，一开始没经验联
系了4个组后来发现实在体力吃不消，光电面就8轮。最后3个组要onsite，这里我犯了
一个错误，告诉他们我在面其他的组，一旦他们知道你在面其他的组就不跟进了，打死
不回email。所以最终我只onsite了一个组。
电面：
1.给平面一堆点，把所有在同一条直线上的点group在一起，求出所有的group
2.一种encoding的方法，如果一个byte第一个bit是0，比如 00000000，那它自己表示
一个字符，如果一个byte第一个bit是1，比如 10000000，那它和它后面紧跟的byte表
示一个字符，现在给一个byte array，判断最后一个字符是一个byte还是两个byte组成。
3.parse message from byte stream，message format是前4个bytes组成的int值表示
message的长度L，然后后面连续的L个byte是message真正的内容，每个message都是这
样表示，需要一边读byte stream一边parse每个message
4. 两个table做join有哪几种方法，分别有哪些drawback
5. merge two sorted list
6. sqrt(double number, double epsilon)
7. auto completion implementation using trie
8. edit distance
9. Implement blockingqueue
10. how is a hive query transferred to mapreduce jobs
Onsite:
1. given a list of pairs, pair.first 表示parent, pair.second表示child,
reconstruct the tree, return the root node.
2. auto completion - design the service
3. design a service, accept stream of events, each event has a type and
timestamp, need to support the query of top k most frequent types in a query
specified [start, end] time range.
4. closest number to target in BST
5. validate soduku / solve soduku, and optimizations
6. 给一个json object，给一个wildcard path with ‘?’ as arbitrary name，比如
a.?.b 找到所有符合path的objects
Apple一般onsite的时候4轮tech interview，中午的时候将来的manager带着吃午饭。
如果tech这4轮面的好会有第5轮见到hiring manager，如果有这一轮基本说明offer没
啥问题了，这轮会是一堆behavior。如果第5轮也没啥问题会有第6轮见大boss，继续
behavior，会问之前做过的project有多牛叉，会吹就行。
同等级下Apple的offer远不如FG给力，而且match不上去，bonus也不会写在offer
letter里面，虽然据说每年的refresh有些组相当多，但是感觉整体上跟FG还是差距比
较大。而且组跟组工作强度差别也很大，有些组忙死有些组闲死，不过software的组一
般都还好，感觉大部分人精神状态还是不错的。
就engineer水平来看，我有遇到水平相当不错的面试官，但是整体水准远不如FG。
他们各个组做项目是完全分开的，基本没交流。做东西完全是product driven，不过
engineer一般需要fullstack，需要自己end to end维护一个product，这点对有些人可
能还比较有吸引力。
############################################################################
###########
Amazon：
练手公司2，我面的是marketing solution和ads相关的team。大公司周期很长，感觉
recruiter不是很上心。
电面：
三哥，但是感觉还行没黑。
1.用trie来解决求dictionary里面所有符合given prefix的word。然后又扩展到prefix
里面有wildcard的情况，然后继续讨论如果要design a system做这个事情怎么搞，需
要注意哪些问题。
Onsite：
居然没有遇到三哥，除了一轮老中外其他都是老白，每一轮开始都是至少15分钟的
behavior，而且每个人还能换着花样问不一样的问题，感觉大部分脑细胞都花在这些没
用的东西上面了，所以感觉很不爽。
1. OOD Restaurant Reservation System
2. Merge K Sorted List
3. K Sized Sliding Window Sum/Minimum Value
4. 给一个css file里面很多class，然后class name里面其实很多重复的，怎么
compress用尽量最小size的string来表示，这样传输的byte比较少。
5. shorten url system design
6. longest palindromic substring
7. robot moving from topleft to bottomright corner of a matrix，matrix里面有
些cell是障碍物不能通过，只能往下或者往右走，有多少种方法。
8. 之前做的项目，和我之前坑爹公司的architecture
相比起他们的behavior问题，我觉得亚麻的engineer水平相当一般，很多design
principle都不知道，可能因为他们内部都直接用aws很多细节都不需要考虑，也有可能
跟我面的组有关系，如果面的是aws会好些吧。
亚麻最后给我senior title，但是package跟其他几家比起来差距略大，所以也就没再
继续谈。
############################################################################
###########
WalmartLab：
我面的是walmartlab里面仅存的几个不是三哥的组，通过靠谱的朋友内推。
面试题整体难度也还好，算法基本上都是常见题目，国人面试官都非常非常非常nice。
只说其中几轮比较有意思的吧
1.topological sort
2.design web crawler system，how to scale，what would be the bottle neck and
how to solve the problem
3. 如何用semaphore或者condition variable实现3个process p1, p2, p3，p2必须要
p1结束才能运行，p3必须要p2结束才能运行
4. bloom filter 如何implement，estimate false rate
5. what is the best design pattern do you think and why
他们onsite有一轮会是跟product manager聊天，就是瞎扯。一个小时我都在绞尽脑汁
找话题，应该是类似culture fit吧，看看你是不是比较容易融入team。
walmartlab是第一个给我比较decent offer的公司，cash给的很多，所以其实我很感激
，而且我面的组的work life balance极好，我见过的最好的没有之一，onsite居然有
两轮是video因为面试官WFH。平时干活也非常自由，没有OKR，没有deadline（是的你
没看错，啥都没有，performance完全老板说了算）。
不去walmartlab的原因是我觉得他们实在缺有经验的engineer，而且很多做的很多东西
都是实验性质的，没有明显的business impact，现阶段我还是比较想去一个大腿比较
多的地方抱一下。
############################################################################
###########
Sumo Logic：
一开始看到这家公司里面好多MIT毕业的人，而且听说他们bar很高，所以一开始也只是
想拿来做一下benchmark。他们基本上都用scala，如果懂一点scala效果会比较好但是
不懂对面试也完全没有影响。
他们的面试是先一轮phone，然后两次onsite，第一次onsite2轮，第二次onsite3轮，
第一次onsite过了才会有第二次onsite。第二次onsite每一轮会有两个面试官，每个面
试官都会出一道题目。
电面：
1. 两个binary tree，每个node存的值有两种可能，1或者0，把两个tree对应node做or
操作。
极为简单，扯了一下immutable data structure然后聊了一会之前做的东西就过了。
onsite 1：
1. 纯聊project和讨论他们现有的data ingestion架构，刚好他们最近想用Kafka所以
就这个话题聊了一个小时，最后没时间做题就结束了
2. 小三哥，但是也不黑。
given a list of intervals，query if another interval is totally covered by
the list of intervals。
totally covered是指整个区间都被某些已有的区间 cover了。
比如如果有 list of intervals = 【（1， 4），（2，8）】
given interval【3，6】就被完全cover了。
然后扩展到design a system来做这个事情，可以query，也可以insert interval，假
设query操作的频率远远大于insert操作，并且interval的数量非常非常多。
onsite 2：
1. 有意思的题目1，设计Bi-directional LRU cache data structure，既可以lookup
key to get value，也可以lookup value to get key，还支持set(key, value)操作，
后面又加了条件，concurrent的情况下，会有什么问题，如何改进，假如set这个操作
的频率远远小于get这个操作的频率，需要写代码实现。
2. robot from topleft to bottomright LC原题，无障碍和有障碍
3. given a list of sets，find all pair of sets having any intersection
4. 有意思的题目2，设计caltrain system，要实现caltrain上车下车刷卡扣钱整个功
能，assume每个station都跟一个central server相连，要处理如果有network
partition怎么办，eventually车费还是要charge到账户上，但是不能影响partition的
station正常运作。要处理某些人下车没刷卡怎么办，followup可以非常多
5. 有意思的题目3，仍然是设计一个cocurrent环境下的time leased cache，但是有些
区别，假如delete操作是一个daemon thread来做不用太多考虑，但是get(key)操作的
逻辑是如果key不在cache里面，需要一个非常expensive的操作把对应value load进来
，如何让这个load的操作对同一个key尽量少发生，需要写代码实现。
这家的题目我觉得非常有意思，engineer都超级nice，感觉我见过的人的能力都非常不
错，年轻一点的反应非常快，年长一点的经验非常丰富。整体上看三哥并不多，虽然
engineering vp是三哥。
这家很有诚意，最后给我的base跟walmartlab差不多，再加上很难估值的option。他们
觉得他们的bar很高，能过他们面试的人不多，所以一旦你过了他们面试，要做好被他
们的recruiter不停骚扰的准备。
有关这个公司，在其他帖子里面我提到过，虽然engineering vp是个三哥，但是感觉还
比较靠谱，不像某些三哥吹牛没有边际，对于整个公司发展的前景比较有数，business
model也很promising，最近刚刚拿到一笔80M的投资。
############################################################################
###########
Palantir：
号称湾区面试最难的公司。但是again我运气比较好没有碰到很难的题目。我觉得这家
公司有点吹的过大了，本身做的东西根本没有什么技术含量，里面都是一群没经验的
stanford小年轻，都是自我感觉超好。另外去这家公司要做好准备每周工作60hours。
估值150亿了还给option我也是醉了，能上市不？我的看法就是这家公司基本就是坑，
从哪个角度来讲都不值得去。
他们的onsite上午会有3轮，然后中午吃完饭后会有一个小时的demo（因为实在没什么
意思所以我差点睡着了），如果上午过了下午还会有1 - 2轮，一般下午会有一轮
system design，另一轮是见hiring manager，如果上午没过demo结束就可以回家了。
电面：
万年不变的电面题，给一个array，问有没有duplicate
follow up1，只要index的距离 < k并且value相同就算duplicate
follow up2，只要index的距离 < k并且value的绝对值差 < d 就算duplicate
follow up3，follow up2能不能有time complexity O(n)的解？
Onsite：
1. OOD astroid game，就是飞机打石块的游戏，石块可以任意形状可以移动，飞机撞
上就挂了，飞机可以发射子弹，子弹打上石块会把石块分成多个小石块按照不同方向和
速度移动。要写伪代码。
2. 每个person有一个list of intervals，表示busy的时间段，问最busy的一段时间分
别都是谁busy。
3. 一个描述起来不算简单的题目，但是算法不难，在版上看到过但是细节记不清了，
好像是给一堆stock profile然后算profit
4. 一个2d matrix，被分成好几个区域，区域之间都是value为0的cell，每一堆
connected的非0cell算是一个区域，问和最大的区域是哪个，要设计API，怎么用json
return结果。
5. system design又是 distributed key-value store，万年不变的题目，后来没啥好
聊的只好跟面试官扯他们的那个atlas，distributed transaction layer，没办法想拿
offer跪舔还是需要的。
基本上每个面试官都是一副老子很牛逼的样子，一问他们到底做了什么牛逼的东西马上
支支吾吾说不出个所以然。他们的offer也没诚意，150k的base + 25k signon +
55000option，没谈就直接拒掉了。
############################################################################
###########
Dropbox：
Dropbox的面试题都是从题库出的，但问题是他们的题库并不大。所以，我可以负责任
的说，你在这个版上找到的面经题目，你在面试过程中绝对能碰到。另外他们复杂的算
法题目并不多，但是大部分是跟concurrency有关的问题。
一般标配是 2轮电面 + 6轮onsite，6轮onsite中居然有两轮是behavior和culture fit
另外，他们面试的要求都是要写能run的code，要写完整的solution，不能写个主要
function就完事。
电面：
1. 给一堆file，如何比较有效率的把内容完全相同的file group到一起，file可能非
常大
2. 被人面过无数次的电话号码转成string，然后再word break那个题目
Onsite：
1. log_hit(), get_last_5mins_hits()那个题目，concurrent怎么搞
2. token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如
果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样
用最简单的方法实现
3. web crawler，要分析可能的bottleneck，然后转化成concurrent运行的版本，写
runnable代码。
4. system desgin那一轮是两个三哥，轮流轰炸了一个小时，把我之前做的所有东西完
全推翻了，所以这一轮没结束我就知道肯定挂了。
############################################################################
###########
后面这三个公司是整个面试过程中给我感觉最好的三个公司。
Uber：
Uber的效率不是一般的牛叉。我从刚开始被Uber联系到最后拿到offer基本在一个周之
内搞定。面完了Uber之后真的有点心动，因为面我的人我觉得都很牛逼，人也都很超
nice，非常乐于提供很多关于Uber的信息，整个氛围非常积极向上。老板虽然是个三哥
但是也没有任何能吐槽的地方，他手下现在也基本都是老中。
电面：
一般电面会是hiring manager，除了问了一下之前做过什么之外只有一道题目：
OOD card deck，要现场deug，需要能运行
电面后一个小时通知我可以onsite
Onsite：
onsite一般是5轮，中间老板带着吃午饭
5轮中必然有一轮是只讨论之前做过的project，要做好准备，一定要对自己之前做的东
西特别熟
另外我面试过程中问了不少怎么设计一个系统解决Uber实际问题这种题目，很新颖很有
意思
1. 问了我不少关于storm的问题，比如storm怎么保证exact once/at least once
semantic，如何做timed window join，因为我简历上有相关的东西，然后让我用storm
来做一个比较简单的sliding window count。
2. big integer multiplication，要求现场运行代码。
3. longest increasing subarray，longest increasing subpath in a tree，path只
能从root到某个leaf
4. boggle game，given a boggle board and a dictionary，find all words on the
board，
follow up，如果dictionay 不变但是board不停的变怎么优化
follow up，如果board不变但是dictionary不停的变怎么优化
5. given a matrix only containing 1 or 0，find how many rectangles are 4个角
都是1
6. how to design a system to automatically detect hotspot on geo graph, a
hotspot is an area such that 打车的request远多于available driver的数量
7. how to design a system to detect if dispatch algorithm has some bug，
dispatch主要是收集所有打车request和available driver的信息然后决定哪个driver
哪个客人
Onsite过后两个小时通知我有offer了，如果onsite过后一两天之内没通知的话，基本
上说明你的waiting list上，要等排在你前面的人据掉offer才可以继续下一步。
############################################################################
###########
Facebook：
initial round我是直接去onsite的，但是根据其他朋友的经验似乎电面或者onsite影
响也根本不大，因为第一轮基本只要没有太大的纰漏都会过。
Onsite：
一共5轮，如果是4级的话会是3轮coding，1轮behavior和1轮system design。因为偏
infra, 所以我有3轮是三哥，当时已经做好挂的准备了。
1. move all 0s to right end of the array
2. decode way
3. binary tree inorder iterator
4. determine if there is a subarray sum to target number
5. convert integer to string，1000 to “one thousand”
6. system design - design facebook music system，只需要design service tier，
两个API
get_top_10_list_music_ids(int64 userid) - return top 10 most frequent
listened music ids for a given user last week. 这个call在load页面的时候要进
行，所以对latency要求比较高。
record(int64 userid, int64 musicid, int64 timestamp) - 每当user听一首歌，就
需要记录下来，这个可以asynch进行，需要eventually consistent，但不需要每听一
首歌马上就能反映到上一个call中。要做各种spec和resource的estimation。
7. 抄dropbox那个问题，get_hits_last_5mins(), record_hit()，但是后面又扯到
system design，如何thread safe，如果是districuted syste怎么搞，能想到几种方法
8. behavior那一轮基本上围绕着的主题是，你之前碰到什么难解决的问题，怎么解决
的，你学到了什么，production有过什么比较傻叉的bug，怎么避免的。你之前做项目
有没有cross team的，你怎么说服其他team听你的，等等。聊得过多导致最后没有时间
所有这一轮没有coding
我觉得我的运气很好，再次没有碰到很难的题目，尤其是算法。
############################################################################
###########
Google：
狗家如果真的想快的话还是可以的，我从开始被recruiter联系到offer也是一个周之内
搞定。
狗家和F家整个感觉都很好，面试官都很乐意帮忙，而且明显感觉到水平跟其他公司不
一样，技术功底非常扎实。
再次运气很好所以没有碰到很偏很难的题目，基本上就是水过了。其中几道比较有意思
的题目：
1. 一个正整数可以表示成其他几个正整数的平方和，给任何一个正整数，求最少的那
几个正整数，平方和是给定的数，比如14 = 1^2 + 2^2 + 3^2，如果给的数是14，应该
返回（1，2，3）
2. 给一个dictionary，然后可以support的query是，给一个string，返回在
dictionary里面包含给定string的所有character的最短的string
3. 如何设计google login system
4. web crawl的时候如何判断两个document是相同/相似的。
抱歉很多细节实在记不清了，表达能力也有限没办法在这个帖子里面说的很明白。如果
大家有问题我会尽我所能回答，谢谢。
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给）
再上各个公司的面经和感受：
Yahoo：
最早面的公司，面的是Flurry Team，Yahoo去年收购的一家在城里的小公司，所以不一
定有代表性。因为re-org我两个月之后才拿到offer，中间还给我match到其他team几次
，Yahoo比较动荡，个人也不看好。
电面：
和director聊了有两个小时，无coding，问了很多之前project内容和hadoop相关的内
容。
最后讨论了一道design，如何设计distributed key-value store，因为他们主要用
HBase。
Programming Test:
Validate Soduko Solution，从文件读solution，尽量用production标准写程序。
Onsite：
五轮Onsite没有coding，全是问实际问题怎么解决和design。
1. 如何设计一个priorityqueue service，client可以submit job request然后server
按照priority执行
2. 需要一个key-value store with 1M qps，most read，1ms 99% latency，如果用
HBase的话会有什么问题，怎么解决
3. 给很多整数，如何用mapreduce找median，如果是很多float数，可以有一定的误差
，如何找
4. Programming Test的扩展，如果soduku matrix非常之大怎么做
然后还有一大堆针对hadoop的各种情况下怎么optimize的问题
onsite完了之后他们director说very positive，然后就开始re-org两个月。Flurry做
的东西其实挺有意思，mobile analytics platform #1，我感觉他们engineer人很nice
，水准也非常不错，可惜没缘分。
############################################################################
###########
Apple：
练手公司1，Apple可以同时面很多组，每个组有各自的recruiter。我把简历递了之后
陆续有10个组联系我，然后每个组基本上都是onsite之前两轮phone，一开始没经验联
系了4个组后来发现实在体力吃不消，光电面就8轮。最后3个组要onsite，这里我犯了
一个错误，告诉他们我在面其他的组，一旦他们知道你在面其他的组就不跟进了，打死
不回email。所以最终我只onsite了一个组。
电面：
1.给平面一堆点，把所有在同一条直线上的点group在一起，求出所有的group
2.一种encoding的方法，如果一个byte第一个bit是0，比如 00000000，那它自己表示
一个字符，如果一个byte第一个bit是1，比如 10000000，那它和它后面紧跟的byte表
示一个字符，现在给一个byte array，判断最后一个字符是一个byte还是两个byte组成。
3.parse message from byte stream，message format是前4个bytes组成的int值表示
message的长度L，然后后面连续的L个byte是message真正的内容，每个message都是这
样表示，需要一边读byte stream一边parse每个message
4. 两个table做join有哪几种方法，分别有哪些drawback
5. merge two sorted list
6. sqrt(double number, double epsilon)
7. auto completion implementation using trie
8. edit distance
9. Implement blockingqueue
10. how is a hive query transferred to mapreduce jobs
Onsite:
1. given a list of pairs, pair.first 表示parent, pair.second表示child,
reconstruct the tree, return the root node.
2. auto completion - design the service
3. design a service, accept stream of events, each event has a type and
timestamp, need to support the query of top k most frequent types in a query
specified [start, end] time range.
4. closest number to target in BST
5. validate soduku / solve soduku, and optimizations
6. 给一个json object，给一个wildcard path with ‘?’ as arbitrary name，比如
a.?.b 找到所有符合path的objects
Apple一般onsite的时候4轮tech interview，中午的时候将来的manager带着吃午饭。
如果tech这4轮面的好会有第5轮见到hiring manager，如果有这一轮基本说明offer没
啥问题了，这轮会是一堆behavior。如果第5轮也没啥问题会有第6轮见大boss，继续
behavior，会问之前做过的project有多牛叉，会吹就行。
同等级下Apple的offer远不如FG给力，而且match不上去，bonus也不会写在offer
letter里面，虽然据说每年的refresh有些组相当多，但是感觉整体上跟FG还是差距比
较大。而且组跟组工作强度差别也很大，有些组忙死有些组闲死，不过software的组一
般都还好，感觉大部分人精神状态还是不错的。
就engineer水平来看，我有遇到水平相当不错的面试官，但是整体水准远不如FG。
他们各个组做项目是完全分开的，基本没交流。做东西完全是product driven，不过
engineer一般需要fullstack，需要自己end to end维护一个product，这点对有些人可
能还比较有吸引力。
############################################################################
###########
Amazon：
练手公司2，我面的是marketing solution和ads相关的team。大公司周期很长，感觉
recruiter不是很上心。
电面：
三哥，但是感觉还行没黑。
1.用trie来解决求dictionary里面所有符合given prefix的word。然后又扩展到prefix
里面有wildcard的情况，然后继续讨论如果要design a system做这个事情怎么搞，需
要注意哪些问题。
Onsite：
居然没有遇到三哥，除了一轮老中外其他都是老白，每一轮开始都是至少15分钟的
behavior，而且每个人还能换着花样问不一样的问题，感觉大部分脑细胞都花在这些没
用的东西上面了，所以感觉很不爽。
1. OOD Restaurant Reservation System
2. Merge K Sorted List
3. K Sized Sliding Window Sum/Minimum Value
4. 给一个css file里面很多class，然后class name里面其实很多重复的，怎么
compress用尽量最小size的string来表示，这样传输的byte比较少。
5. shorten url system design
6. longest palindromic substring
7. robot moving from topleft to bottomright corner of a matrix，matrix里面有
些cell是障碍物不能通过，只能往下或者往右走，有多少种方法。
8. 之前做的项目，和我之前坑爹公司的architecture
相比起他们的behavior问题，我觉得亚麻的engineer水平相当一般，很多design
principle都不知道，可能因为他们内部都直接用aws很多细节都不需要考虑，也有可能
跟我面的组有关系，如果面的是aws会好些吧。
亚麻最后给我senior title，但是package跟其他几家比起来差距略大，所以也就没再
继续谈。
############################################################################
###########
WalmartLab：
我面的是walmartlab里面仅存的几个不是三哥的组，通过靠谱的朋友内推。
面试题整体难度也还好，算法基本上都是常见题目，国人面试官都非常非常非常nice。
只说其中几轮比较有意思的吧
1.topological sort
2.design web crawler system，how to scale，what would be the bottle neck and
how to solve the problem
3. 如何用semaphore或者condition variable实现3个process p1, p2, p3，p2必须要
p1结束才能运行，p3必须要p2结束才能运行
4. bloom filter 如何implement，estimate false rate
5. what is the best design pattern do you think and why
他们onsite有一轮会是跟product manager聊天，就是瞎扯。一个小时我都在绞尽脑汁
找话题，应该是类似culture fit吧，看看你是不是比较容易融入team。
walmartlab是第一个给我比较decent offer的公司，cash给的很多，所以其实我很感激
，而且我面的组的work life balance极好，我见过的最好的没有之一，onsite居然有
两轮是video因为面试官WFH。平时干活也非常自由，没有OKR，没有deadline（是的你
没看错，啥都没有，performance完全老板说了算）。
不去walmartlab的原因是我觉得他们实在缺有经验的engineer，而且很多做的很多东西
都是实验性质的，没有明显的business impact，现阶段我还是比较想去一个大腿比较
多的地方抱一下。
############################################################################
###########
Sumo Logic：
一开始看到这家公司里面好多MIT毕业的人，而且听说他们bar很高，所以一开始也只是
想拿来做一下benchmark。他们基本上都用scala，如果懂一点scala效果会比较好但是
不懂对面试也完全没有影响。
他们的面试是先一轮phone，然后两次onsite，第一次onsite2轮，第二次onsite3轮，
第一次onsite过了才会有第二次onsite。第二次onsite每一轮会有两个面试官，每个面
试官都会出一道题目。
电面：
1. 两个binary tree，每个node存的值有两种可能，1或者0，把两个tree对应node做or
操作。
极为简单，扯了一下immutable data structure然后聊了一会之前做的东西就过了。
onsite 1：
1. 纯聊project和讨论他们现有的data ingestion架构，刚好他们最近想用Kafka所以
就这个话题聊了一个小时，最后没时间做题就结束了
2. 小三哥，但是也不黑。
given a list of intervals，query if another interval is totally covered by
the list of intervals。
totally covered是指整个区间都被某些已有的区间 cover了。
比如如果有 list of intervals = 【（1， 4），（2，8）】
given interval【3，6】就被完全cover了。
然后扩展到design a system来做这个事情，可以query，也可以insert interval，假
设query操作的频率远远大于insert操作，并且interval的数量非常非常多。
onsite 2：
1. 有意思的题目1，设计Bi-directional LRU cache data structure，既可以lookup
key to get value，也可以lookup value to get key，还支持set(key, value)操作，
后面又加了条件，concurrent的情况下，会有什么问题，如何改进，假如set这个操作
的频率远远小于get这个操作的频率，需要写代码实现。
2. robot from topleft to bottomright LC原题，无障碍和有障碍
3. given a list of sets，find all pair of sets having any intersection
4. 有意思的题目2，设计caltrain system，要实现caltrain上车下车刷卡扣钱整个功
能，assume每个station都跟一个central server相连，要处理如果有network
partition怎么办，eventually车费还是要charge到账户上，但是不能影响partition的
station正常运作。要处理某些人下车没刷卡怎么办，followup可以非常多
5. 有意思的题目3，仍然是设计一个cocurrent环境下的time leased cache，但是有些
区别，假如delete操作是一个daemon thread来做不用太多考虑，但是get(key)操作的
逻辑是如果key不在cache里面，需要一个非常expensive的操作把对应value load进来
，如何让这个load的操作对同一个key尽量少发生，需要写代码实现。
这家的题目我觉得非常有意思，engineer都超级nice，感觉我见过的人的能力都非常不
错，年轻一点的反应非常快，年长一点的经验非常丰富。整体上看三哥并不多，虽然
engineering vp是三哥。
这家很有诚意，最后给我的base跟walmartlab差不多，再加上很难估值的option。他们
觉得他们的bar很高，能过他们面试的人不多，所以一旦你过了他们面试，要做好被他
们的recruiter不停骚扰的准备。
有关这个公司，在其他帖子里面我提到过，虽然engineering vp是个三哥，但是感觉还
比较靠谱，不像某些三哥吹牛没有边际，对于整个公司发展的前景比较有数，business
model也很promising，最近刚刚拿到一笔80M的投资。
############################################################################
###########
Palantir：
号称湾区面试最难的公司。但是again我运气比较好没有碰到很难的题目。我觉得这家
公司有点吹的过大了，本身做的东西根本没有什么技术含量，里面都是一群没经验的
stanford小年轻，都是自我感觉超好。另外去这家公司要做好准备每周工作60hours。
估值150亿了还给option我也是醉了，能上市不？我的看法就是这家公司基本就是坑，
从哪个角度来讲都不值得去。
他们的onsite上午会有3轮，然后中午吃完饭后会有一个小时的demo（因为实在没什么
意思所以我差点睡着了），如果上午过了下午还会有1 - 2轮，一般下午会有一轮
system design，另一轮是见hiring manager，如果上午没过demo结束就可以回家了。
电面：
万年不变的电面题，给一个array，问有没有duplicate
follow up1，只要index的距离 < k并且value相同就算duplicate
follow up2，只要index的距离 < k并且value的绝对值差 < d 就算duplicate
follow up3，follow up2能不能有time complexity O(n)的解？
Onsite：
1. OOD astroid game，就是飞机打石块的游戏，石块可以任意形状可以移动，飞机撞
上就挂了，飞机可以发射子弹，子弹打上石块会把石块分成多个小石块按照不同方向和
速度移动。要写伪代码。
2. 每个person有一个list of intervals，表示busy的时间段，问最busy的一段时间分
别都是谁busy。
3. 一个描述起来不算简单的题目，但是算法不难，在版上看到过但是细节记不清了，
好像是给一堆stock profile然后算profit
4. 一个2d matrix，被分成好几个区域，区域之间都是value为0的cell，每一堆
connected的非0cell算是一个区域，问和最大的区域是哪个，要设计API，怎么用json
return结果。
5. system design又是 distributed key-value store，万年不变的题目，后来没啥好
聊的只好跟面试官扯他们的那个atlas，distributed transaction layer，没办法想拿
offer跪舔还是需要的。
基本上每个面试官都是一副老子很牛逼的样子，一问他们到底做了什么牛逼的东西马上
支支吾吾说不出个所以然。他们的offer也没诚意，150k的base + 25k signon +
55000option，没谈就直接拒掉了。
############################################################################
###########
Dropbox：
Dropbox的面试题都是从题库出的，但问题是他们的题库并不大。所以，我可以负责任
的说，你在这个版上找到的面经题目，你在面试过程中绝对能碰到。另外他们复杂的算
法题目并不多，但是大部分是跟concurrency有关的问题。
一般标配是 2轮电面 + 6轮onsite，6轮onsite中居然有两轮是behavior和culture fit
另外，他们面试的要求都是要写能run的code，要写完整的solution，不能写个主要
function就完事。
电面：
1. 给一堆file，如何比较有效率的把内容完全相同的file group到一起，file可能非
常大
2. 被人面过无数次的电话号码转成string，然后再word break那个题目
Onsite：
1. log_hit(), get_last_5mins_hits()那个题目，concurrent怎么搞
2. token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如
果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样
用最简单的方法实现
3. web crawler，要分析可能的bottleneck，然后转化成concurrent运行的版本，写
runnable代码。
4. system desgin那一轮是两个三哥，轮流轰炸了一个小时，把我之前做的所有东西完
全推翻了，所以这一轮没结束我就知道肯定挂了。
############################################################################
###########
后面这三个公司是整个面试过程中给我感觉最好的三个公司。
Uber：
Uber的效率不是一般的牛叉。我从刚开始被Uber联系到最后拿到offer基本在一个周之
内搞定。面完了Uber之后真的有点心动，因为面我的人我觉得都很牛逼，人也都很超
nice，非常乐于提供很多关于Uber的信息，整个氛围非常积极向上。老板虽然是个三哥
但是也没有任何能吐槽的地方，他手下现在也基本都是老中。
电面：
一般电面会是hiring manager，除了问了一下之前做过什么之外只有一道题目：
OOD card deck，要现场deug，需要能运行
电面后一个小时通知我可以onsite
Onsite：
onsite一般是5轮，中间老板带着吃午饭
5轮中必然有一轮是只讨论之前做过的project，要做好准备，一定要对自己之前做的东
西特别熟
另外我面试过程中问了不少怎么设计一个系统解决Uber实际问题这种题目，很新颖很有
意思
1. 问了我不少关于storm的问题，比如storm怎么保证exact once/at least once
semantic，如何做timed window join，因为我简历上有相关的东西，然后让我用storm
来做一个比较简单的sliding window count。
2. big integer multiplication，要求现场运行代码。
3. longest increasing subarray，longest increasing subpath in a tree，path只
能从root到某个leaf
4. boggle game，given a boggle board and a dictionary，find all words on the
board，
follow up，如果dictionay 不变但是board不停的变怎么优化
follow up，如果board不变但是dictionary不停的变怎么优化
5. given a matrix only containing 1 or 0，find how many rectangles are 4个角
都是1
6. how to design a system to automatically detect hotspot on geo graph, a
hotspot is an area such that 打车的request远多于available driver的数量
7. how to design a system to detect if dispatch algorithm has some bug，
dispatch主要是收集所有打车request和available driver的信息然后决定哪个driver
哪个客人
Onsite过后两个小时通知我有offer了，如果onsite过后一两天之内没通知的话，基本
上说明你的waiting list上，要等排在你前面的人据掉offer才可以继续下一步。
############################################################################
###########
Facebook：
initial round我是直接去onsite的，但是根据其他朋友的经验似乎电面或者onsite影
响也根本不大，因为第一轮基本只要没有太大的纰漏都会过。
Onsite：
一共5轮，如果是4级的话会是3轮coding，1轮behavior和1轮system design。因为偏
infra, 所以我有3轮是三哥，当时已经做好挂的准备了。
1. move all 0s to right end of the array
2. decode way
3. binary tree inorder iterator
4. determine if there is a subarray sum to target number
5. convert integer to string，1000 to “one thousand”
6. system design - design facebook music system，只需要design service tier，
两个API
get_top_10_list_music_ids(int64 userid) - return top 10 most frequent
listened music ids for a given user last week. 这个call在load页面的时候要进
行，所以对latency要求比较高。
record(int64 userid, int64 musicid, int64 timestamp) - 每当user听一首歌，就
需要记录下来，这个可以asynch进行，需要eventually consistent，但不需要每听一
首歌马上就能反映到上一个call中。要做各种spec和resource的estimation。
7. 抄dropbox那个问题，get_hits_last_5mins(), record_hit()，但是后面又扯到
system design，如何thread safe，如果是districuted syste怎么搞，能想到几种方法
8. behavior那一轮基本上围绕着的主题是，你之前碰到什么难解决的问题，怎么解决
的，你学到了什么，production有过什么比较傻叉的bug，怎么避免的。你之前做项目
有没有cross team的，你怎么说服其他team听你的，等等。聊得过多导致最后没有时间
所有这一轮没有coding
我觉得我的运气很好，再次没有碰到很难的题目，尤其是算法。
############################################################################
###########
Google：
狗家如果真的想快的话还是可以的，我从开始被recruiter联系到offer也是一个周之内
搞定。
狗家和F家整个感觉都很好，面试官都很乐意帮忙，而且明显感觉到水平跟其他公司不
一样，技术功底非常扎实。
再次运气很好所以没有碰到很偏很难的题目，基本上就是水过了。其中几道比较有意思
的题目：
1. 一个正整数可以表示成其他几个正整数的平方和，给任何一个正整数，求最少的那
几个正整数，平方和是给定的数，比如14 = 1^2 + 2^2 + 3^2，如果给的数是14，应该
返回（1，2，3）
2. 给一个dictionary，然后可以support的query是，给一个string，返回在
dictionary里面包含给定string的所有character的最短的string
3. 如何设计google login system
4. web crawl的时候如何判断两个document是相同/相似的。
抱歉很多细节实在记不清了，表达能力也有限没办法在这个帖子里面说的很明白。如果
大家有问题我会尽我所能回答，谢谢。
