Good面试总结

发信人: Mitan009 (aha), 信区: JobHunting
标  题: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Wed Dec 10 22:21:18 2014, 美东)

基本都面完了，前一段刚注册了一个帐号，上来发文，大概说下自己的经历，抛个砖头
，希望对大家有用，也祝愿大家都能找到满意的工作。有NDA就不说onsite具体题目了
，感觉也没什么必要说，会大概说说面到的知识点，可能比较乱，大家将就着看。

基本情况：fresh cs phd, 找的都是SE的工作，为啥不找教职或者research lab这里就
不讨论了. FLGT(2 offers, 1家withdraw, 1家简历被刷), startups UPASD(2 offers,
2家电面挂，1家没申请)
pros：背景还不错，都是top school, GPA高。。(fresh貌似公司还是会稍微看看这个)
cons: 没有intern经验是硬伤，PhD期间，上完课后代码写得不多

package还没开始谈，initial offer都差不多200k+的样子，大公司hr明确表示等我都
面完了可以谈, startup感觉不好谈。LD目前在一家大公司，说其实先去大公司几年也
不错，比较稳定，貌似股票refresh也可能不错，work/life balance比较好。我自己是
想去startup, 但是究竟现在去还是大公司里先办绿卡，积累几年经验再去，也是有些
纠结的，目前倾向于去其中一家startup，主要concern是hr说主要办Eb2，绿卡可能不
方便走EB1b，另外package也希望能谈高一些。

准备：周围同学有准备1，2天coding就上的，我主要是平时代码写得不多，coding要热
身一下。programming exposed和cc150看了一遍，没有动手写，leecode动手写了，半
年前过了一遍，找工作前又过了一遍。Research也简单准备了下，怎么说high level
idea, 我自己没怎么讲details, 感觉面试官都会问下potential应用之类的问题。
design看了下几篇文章，知道个大意，google的mapreduce, file system, big table,
fb的memcache, unicorn。其他看到过的觉得还不错的design资料，最后一个常见题目
汇总可以过过看，很有帮助:
http://blog.csdn.net/v_july_v/article/details/7382693
https://www.youtube.com/watch?v=-W9F__D3oY4
http://www.mitbbs.com/article_t/JobHunting/32741713.html
另外建议稍微准备下常见数据类的写法(包括generic programming), 我倒是没碰到其
他一些concurrency, database, NP-hard之类的题目.

如果说有什么经验教训的话，我个体采样样本感觉就是要找refer!
我的offer都是找refer投简历的，1家大公司免了phone interview. 2家startup面试的
时候面试官都超级热情, 相反两家电面就挂了的startup是自己网投的，可能是对比强
烈，明显感觉得出面试官语气比较冷淡, 谈话会让人略微不舒服，也可能是我自己修为
不够，
题目倒不难，没想到结果是据信(1家说不match,1家不给feedback)。

面试时，对不同的部分我的基本步骤是
1.coding:
(a) 先确保理解了题意，然后一边想一遍描述思路，coding前和面试官confirm，这时
候要是面试官有其他想法会和你交流，或者给你hint，从中你可以大概知道他们脑子里
预定的解法.
(b) coding
(c) test case (corner cases, negative&positive cases。。。): 一个是确保你自
己写对了，没有粗心之类的错误。另外有时也是一个考察点，这个看时间，大概说说其
实也可以，也有些面试官会直接说不用了，挺好的。

2.design: 其实这部分我没怎么准备，基本就是凭感觉和常识扯蛋，面试前很紧张这部
分，其实后来觉得这部分大多数面试可能都是表现不错，和面试官聊得很开心，可能是
对fresh要求不高吧。我自己给自己定的步骤如下
(a) 分析需求和给个要考虑问题的outline: 可以画画大概前端，后端之类的，然后数
据流啊啥的，这个时候我一般是针对问题本身，但是会提到scale的问题作为一点以后
讨论，不过有的时候scale小和大的方案会不同，所以中间会有一些back and forth.
(b) 根据outline预留的问题开始一个个讨论解决方案, 比如算法，数据结构，
tradeoff.
(c) 一般会有一个估算的问题，比如这个问题多少用户，数据多少字节，算法处理时间
...不确定的数据可以问他是否这个估计make sense.
(d) 根据前面的估算，小scale的时候一个机器就可以解决(不同的问题可能要考虑
cache, memory, disk, cpu)；大scale的时候怎么办？vertical/horizontal scaling,
数据怎么partition, load balancer, index server, backup for single-point
failure, consistency, sharding。。。。。知道什么说什么，可能是fresh, 面试官
倒是没大追根究底为难我.
(e) 只有一家公司让我最后编程实现一个核心的算法，不难，不过这时候时间不够了，
最后就是一个伪代码的思路.

3. 面试调适：要是以前没有面试经验的new grad, 第一次电面或onsite可能会紧张，
我自己挺紧张，不过多面几次就适应了. 另外, 我有两家公司onsite是所有面试都在下
午，要是前两轮太兴奋的话，到后来可能会比较疲劳，中间需要的话可以问面试官稍微
休息下，上个厕所，喝点饮料啥的。

面试伪面经：
公司A：
电面(华人马内基：needle in haystack, sqrt(double)：binary search, 因为是
double需要考虑精度，然后boundary细心些)
onsite:
1. 小印：edit distance简化版，用双指针iterate，中间让我做了几个小改进，比如
constant space(我偷懒，没有iterate到底); 数组里找数，binary search的经典题,
当时还剩10分钟，还要留5分钟问问题，小印让我只描述算法，当时犹豫了下要不要快
速写掉，
但是怕一急出bug; 应该最后没难为我.
2. 华人马内基: expression matching类的经典题, recursion和dp的方法各写一遍，
分析复杂度
3. 东欧人: design常见题
4. 老美: thesis research + 最后5分钟1题小编程...

