总结

发信人: Sneijder10 (斯内德), 信区: JobHunting
标  题: 发点面经回馈下本版的帮助
发信站: BBS 未名空间站 (Fri Feb 27 16:11:53 2015, 美东)

从去年11月份开始，一直在本版向各位大牛取经学习。 最近刚刚接了M家的offer，job
hunting终于告一段落，虽然失败了很多，面试拿的也少，但对于一个非cs phd的背景
，已经很知足了。我背景是engineering，主要就是写code，做模拟，能转行主要是因
为学了些并行计算的东西，研究中写了大量的code，读了我们这个领域的一个famous 
open source code，从professional programmer里学到了很多实践经验。 虽然有些经
验，但实际找工作工程中大多数公司理都不会理我，Airbnb一个recruiter跟我说过一
些，大概意思就是说每天收到太多简历，对于非CS学生，仅仅从从简历上很难看出什么
， 所以非CS学生争取能多修几门cs的课，把keyword放上去。不然就像我一样，就是内
推也被拒或者石沉大海，这里面包括了很多本版好心的人帮我内推的，有ebay， 
linkedin, twitter, oracle 等。 在这里也想对帮助过我的人说声谢谢，以后我也会
帮助国人。

leetcode是从去年11月份yahoo是onsite失败后开始刷的，刷了一遍半，看了cracking 
the code的书，但是没有做每一道题，看了一部分algorithm的textbook， 在
careercup，glassdoor还有本版上找了很多面经。 Onsite 挂的公司有 Y家，G家，F家
, 电面挂的是Airbnb, 拿到的offer是 ServiceNow, M家, Bloomberg。 Wolfram的电面
了2个组，后来主动放弃了。 唯一的建议就是，如果你的dream company是FLG， 就好
好刷题吧，至少2遍， 而且是在纸上， 除非你是天才。。。 我错就是错在很长一段时
间都是在电脑上写了

每个公司面试的经历都不太一样，一家一家说说吧。 

Y家是去年11月面的mail组，都是阿三，但是考的题都不太难，主要当时还没怎么刷题
，很多data structure都不太熟，挂得很快，现在想来，真的很遗憾，感觉人家根本没
想难我，是我太挫了。。。 如果想去湾区，去不了你的dream company，Y家应该是一
个很不错的选择，从本版的反馈，Y家是可以学到很多知识的，而且他家现在想翻身，
很努力的再招各种talented people，文化也再改变，我在纽约部和manager谈的时候，
他就说他们想找new brain，是不是cs并不重要，所以非cs的同学都可以试试。

G和F应该是bar最高的，毫无疑问，G和F都没有过hire committee， 几乎同一周拿到的
拒信，G是recruiter打的电话，F是一封邮件，那一周真是心都碎了。。。 G家面试是5
轮，说好了有一轮要谈research，但最后还是做题。面试官都挺屌屌的，不过这么多面
试官里，可以很明显的感觉到G家的面试官基本功最好。 F家的氛围我是真的很喜欢，
很active，人也很nice，拿到面试也是多亏一个朋友内推。 面了4轮，有一轮design，
一轮culture fit，两轮做题，感觉题目不算太难，但是简单不代表就好过，感觉是挂
在了一个在家里做过2遍的题目， 说明有些题自己还是理解不够深刻， F家挂了后， 
痛定思痛，总结了下自己的问题，发现自己在准备的过程中犯了个严重的错误，code都
是电脑上写的，之后就立即在纸上写的，感觉效果很明显。

Airbnb 是苦苦求来的电面， 他家recruiter发信拒了后，我又回了一封扬扬洒洒的信
，解释为什么我不是cs背景，但也能写code， recruiter人很好，聊天通过后给了我电
面，面试的题目头一天准备到了，但是我傻逼，最难的一个corner case没有考虑，结
果导致写的算法根本没用。。。 显然最后就。。。 挂了，唯一一个挂掉的电面。 

