微软onsite面经# JobHunting - 待字闺中
s*c
1 楼
刚从微软onsite回来。 当天面试了6轮,从11点直到下午6点,最后都快撑不住了。有
一个算法问题,都不太难,但有很多open design的问题有些难度。我记得的问题有几
个:
1. two arrays of strings A and B, find intersections, union, A-B and B-A.
如果array小于mem size,我的思路是: scan A array, 建立hash table; 然后scan
array B, 对每一个元素
检查是否在A 的hash table存在。在白板上code实现。
如果array 大于mem size, 导致hash table也大于mem size, 则对每个array做
external sort:
把array分割成多块,每块都小于mem size, load到memory, sort, 写回disk;然后
merge sort.
之后,顺序扫描另个array,比较每个元素是否相同。
面试官还问,如果用SSD,该如何改进。我的答案是建立index table,但这是把index
table存在SSD里。
2. 不断从一个stream里读数据,找到最大的K个数。就是用一个大小为K的min-heap就
好了。但是要求
写code 实现min-heap的插入/删除操作。
3. 一个超大文件(many TB), have 1 GB memory. 如何设计一个cache,主要目的是
缓存最近访问过的
数据。本质上就是一个LRU list加上一个hash table。用文件的offset做key来查找
hash table以找到
访问过的数据记录。在数据记录里要包括一个refence count来标识当前active的数据。
同时要更新LRU list。当memory不够用时,要evict一些缓存的数据。
4. tow single linked-list, see if they converge。我用了career cup上典型解法
,后来在面试官提醒下才发现还有更好的方法:
traverse list 1, note down last node;
traverse list 2, note down last node;
it the two last nodes are identical, converge
(2) find converge point。这个不用多说了吧。
一个算法问题,都不太难,但有很多open design的问题有些难度。我记得的问题有几
个:
1. two arrays of strings A and B, find intersections, union, A-B and B-A.
如果array小于mem size,我的思路是: scan A array, 建立hash table; 然后scan
array B, 对每一个元素
检查是否在A 的hash table存在。在白板上code实现。
如果array 大于mem size, 导致hash table也大于mem size, 则对每个array做
external sort:
把array分割成多块,每块都小于mem size, load到memory, sort, 写回disk;然后
merge sort.
之后,顺序扫描另个array,比较每个元素是否相同。
面试官还问,如果用SSD,该如何改进。我的答案是建立index table,但这是把index
table存在SSD里。
2. 不断从一个stream里读数据,找到最大的K个数。就是用一个大小为K的min-heap就
好了。但是要求
写code 实现min-heap的插入/删除操作。
3. 一个超大文件(many TB), have 1 GB memory. 如何设计一个cache,主要目的是
缓存最近访问过的
数据。本质上就是一个LRU list加上一个hash table。用文件的offset做key来查找
hash table以找到
访问过的数据记录。在数据记录里要包括一个refence count来标识当前active的数据。
同时要更新LRU list。当memory不够用时,要evict一些缓存的数据。
4. tow single linked-list, see if they converge。我用了career cup上典型解法
,后来在面试官提醒下才发现还有更好的方法:
traverse list 1, note down last node;
traverse list 2, note down last node;
it the two last nodes are identical, converge
(2) find converge point。这个不用多说了吧。