近期的一些面经

原帖地址:mitbbs

找工作告一段落,把前一段面试的题目整理一下一起发出来。各个公司的放在一起了,
包括flu亚麻等。有店面也有onsite。

1. LRU cache
2. 一个整数数组,先递增然后递减,也有可能只有递增或者递减。查找某个整数在不
在数组里。
3. 设计Boggle游戏
4. OO design, 用树形结构表示表达式。注意operator要用多态实现。
5. 2 sum,一个元素只能用一次

6. 1)判断一个数组中是否有3个元素和为0,元素可以重用。2)merge k sorted
array。3)稀疏向量的点乘。
7. 一个数组,把非0的元素移动到开头。
8. 1) maximum subarray 2)树里两个节点的最低公共祖先 3)LC subset
9. 设计fb newsfeed
10. 大数相乘

11. 1) 给一段话,再给两个单词,求这两个单词在这段话里的最小距离 2)打印二叉
树(level order遍历)
12. 随机洗牌算法
13. 1)给一个字符串,返回每个字符及其个数。比如:aaabcc-> 3a1b2c 2) 给字符及
其个数,返回原本的字符串 3)median of an array,有哪些方法,如果数据太多内存
装不下怎么办
14. 用一个m*n的矩阵表示一副图片,其中每个元素对应pixel的灰度。Smooth the
image with m1 * n1 scale。也就是每m1 * n1的矩阵里面的值求平均,放到中间的那
个像素里。如何节省内存?
15. 一个server,多个client。client给server发任务,每个任务带有过期时间。
server要按顺序处理这些任务,直到该任务做完或者被取消或者过期。实现提交,取消
和查看任务状态的API。

16. 二位数组的Zig zag traversal
17. 一个数组长度未知。如果访问超过长度的index会产生out-of-bound异常。查找某
个元素,如果不在数组内则返回-1
18. 给出左下角和右上角坐标,画出矩阵
19. 如何检测数据库的死锁
20. k-means算法实现

21. 一个数组有n+1个元素,每个元素都在1到n之间,只有一个元素出现了两遍,找到
这个元素

几点感受:
1. bug free很重要,但是不是决定因素。我有的题目有小bug是面试官指出来的,但是
还是给过了。和面试官的交流应该更重要。
2. 面试的级别越高,design的比重越大。
3. 在本版收获很多,面试也遇到了很多中国人,都很友好和帮忙。在此一并感谢!