2014年1月7日Google实习电面

2019-04-13 17:38发布

站内文章 / 模拟电子
13233 0 1563
Google两轮电面，两个面试官都根据我的背景聊了下big data。

第一轮相谈甚欢，就问了我一个题目：
给K个排好序的链表，总长度为N，求如何合并成一个排好序的总链表。

我先谈了谈直接设K个指针从每个表头开始扫，每次将k个数中的最小数加入总链表。然后我说这个显然没效率的，O(K*N)复杂度。
然后我说应该可以用分治法搞，两两merge，复杂度为O(logK*N)。

之后他问我虽然分治法快，但是相比第一种方法，有什么缺点。
我犹豫了下，感觉没发现什么缺点，然后想歪了，在想是不是不好并行，不够scalable？但是想了下感觉应该不是，然后就随口用疑问的口吻丢出一句“space？”。美国人真nice，直接兴奋的告诉我对啦！就是space，然后一串bulabula...


他之后说让我选一个方法实现。我觉得要实现肯定得实现更有效的啦。
我写了一段代码，他没发现bug，我还发现了一个小bug补上了，原来是忘记考虑输入为null的情况了。他说这个无所谓，我汗，感觉还没我严谨。

之后问我，那你有没有什么方法减小空间的开销。
我觉得这个很简单，直接问输入可以修改不？他表示ok。我就说，那我merge两个链表的时候直接修改两个链表结构，做成in place merge不就行了么，无需额外空间开销。他觉得这个方法可以，不过见我代码是java写的，表示in place merge在java中可不好实现哦，然后又bulabula一串，重点是虽然不好实现，但是仍然可以实现。我看他说得那么兴奋，瀑布汗啊。。。我本身就觉得这个问题分治法开销本来就不大，要是我用c++或者按照LeetCode的ListNode定义，我本来就打算做成in place merge的，只不过他给我定义好接口了，用java API写就没写成in place的。这也是在他问我缺点的时候我疑惑的原因。


第二面听声音是个年纪比较大的人，一开始还跟我讨论校园文化，说他女儿对我校的鼓号队感兴趣，汗哪。。。

第一个问题是个经典问题，问给你millions of documents，如何sort这些string。之前还问我map reduce里sorting是怎么实现的。
我就说数据这么大，用外排序呗，分成一个block一个block的排序，然后in place合并。他问了又些细节，我虽然见过这个问题，但是没有想得那么深入，感觉他对有些细节问题的回答不太满意。
他还问了一个问题，说如果输出的数据也要分块的话，你是如何进行分块操作的。我当时随口一说，可以对每个string加一个data field叫size，做成类似于prefix sum的东西，不过这样肯定不够高效。
他说嗯，这个可以吧，没让我多想。不过事后想了下，发现这个问题太简单了，之前自己还在project中实现过对文本文件的partition。就是先等长划分，然后再调整划分点的位置即可，通过寻找类似于'

热门文章