G家LA office电面

原帖地址:mitbbs

国女,第一题找n个数中最大的k个,我说用size为k+1的min heap,放满,然后循环里
不断
poll和add。她觉得结果不对,我就写了下伪码示意(她没让我写代码,我是为了给她
讲明白)
minHeap(k+1)
for(){
heap.poll();
heap.add();
}
她认为不正确,说如果先遇到前k大的结果就不对了(此处我也不知道她在想什么),
我就给她解释+测试,她又想到别的情况,换各种测试,10多分钟浪费在这,她终于觉
得好像没错。中间我试图给她个台阶,说quick select方法更快,但她完全不理会,继
续纠缠heap的正确性。后来终于跟我说,她想要的解法时size为k的heap,循环里先
peek再根据情况add。如果是讨论复杂度我完全理解,为什么方法不一样就认为是错的
,水平实在很让我吃惊,到最后也没跟我提quick select方法,目测已经超出了她的知
识范围

第二题不知从哪粘过来的,背景还是红色的。。在string末尾添加字符串,使原string
成为回文,返回需要添加的最小string。跟leetcode的Shortest Palindrome差不多,
那题我是一次过的。循环中两种情况:以字母为中心;以字母间隔为中心。她问我为什
么要考虑第二种情况,我是连画图,再举例,她愣是不明白,最后说要回去再想想。

结果给我来个据信。各位不用怀疑我面试中的态度,我是绝对耐心+各种给台阶说可能
是我没说清

又一次不得不提到烙印,对比实在太明显,前一天推特电面,merge k个iterator of
list,也是用的heap,中间对iterator的操作跟他的要求有点出入,改了一遍,之后给
了onsite