五千年(敝帚自珍)

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

共:💬13 🌺49
全看树展主题 · 分页首页 上页
/ 1
下页 末页
家园 45分钟google电话面试实录

在河里好像很少有面试题目的讨论。在下就抛砖引玉,贴一下最近的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的算法题目还是比其他公司难一些。

元宝推荐:爱莲,
家园 大胖子沙发
家园 电话面试算法?感觉很难说清楚啊?
家园 牛!估计几句英语就把我打倒了;-)

请问楼主,你在思考的时候是用英语还是用中文?

家园 你必须对基本算法问题很熟悉,这样才能当场给出答案

基本的排序,链表,栈,队列,动态规划,树,都要非常熟悉。此外对于google,microsoft面试而言,programming pearls是必须掌握的,introduction to algorithms的一部分章节也要很熟悉。尤其现在竞争很激烈,不充分准备是不行的。

家园 汗,咱英语也一般

因为要不停的在电话里面说,我估摸着是英文吧,我自己还真没可以关注过这个问题。其实在米国好几年了,咱英语是没啥长进啊。突然想到,可能听咖喱英语能力有进步:)

家园 这些我都不懂,我是学生物的……
家园 数据结构那一部分有什么好书推荐吗?谢谢!
家园 很久以前的经验

有一本书叫<数据结构+算法=程序>,个人感觉非常非常非常精典.当然,我看这书是在十多年前.

这书的作者是Niklaus Wirth.有点熟不?他是Pascal语言的发明人.

家园 英文看不懂,其它回复一下

第一题,建一个数组,把第一个单词先排序,再逐字放进去,然后对后面的单词,都是先排序,再和数组里面的字比对,剔出没有的。比对到最后一个词,结果就出来了,那个啥啥树,用不着吧?

第二题,不知道你是在哪里求职,要是我第一步先怀疑网络有问题。因为对于自己常用的电脑,硬件和系统的状态是可以预知的,出现意料之外的缓慢,首先怀疑网络。

家园 书籍推荐

偏向编程的,我推荐这两本

1. algorithm in c++

http://www.amazon.com/Algorithms-Parts-1-4-Fundamentals-Structure/dp/0201350882

此书国内有卖。还有相应的java,c版本

2. Data Structures and Algorithms in C++

http://www.amazon.com/Data-Structures-Algorithms-Adam-Drozdek/dp/0534491820/ref=sr_1_1?ie=UTF8&s=books&qid=1261884924&sr=1-1-spell

此书清华翻译出版了。但是翻译的非常一般。正文还可以捏着鼻子读下去。而图,估计是找学生画的,错误百出。

如果这两本都仔细的读下来,程序也过一遍,基本的内容就掌握了。

理论:

1. introduction to algorithms,

http://www.amazon.com/Introduction-Algorithms-Second-Thomas-Cormen/dp/0262032937

有三十多章,必须掌握的应该有17章左右(没有仔细数)。其中包含基本的排序,动态规划,贪婪算法,树,基本图算法,hash等章节都须熟悉。其他的有些augumented data structures, network flow等有空也应该看看,没空就算了。

2. Art of Computer Programming

http://www.amazon.com/Art-Computer-Programming-Volumes-Boxed/dp/0201485419/ref=sr_1_1?ie=UTF8&s=books&qid=1261885348&sr=1-1

终极宝典,不过比较难读。Knuth用一种很老的汇编语言来描述算法。我刚开始看的时候以为必须看懂那个汇编才可以继续下去,被折磨的不行。后来发现不懂那个汇编也可以接着看,当然这样就有很多特别细致的分析就不能深入了,但是我个人认为得到asympototic bound应该就可以了,没必要精确到到底执行了多少次加法,乘法。当然Knuth不这么想:)

面试算法

即使把以上的书看完了(估计能真正看完Knuth三卷本的凤毛麟角),对于非牛人而言还是有必要专门针对面试进行练习。牛人可以当场得到答案,但是鉴于现在恶性竞争,经常有些直接从paper中拿出来的特殊算法,还是有必要先练习一下。

Programming pearls

http://www.amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/0201657880/ref=sr_1_1?ie=UTF8&s=books&qid=1261885733&sr=1-1

这本书必须全部看完,并且熟悉书上的每个习题。

www.careercup.com

www.mitbbs.com jobhunting版

比较好的讨论面试题的地方。我经常在那潜水。但是论坛的特点就是鱼龙混杂。所以还是先看完jobhunting版的精华区吧。

家园 introduction to algorithms下载

http://rs255.rapidshare.com/files/221287664/Introduction_to_Algorithm.pdf

难得还能下,需要的快下

家园 花,非常感谢。
全看树展主题 · 分页首页 上页
/ 1
下页 末页


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河