servicenow和wolfram面试方法有点不一样样，servicenow第一面是做project，写一个
网页游戏，二面是remote在对方的ide上debug，修改程序。 运气不错，都顺利过了。 
onsite就是聊天，但可惜因为自己背景非常不match，虽然有一个engineer力挺，但是
manager不太看好我，给了个我在本版看到过的最低offer，后来那个engineer还跟我说
如果以后过得不开心，可以再联系他。 这家公司也是本版一个id给我内推的，真的很
感谢他。 其实他家现在发展趋势非常好，看看股票就知道了，本来我是想好了只要给
个standard package，哪怕match不了其他家，也去了，最后没能去成湾区真的很可惜
。 

wolfram电面了2个组，因为我research做了很多并行计算，所以有一个组想要我过去做
那块，另一个组是搞customer support，但比接电话的高级点。。。 说好听点的就是
consulting， 电面后丢给了我一堆题目做，要求用wolfram lang， 花了一天才做了一
题出来。。。 因为比较想去西海岸，所以最后就放弃了。 

最后就是M家了，话说M家的面试也不太好拿，至少2个人帮我内推过，都没音信，最后
我是在软软家网页上找到了管理我们学校这片区域的campus recruiter的联系方式，于
是又一封扬扬洒洒的信丢过去，第一轮电面秒过，直接跳过了campus onsite，去
seattle了，面的是office组。 这次面试应该是我准备最好一次了，也就是F家失败后
面，当时手上剩下的唯一一个onsite。 我是国米球迷，当时就想，小国际你赢一次吧
，哥这次就过了，结果那周小国际赢了，西雅图也几周第一次放晴（记得那个说下雨抑
郁的帖子么？我面试那天是第一次放晴哦，都是命。。。）面了４轮吧，都是白人，人
都挺好，题目平均难度不大，但是方差比较大，有的感觉比ＧＦ面的都还难，还好人品
爆发，都做出来了。第二天坐飞机回家，起飞前收到servicenow的口头offer，下飞机
就收到了软软家的口头offer。 

本来想着就这么结束了，没想到bloomberg最后时候给安排了面试，process 很快，连
续2天campus onsite，前些时刚去总部面，话说他家真的是高大上，各个高富帅，白富
美，和西边的文化简直一个天上一个地上，不过呢，你还是能很轻松的就看出谁是sde
，谁是搞金融的，哈哈   bloomberg的面的就比较轻松了，campus onsite做题，
onsite就是和manager聊天，因为我做过一个android app，一个小的practice，那
manager正好也懂，就问了我好多android的问题，可我大概有半年没碰了，当时写也是
各处查api，一下答不上来，搞的自己好囧，所以我觉得，简历上写的任何东西，真的
是要好好准备，说不清楚最好还是不写。后来manager出了一个ood，大概写了几个
class，他应该知道我没有找枪手写app，就让水过了。他家recruiter知道我已经有M家
offer后，很sweet的加速了过程，面试2天后就收到正式package，但仔细想了后，还是
决定去投奔软软了，至少病了可以找格蕾看看病哈~~~ LOL

说了这么多，希望能给很多像我一样对coding有passion的非CS phd同学一些经验。最
后上面经吧，因为签了NDA，题目就不一一针对公司了，混在一起，记得清楚的多给点
细节，记不清的就给个key word了。 请多多包涵。 哦， 版上不是经常都有各种讨伐
面试官的帖子么，现在回头一想，发现自己答得不太好的还真都是国人出的题目，难得
全白人的时候， 就都过了。。。 在这里我也不是想说国人出的就多难，至少我没答好
的那几题也还好，也许就是这么运气不好吧。。。 把自己变强才是王道啊


1. Return true or false whether a expression has extra parentheses 
eg.  1 + ((2+3)) 

2. Valid parentheses  很多follow up， leetcode上相关的都做一边就好，最后一个
follow up是user defined parentheses, the input can be very very long

