Google 15 Fall SDE Intern Phone Interview (Additional Interview)

原帖地址:一亩三分地

上周二和Google Phone Interview的, 一共两轮,面经在这里。 当时第二轮被问了一道Reservoir Sampling的变种题,所有时间基本上花在确认问题上,答得很不好,思来想去觉得还想再搏一下试一试,于是第二天直接给HR发信说明情况,表明确定题目花时间太久感觉影响了technical skills’ evaluation希望重新面一次, 极其幸运的是,HR很爽快的reschedule了这周的一轮additional interview。
之前两轮都是中国人,这次一个三哥,个人觉得很不错,很和善也很愿意说话之类的。 问了两道题。
第一题是 Given an array of integers, remove all the duplicates from it.
这题我比较瞎的一点是忘记和他确认sorted or not了,但是感觉三哥自己也没察觉或者,我第一次就是原数组两个pointer直接消除duplicates,我刚写玩pseudo code说要convert into real code,他就直接说觉得是work的,然后问我time complexity,然后说能不能比 O(n^2) 更好, 于是initiate a new array, 接着两个pointer比较。这次写完了的时候,惊觉忘记确认sorted了,于是还没跑test case之前马上问,然后三哥貌似也突然意识到然后顺势说unsorted, 我就说iterate之前先sort,三哥又表示希望keep original order。于是用了hashmap。写完这题大概还剩15分钟。

第二题是Given a list of integers, sort them in a way that if output is s1, s2, s3 .. sN then s1 <= s2 >=s3 <=s4 … sN. 因为时间不多了,看到题的时候有点着急,于是直接说了最开始的idea,说先写这个algorithm然后我再optimize,三哥很nice,说怕我时间来不及,尽量在结束前写完,直接real code吧。最开始想法是说直接merge sort然后头尾依次输出,三哥问了time complexity,然后说希望更快,于是边说边写了 iterate 的方法,就是每个元素和后一个元素比较看是不是希望的次序,如果不是的话互换就好。写完之后三说 he thinks this won’t work for every case. 然后让我想一个not working case 最开始有点蒙,但是我一直没想到,于是小哥自己写了一个case,说你看这个是不是不work,我给他跑了一遍,发现是work的,此时小哥自己有点蒙说give me a second, 然后说觉得code goes well,后时间刚刚好到,相互客套结束interview。 总体感觉没有上次那么紧张,然后一定注意细节,多沟通确认方向,也会有hints。以及鼓励大家如果觉得面的不好且感觉自己没有发挥到准备的水平的话,不妨及时给HR写信反映,说不定就会additional interview的机会。 Anyway,希望大家面试顺利,一起加油。