2014年1月7日Google实习电面 - ┅☆心随风飞 - 博客频道 - CSDN.NET
然后我说应该可以用分治法搞，两两merge，复杂度为O(logK*N)。 他之后说让我选一个方法实现。我觉得要实现肯定得实现更有效的啦。 之后问我，那你有没有什么方法减小空间的开销。 第二面听声音是个年纪比较大的人，一开始还跟我讨论校园文化，说他女儿对我校的鼓号队感兴趣，汗哪。。。 我就说数据这么大，用外排序呗，分成一个block一个block的排序，然后in place合并。他问了又些细节，我虽然见过这个问题，但是没有想得那么深入，感觉他对有些细节问题的回答不太满意。 他还问了一个问题，说如果输出的数据也要分块的话，你是如何进行分块操作的。我当时随口一说，可以对每个string加一个data field叫size，做成类似于prefix sum的东西，不过这样肯定不够高效。 他说嗯，这个可以吧，没让我多想。不过事后想了下，发现这个问题太简单了，之前自己还在project中实现过对文本文件的partition。就是先等长划分，然后再调整划分点的位置即可，通过寻找类似于'\0'这样的字符就可以了。后悔死了，不过也怪他没给我时间多想，直接转到下个问题了。 第二个问题让我打印出质数。 后来稍微想了下，说与其存储之前所有从2到i-1的数，还不如存这些数最后分解的因子，毕竟之前遇到的因子肯定比之前遇到的数要少得多。 这样我就放心了，然后他说那你就coding吧。 之后他问我如果一直这样循环下去，会有什么后果。我就说cpu一直飞速运行，直到内存溢出，因为内存是不可能存储下所有因子的。 他接着问有没有什么方法让循环持续时间更长，找到更多的质数。 我说那就把这些因子分块写到硬盘上，然后每次遍历所有因子的时候按一个block一个block的来。 他看了下，说不高效，这样每次检查一个数是不是质数，都会遍历所有的block，disk io开销太大。 我没听懂意思，以为说我写for each的时候需要预先载入所有的block，我连忙说不是的，这些block是链表形式链接的，把for each语句改成了链表形式的遍历。 他还是不满意，毕竟我没抓住重点。他说你应该把函数接口变下，输入的数据不应该是一个数，而是一个block的数。 我恍然大悟，然后连忙接过话，说这个学过，本质就是编译器课里对嵌套循环的优化嘛，把多层循环分块，提高data locality。然后解释说我以为他是让我在降低timeRead full article from 2014年1月7日Google实习电面 - ┅☆心随风飞 - 博客频道 - CSDN.NET