3. Least common ancestor of tree nodes a & b

4. Search a number in a matrix. In the matrix, each row and the col are both
in ascending order. Write an efficient algorithm  在cracking code上看到过这
题的思路，现场运气不错，居然写出来了

5. add two string

6. LRU cache

7. Parse CSV. Please pay attention to all corner cases. You can google the 
CSV format

8. Find the second smallest number with one pass

9. Add node in a linked list

9. Kth largest number in a BST

10. Dot product of a sparse vector. Follow up, what you can do to improve 
the efficiency if a vector has millions elements, and the other is very 
small. 

11. two sum

12. single number

13. Use quicksort to find the median number. Use two heap to find the median
number in real time

14. Use vector to realize queue

15. Linked List Cycle

16. Build a trie for strings like (cat, cats, ...)

17. Using iterative method for in-order traversal

18. Tiny URL， 谁都知道算法，但是还会问到很多server方面的， htable之类的，这
个我是真心不太懂

19. 有一题类似minimum window substring 但简单了很多， 记不清了

20. rotation of a vector (in place) 

21. OOD for a mail folder structure. 类似的还有，你有一个系统可以把公司分类
到各个不同的category，点每一个category都可以看到公司列表，展开这个category，
底下还有sub-category,  一个公司可能属于不同的category， 如何实现insert , 
delete, 或者update  要考虑各种scale的问题。 总结下，其实就是要建几个class，
用trie结构。

22. stock problem, one transaction, two transaction...

23. largest sum of a contiguous array  eg: (2, 3, -1, 2, 4, 2, -8) 

24. 很多圆，重叠在一起，如果算圆所占的面积，可以有一定误差

25. same tree，subtree



祝愿还在找工作的都能找到中意的offer

G onsite 2015/02/09

from here

斗胆面了谷歌，小弟很弱，不出意外挂了，因为每轮只面我一道题。

1. 给你一个target number，和一个list，list里面装的都是整数。问是否能用list里面的所有数字，只用四则运算和括号之类的，问能不能得到target number。很像24点，不过是它的扩展。
2. 给你一堆input，每一个input是一条边，表示谁和谁是朋友，例如
1 - 2
3 - 4
4 - 5
要求找出所有的groups，每个group里面的人认识，group和group间的人不认识。如上面的例子，返回 {1, 2}, {3, 4, 5}
3. 先讲了半天什么事profiling。所谓的profiling是指一个程序，里面有许多函数，我们记录每个函数什么时候开始执行，什么时候执行结束。输入就是一堆entry，每个entry有：函数名，时间戳，开始执行/执行结束，例如：
main 0 ENTER
foo 5 ENTER
foo 50 EXIT
bar 60 ENTER
bar 90 EXIT
main 100 EXIT
输出有以下要求：1.按照CPU执行的顺序来显示结果。2. 若一个函数a里面调用函数b，函数b要求缩进。
main 100
foo 45
bar 30
4. 给两组点，第一组的点都在圆上，第二组的点都在圆外，从第一组里面和第二组里面分别找一点，这两点之间的距离最小。

小弟技术浅薄，经验少，估计要挂了……希望各位大大集思广益~

FB面经

发信人: tdscdma (tdscdma), 信区: JobHunting
标  题: FB面经
发信站: BBS 未名空间站 (Mon Feb  9 17:47:01 2015, 美东)

FB已挂，上面经。
Round 1: 1. Given an array, find the max drop. Buying stock 的变种。buying 
stock是找最大的increase,这个是找decrease.
               2. Build BST from an array. leetcode原题。
               3. Combine logs. 一个用户可能有多个log, log1, log2, log3, 这
些log之间有相同元素，combine所有相似log. 给了两个解法，建graph找connected 
components, 和iterative. 最后就写了iterative, 有个小bug, 改了。

