主题：45分钟google电话面试实录 -- krone

在河里好像很少有面试题目的讨论。在下就抛砖引玉，贴一下最近的google第一轮电话面试的经验。谢绝转载，欢迎拍砖。

这是我找工作以来的第一个正式的电话面试。本来是想拿小公司练练手，哪知道老板突然有推荐，机会难得，不能放弃，只好先上了。投了简历之后，就有 recruiter和我取得联系。在一番email往来之后，确定了今天下午的面试。整个interview有45分钟，问了两个算法题，一个设计题。难度不是很大，但是感觉一般，发挥不算太好。

首先和面试官一番寒暄。稍微介绍了下research热热身，然后开始正式的面试。第一个题目是个字符串匹配。给定n个长度相等的字符串，输出最长公共字串。注：串数目为n，可假定所有串等长。

example: abcabb, xyabcd, dcabcc

output: abc

a. first attempt, suffix tree. 这是我的第一反应，因为Knuth曾经猜测对两个字符串求最大共同连续字串是不能在线性时间内完成的，但是结果用后缀树可以在线性时间检测。所以我提出以下方案：get suffix tree of 1 and 2 merge the tree to find the longest shared length

I found that this did not work. because the longest shared string of 1 and 2 was not necessary the longest of all the strings. I changed my idea immediately.

注：我后来仔细的思考了一下，后缀树仍然是可行的。 Just set up a big suffix tree for all the strings. For each nonleaf node, count the subtree nodes id, i.e, the indexes of all the strings that have showed up in the subtree. If the indexes make up the set {1...n}, then that inner node has the label shared by all the strings. Then we just need to find the guy with larges label length. Thus the total time would be n * nx = xn^2

b. 我提议k-gram再用inverted indexes.可惜面试官没有听说过这个算法 :< 只能用例子来解释k-gram.

idea of k-gram: set up all 2-grams, 3-grams, ..., x-grams of the n input strings. Then there are nx^2 *-grams in total. For each gram, check if a k-gram contains the whole 1:n, if so, that certain gram is shared by all the strings. Then finding the longest length gram and we will get the solution.

REALIZATION: set up a hashtable for all the grams, then a new tuple (gramwords, stringNo, idx), will be mapped to a bucket. There are totally nx^2 map images. For each gram, we can use a length-n bit vector to record the appearance of different strings. 注意，如果大部分gram所含的相交字符串集数目不超过n，用list更好。

面试官的评论: the time may not be exactly nx^2 because we need to compute the hash value and it takes l time for a l-gram. Hence the final time may still be nx^3 which match his brutal force solution. (敌人大大的狡猾啊）

MY ANSWER: the hash values are not computed separately. We will use Karp-Rabin algorithm to compute a signature of the grams. 他不知道Karp-Rabin algorithm :< 估计他不知道我是啥意思。我同时补充到，我的算法具有可扩展性。任何一个新的string都可以加入原数据结构，不需要全部重做。他也就哼哼阿阿的算是了解了我的算法。然后他提出了一个简单的算法，说期望我先上那个算法。。。

总之，我觉得这题答的并不好。我应该第一时间回答最简单的暴力解法，也就是接下来他希望我回答的。因为如果不用后缀树，后缀数组，kgram这些高级的数据结构是很难实现优化的。可是面试官对于字符串匹配似乎不是很熟悉。估计我答出暴力算法他就会满足。虽然我很早就读了很多面经，确定了先易后难的策略，可惜还是一激动就拋之脑后了。

注：一位朋友观察到不用建立所有string的kgram，只要第一个字符串的kgram就可以。

c. His algorithm. use brutal force. take s[i:j] and do n-1 string matching. The time will be x^2 * nx = nx^3.

第二题是设计类问题。我基本没有什么感觉。也不知道对错，面试官也没有评价，反正使劲瞎猜也没猜出个啥来。结果中间面试官还被赶出了他的会议室，断线了两分钟。。。

问题，gmail在载入的过程中非常的缓慢，怎么办？（看来和我一样用5岁旧电脑的人不少：）

a. get all machines and do comparison experiments to see if it is caused by the hardware.

INTERVIEWER: it is not hardware problem. nor network. He proposed Javascript

b. give the user choice to choose cleaned version, for example, disable the javascript, or two steps showing up: first incoming messages then others. Rewrite java script and so on.

The thing is I had no idea about how javascript works :< I don't know it will cause page loading slow.其实我曾经被script折磨过的。有很长一段时间上西西河打开某些网页时经常花费很多时间，然后跳出对话框说是google toolbar的某个script有问题，不过我当时没有深究，结果。。。sigh！

这是个problem solving问题。明显应该先硬件后软件，我怎么答出硬件之后忘记了问是否软件的问题，失策失策，答的最差的一题。

算法问题

Background:

有一个错误的log如下，注意时间。具体问题就是，我可以随时要求你给出一下统计数字，比如上一分钟，上一小时得到的错误数。

Example:

404_errors_last_minute: 10

404_errors_last_hour: 100

404_errors_total: 1234

00:01: Event

00:05: Event

00:06: get_total -> 2

01:00: get_last_minute -> 2

01:02: get_last_minute -> 1

01:06: get_last_minute -> 0

有如下函数给出

time_t current_time();

void event()；

希望能得到如下的统计数字。填写相应的函数。

// Get statistics.

int get_last_minute()；

int get_last_hour()；

int get_total()；

解答: 使用队列来分别保存一分钟，一小时的信息。当新的error entry来到的时候，在分钟队列中删除超时的那些（对于小时队列做同样的删除）。思路应该是对的可惜在编写程序是没有一次得到最优的结果。首先删除 outdated数据应该循环删除直至不能，不能只删一次。不过我自己发现了这个bug改正过来了。此外删除应该check queue front元素，我写的代码居然check了back，汗！面试官当时没有发现。不过如果他回头看存下来的代码一定会找到这个，杯具阿。

扩展问题。如果数据项是在太多，亿万记，将全部时间数据保存要耗完内存，怎么半？于是我提议将数据按照0.001秒分成1000个区间，对于时刻s的 query，我们只需要check从s往前数的第1000个区间中的具体数值。这样内存就只需要1／1000，当然我们也增加了disk读写的时间。不过面试官没有详细问，我提出区间划分他就掠过了，也没有太多评价。估计是要超时了。我前两题没答太好，弄了太多时间。

总而言之，发挥一般，暴露了不少问题。字符串匹配算比较熟悉的，可惜面试官又不熟悉。个人感觉google的算法题目还是比其他公司难一些。