|
|---|
|
|
|
|
|
|
o******e
发帖数: 81 | 1 btw这个是俺的马甲
今天第一轮电面，我是experienced的不是fresh
感觉不怎么好，就问了一道题，太多detail了
电话来迟了8分钟，加拿大人。先问了问最challenge/favorite的project，说了几分钟
后他说我知道了，考你个题吧
很简单，Unicode的charactor array/string，找出现次数最多的char
我给了3个解，基本没有用任何考虑时间
1. double loop, O(n^2)
2. hash，他问我worse case，我一不留神说了O(n)，忘了hash的陷阱。他说恩perfect
hashing是不存在的，blablabla，我说我完全同意。我说如果space足够的话效率比较
好的char hashing是不太难的，他说anyway那也是O(n)，好吧。。
3. int[65536]的array，因为是unicode，我跟他确认了一下是2 bytes。我一开始说复
杂度的时候原来的solution是iterate string一遍，然后iterator count的array一遍
，突然想到可以用一个temp variable (key: count, value: char)来keep 当前的
maximum。这样iterate array就省了。我给他解释了好几遍他才明白，还问我为什么
local的maximum是global的。浪费了一些时间在这儿。
然后扩展问题，如果string length是100，用个solution。我说1，100*100 is
nothing。为什么不用hash，我说会pre allocate一些space，depends on hash table
的实现。
然后他想了会，好像没想到别的问题，那就再扩展一下。100M char的string，存在一
个file里，该机器有10个core/cpu，问我怎么办。
我说既然算法是O(n)的，这个program的瓶颈是IO，既然是single file，sequential
read已经是最优了，他说为什么，我说multi-thread会导致磁头来回seek磁道，反而更
慢。所以方法3已经最优了，因为counting相比read可不计，但是multicore就没有用上。
这好像不是他想要的答案，来回解释了一会我还是不知道他想要什么。我说如果不计IO
这个可以parallel，10个core分别做counting然后single thread merge，10个array也
就2M多不大。他问我为什么要merge整个array而不是local max，我说如果有分布不均
的话local max不一定是global max。
最后我也不知道这个是不是他想要的答案还是我没有想对方向？
还剩3分钟了他让我问问题。我问了几个比较personal的，他聊的还比较开心。然后说
HR会联系我的。 |
|
|
|
|
|
|