Round2 . Behavior＋coding. 1. Find island number from an matrix. (1 is 
island). 我说见过，或者DFS/BFS, 或者pattern match.
                              2. Read 4k. 我说见过，然后说了一下解法
                              3. 3sum from 3 different array. 原题变种

Round3. 1. Best time buy stock...
              2. sqrt(float x). 现场泰勒展开推了牛顿公式。
              3. 一道很复杂的multiple weight BST,非常长. 给了两个解法，一个
用splay tree, 一个traditional method + cost function.

Round4. News feed backend design. 画了框图挨个解释，什么2PC, vector clock, 
LRU, DHT全说了，还解释了一下paxos。然后估算各种pull, push时间，被老印否了。(
我哪能知道怎么算具体数，最多说个大概方向)。

然后就跪了。目测老印给了very negative feedback. 最后他都不想和我握手。。。

G家ONSITE

from here



第一题, 找出一个二叉树的最深节点。

这个题目实际是送分给我的。结果我太紧张，用递归函数完成算法，但是把返回最深节点程序写成了返回最深深度。后来考官提醒我不对，我方寸有点乱，推翻全部递归算法，重新用DFS写了一个非递归算法。结果虽然正确，但是过于复杂。后来想了想，其实这个问题稍微修改一下原有递归算法就好了。面试官是个老白，人还算NICE。




第二题，一个LIST里面放了很多句子，找出每个句子共同的PREFIX。这个问题不是很难，我写了个比较函数，然后依次比较每个句子。考官问我算法效率，我说是LIST长度乘最长的LIST单词长度。 他问我有没有更好的算法，我说可以先扫描LIST,找出最短的句子，以它为初始比较，可以减少比较次数。面试官感觉是个东欧白人，比较NICE.




第三题，设计一个 KEY-VALUE机制，必须在O(1)做下列操作: 插入，删除，get(),random_get（）,可以使用hashmap.

这个题目非常tricky. 貌似可以直接使用一个HASHMAP就能完成，但是实际上random_get必须把每个K-V对与一个0到N的整数关联，这个如果直接把MAP放到一个LIST里面去，算法效率就变成了O(N). 我最终使用了两个HASHMAP来实现这个功能，一个HASH表记录0-N的整数下标与KEY的关系，另外一个HASH表记录K-V，还有这个下标。这个算法其实在删除时也有问题，因为删除后会有下标GAP.我实际上是使用了一个机制，让删除操作，每次只删除HASH表最后那个K-V值（之前让最后值与删除值换个位置）。面试官是个亚裔小年轻，非常NICE.



第四题，找出一个GRAPH里面全部的三角形

我的算法： 先做一个访问队列，从一个节点开始BFS遍历，每次把一个节点的所有未访问过的邻居点放入一个LIST,判断这个邻居LIST里面有多少点互相连接。这个就是与这个节点有关的三角形，对它们计数并把结果记入累加器。之后把这个LIST加入队列，继续遍历。累加器最后返回三角形总数。

这个面试官是个三哥，态度很糟糕。似乎看不懂我写的算法，问了很多莫名其妙的问题。估计他给我的REVIEW很差。请各位大神看看，我的算法确实有问题，还是三哥有问题。


第五题 字符串PATTERN MATCH。 一个P字符串 ，一个S字符串。P中下划线 "_"字符通配S的单个字符，"%" 通配S中任意长度字符。

我的算法出现了一个问题，P字符串“ABC_AB%AB"与S字符串 "ABCXABXXXXABAB"这样的匹配，我报FALSE,他说正确的应该是TRUE.

修改过程没有完成时间到了。




好了，情况就这些了，祝各位好运！




补充内容 (2015-2-8 15:46):

这次G家先前电面了我两轮，都比较顺利。后来G出机票让我来ONSITE，题目我没有我想象的难，没想到没过，略有些失望。我不是科班出身，编程和算法都是自学的，没有工作经验应该也是FAIL的原因之一

面试经历

