骑驴找马结束,分享面试题回馈贵版

原帖地址:mitbbs

为了防止违反NDA,就不列出公司名了,就是一些常见公司。

1. Write a iterator to iterate a nested array.
For example, for given array: [1, 2, [3, [4, 5], [6, 7], 8], 9, 10]
call iterator.next() 10 times should return 1,2,3,4,5,6,7,8,9,10.
用了stack存(array, index)的tuple。

2. LeetCode 原题,120 – Triange。有一点变种,给的是一维数组。

3. Implement HashTable 主要看dynamic expanding

4. Implement MaxHeap.

5. Topology sort,就是版上常见的给一些排过序的未知语言的词,求该语言的字母序
。要求实现核心算法。可以给出一些helper function定义不需实现。

6. LeetCode 付费题 157 & 158 – Read N Characters Given Read4()。提供int
read4(char* buf),实现int read(char* buf, int len)。read4函数读至多4个字符,
除非EOF,并返回实际读到的字符个数。题没有难度要注意一些细节问题。

7. Given an array with length n + 1. The array contains numbers from 1 to n,
with one of the number duplicated. Now find the duplicated number.
讨论各种解法以及时间空间复杂度,最后实现O(N)时间O(1)空间的解法。数组可以
mutate.

8. Given a bag of characters and a dictionary, find longest string that can
be constructed.

9. Given a grid of characters and a dictionary, find all possible words from
grid.
以上两题都用的标准Trie树解法。讨论复杂度,和优化方案。

10. Given a grid with 'o' and 'x'. Find minimum steps from top-left to
bottom-right without touching 'x'.
a) You can only move right or move down. (BFS or DP)
b) You can move in all 4 directions. (BFS)

11. CS basics. Thread & Process, address space, how memory mapped file works
, etc.

同时感谢版上大牛们的内推:mitbbsfanfan, xjm,虽然都没有去成…

最后祝大家找工作顺利!