公司B：免了电面
onsite: 这家一般是白板，但是那天拿了一台笔记本给我用，不过我怕新机器打字不习
惯，还是白板。
1. 华人：几何直线常见题，略微变形：没啥算法，数据结构用hashmap就可以了，直线
的表示我用了点斜式，面试官想让我用斜截式，省一个返回参数，其实一样，最后
output返回直线的时候，转换一下就好了。cache的设计: 我扯到了这是一个online问
题，解决hit，miss，很多heuristic, 常见的是LRU, 有一个所谓的理论保证, 然后实
现思路，数据结构，算法，没让我写.
2. 老美： design
3. 老美： 排列组合常见题，有略微变形，用recursion, backtracking就可以了
4. 不明国籍美女： thesis research，面试官超短裙。。hot。。
5. 前苏联加盟共和国： 常见题 binary search; sorting相关的题目，但是需要
linear time, 要么heap，伪代码实现了下，要么用那个NB的5个一堆的quick sort，后
一个我说了算法，没让我证明和实现. http://www.cs.rit.edu/~ib/Classes/CS515_Spring12-13/Slides/022-
SelectMasterThm.pdf

公司C：
电面：华人校友 两道tree的问题；第二题没时间了，就描述了思路, 太久了，忘了题
了，记得不难.
onsite:
1. 华人：实际问题，没有什么算法，但是数据结构要想下，用到一个固定长度array的
循环查找更新；
2. 东欧人：实际问题，本质是给定会议起止时间，最多需要几个会议室的问题，然后
有一个扩展是海量数据，需要按照时间partition怎么办，因为一个会议可能跨越多个
partition，有个小trick, 需要不同partition间传递参数.
3. 老美： dp经典题目，不难；还有一个类似log hit的实际问题，描述思路，没让写
code.
4. 华人： design常见题

公司D:
电面：华人校友 recoverBinaryTree from preorder and inorder，需要在网上运行程
序，写test case时需要顺便实现tree的traversal.
onsite:
1. 老美： 一个简单的数据结构类，需要用generic programming
2. 老美： DP问题，就是直线上jump的经典问题，但是加了扩展，有速度，有限的加速
度，需要小心构造dp的表格，其实本质一样，然后描述下扩展到多维的情况。但是。。
。。面试官觉得dp太复杂。。。。然后我写了recursion，但是说这个要exponential，
然后就僵持了，我说你让我用recursion但是还要polynomial time，这个怎么可能，那
我肯定要存中间结果啊，那不就是dp么，中间略过我快崩溃的不知道多久时间，然后面
试官说你phd啊，本科的东西忘了呀，memorization, 我瞬间明白他要让我存中间输入
参数到输出结果的映射，说了下，宾主尽欢。。他说dp的dimension不好，用hashmap是
linear的结构，简单明了，我只好狗腿的附和。然后电脑上写个简单的code，test
3. 华人： thesis research， 问了一道图的遍历的题目，电脑上跑code
4. 老美： 给了个实际问题，其实最后转换下就是字典查找的问题，可以直接比较，
linear time，但是如果海量查询的话，还是先把字典建一个trie tree, 然后让我实现
trie tree的查找，不用construct.

公司E和F电面：
马内基: 电话聊天
越南人:类似tree traversal的问题，输出root到某个node的路径.
华人: 给一个file system, 让找到里面文件内容一样的所有文件，分开存储返回文件
路径，比如输出vector<vector<string>>, inner的vector里存同一个内容的所有文件
路径，给了几个辅助函数，isfile判断是否文件还是文件夹，readfile是一个读取文件
内容的函数. 我假设文件读出来的是string, 用了tree traversal+hashmap做的，不知
道是不是有其他方法.

发信人: Mitan009 (aha), 信区: JobHunting
标  题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Fri Dec 12 01:58:59 2014, 美东)

上面部分没有具体说的题目真心不难，其实Leetcode上的题目真正理解了肯定没问题，
我列下类似方法的题目或者变形(绝大部分对应leetcode上的题目，有些是实际问题背
景，稍微转化下就是了):
One Edit Distance
Binary Search in Rotated Sorted Array
Sqrt, Power using binary search
Regular Expression Matching
LRU
Max number of Points on line
Combination Sum
Decode ways
K-th biggest/smallest number in unsorted stream/array
Log hit类题目
给定一个string，在字典中查找共同前缀最长的单词
判断树是否BST, 是否symmetric, root到最大值节点路径
判断图是否bipartite,判断有向图是否tree


发信人: goodluck0 (goodluck), 信区: JobHunting
标  题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Fri Dec 12 02:21:34 2014, 美东)

公司B是google吧，这段时间google给不少PhD免了电面


发信人: Mitan009 (aha), 信区: JobHunting
标  题: Re: 我的面试总结(FLGT+UPASD)和伪面经
发信站: BBS 未名空间站 (Mon Dec 15 23:28:09 2014, 美东)

不敢当，我只是fresh屌丝而已。。
常见题链接： http://www.mitbbs.com/article_t/JobHunting/32741713.html
我觉得版上几位大牛总结比较好，你搜搜system design之类的就有了
另外，我总觉得fresh和experience这一块的要求应该不太一样，fresh的感觉common 
sense之类的对头，然后对scalability之类的问题有个大概的概念可能就差不多了
【 在 njusz (sz) 的大作中提到: 】
: 大牛能不能具体说说design的常见题和准备方法