发信人: goodluck0 (goodluck), 信区: JobHunting
标  题: 分享面试经历
发信站: BBS 未名空间站 (Sun Feb  8 03:23:38 2015, 美东)

fresh phd找工，最近面了几家公司，分享一下面试经历，希望对近期找工的同学有所
帮助。Disclaimer：下面针对各个公司的描述是基于自己的经历，不一定可以
generalize。

Google

题目：这几个公司中相对最有挑战性的，但其难度也远没有超过leetcode，leetcode原
题少，变体多，代码量相对大。
要求：可以有bug，但尽量自己指出或者被指出后能立即更正，最终代码需要保证100%
正确。
安排：无电面，onsite 5轮（4轮coding + 1轮phd thesis）。部分coding换成system
design也有可能。
特点：1. 题目常常条件不足，需要自己问清楚。2. 需要检查输入是否有效。3. 考了
一点很基础的物理和数学知识（嵌入在了题里面）。4. 写完代码喜欢进行一些有意思
的讨论，比如code的某个分支在什么情况下会被调用，比如已知输入的范围哪些语句可
能出现buffer overflow以及如何解决。

Facebook

题目：多leetcode原题，难度一般，代码量不大
要求：尽量无bug，特别是简单题，但有bug也不一定就会挂
安排：电面一轮，onsite 4轮（2轮coding + 1轮system design + 1轮聊天/coding）
特点：1. 需要检查输入是否有效。2. 每个题目代码量不大但尽量多做几个

Twitter

题目：一半leetcode原题一半变体，难度一般，代码量有大有小
要求：可以有bug，感觉不太严格，我自己觉得还有bug的时候面试官说这样就可以了
安排：电面一轮，onsite 5轮（全coding）
特点：1. 题目well defined，可以假设输入有效。2. 问了好几个关于数据结构以及涉
及到interface design要求写clean code

Airbnb

题目：难度一般，很多字典和字符串的题目，多leetcode变体，代码量相对大
要求：在电脑上写，能把给出的不算刁钻的test case跑对
安排：电面一轮，onsite 6轮（3轮coding + 1轮project deep dive + 2轮culture
fit）
特点：1. 面试官把标准答案记得很清楚，需要在写之前把思路细节讲清楚并优化到最
优，能少用一点空间就少用一点，即使不能在数量级上产生影响。2. culture fit很独
特但也没有十分刁难，喜欢了解他们商业模式，爱学新东西，有common sense的人

Uber

题目：难度简单（取决于组和面试官）
要求：按照面试官喜好，有让电脑上写也有白板的
安排：电面一轮，onsite 3轮（2轮coding + 1轮system design）
特点：面试难度方差很大

Quora

题目：题目跟Google的难度差不多，一半leecode原题，代码量有大有小
要求：可以有bug，但尽量自己指出来或被指出后立即更正
安排：电面一轮，onsite 4.5轮（4轮coding + 0.5轮聊天）
特点：1. 题目well defined，可以假设输入有效。2. 算法题居多，每道题都要分析复
杂度。3. 有一轮practical interview，关键考点是能否较快用grep扒一个不熟悉的
code base

Square

题目：难度一般偏简单，glassdoor上原题重复率高。
要求：在电脑上写，能把给出的不算刁钻的test case跑对
安排：电面两轮，onsite不知道因为最近不招人
特点：code写好就行，不关心复杂度

Dropbox

题目：难度一般，有的题目很tricky
要求：据说很高，做对题目也会挂
安排：电面两轮，onsite不知道因为第二轮电面挂
特点：1. 偏重系统。2. 有tricky题目。

高频考点
请参考leetcode和本版面经对号入座

- LRU cache
- 各种花式数据结构的Iterator
- Trie。实现hasPrefix()和getWords()
- 字符串字典题目
- 各种数求和，three/permutation/combination/subset sums，考虑是否可重用，是
否unique
- DFS/BFS
- 2^n iteration + bit operations