Linkedin实习两轮电面

原帖地址:一亩三分地

第一轮面了两道LeetCode原题。第一题是Repeated DNA Sequence,貌似面试官一定要最优解法,也就是必须encoding,并且是1-A, 2-C, 3-G, 4-T这样,顺便考了下bit操作。他还反复的问为什么要用HashMap不用array,HashMap会不会blow up,以及一些基本概念比如Java int的范围等等。第二题就是level order traversal,正着反着都写了一遍。两天后通知进入第二轮,然后就是噩梦的开始。第二轮是一个印度大姐,上来直接开始做题,她出了一道好像是她自己刚刚想出的题… 设计一个generic class,要求支持add(T), remove(T), randomRemove(T)三个操作,并且必须保证都是O(1)。比如说add(cat), add(dog), add(pig), add(cat), remove(cat), remove(dog)等等,她还特意说必须要考虑重复,也就是说删掉一个cat后另一个cat必须还在,而且randomRemove()必须保证所有元素被删掉的概率均等。
我当时觉得这个有点像LeetCode上的LRU cache,就说准备用HashMap + Double linked list。HashMap存(element + arrayList of the double linked list node),之所以arrayList是因为要考虑重复,要double linked list是要保证单位时间能删除。她让我解释为什么这样做,然后说你可以开始写了。我把add和delete写好,期间被她各种challenge,最后等到写randomRemove()的时候,我突然意识到好像并不能保证O(1)了…因为生成一个随机数,也没办法单位时间定位到该元素,除非再加一个HashMap。
这时候大姐开始放大招了,说你已经用了两个data structure,不能用第三个了。我说can you give me a hint?她说you should think about why you want to use linked list in the first place, that’s my hint… 我心想这不等于没说?然后她说I’m actually questioning your whole data structure design…我汗。我想了下说是要用两个HashMap?她说对。可是这时候就剩不到十分钟了。我赶紧跟她说应该怎么做,边说边写,但是也还是没写完就到时间了。所以这题应该是用第一个HashMap放index + 元素内容,重复的元素要分开放,第二个HashMap放元素内容+arrayList of indexes,把重复元素的indexes放在一起。所以上面的例子就应该是HashMap1 : (1, cat), (2, dog), (3, pig), (4, cat), HashMap2: (cat, (1, 4)), (dog, 2), (pig, 3)这样。add, remove很容易O(1),randomRemove()时生成一个1-4的随机数,比如2,然后从第一个map里找2对应的是dog,然后从第二个HashMap里找到dog,把dog删掉。但有一个小问题我觉得她自己也没想清楚,就是如果有很多dog,那么dog的list很长,并不能保证O(1)找到要删的那个dog的index吧?。。另外还有一个trick,就是删掉dog后,要用第一个map中的最后一个元素去填补中间的gap,否则下次如果再生成随机数2,就找不到元素了。
果然两天后被拒了,毕竟代码都没写完。。祝版上的朋友们好运!