Google电面(雪崩)

原帖地址:一亩三分地

Full-time 第一家,上周Google HR发来邮件,简短的聊了一下就安排了今天的电面。刚面完,雪崩。。。45分钟就答了一道题。。。
面试的应该是个国人,上来都没寒暄,直接写题:Word break problem (Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words. E.g. Input “iamgoingtoworktoday” dict {i, am, going, to, work, today, day}, Google一搜便知),改成了输出space seperated string。
刚看到题脑子一片空白,只能想到简单recursion的算法,试着说了一下思路,对面半天就回了一个ok。知道肯定不optimal,巨尴尬,硬着头皮写完,他让分析复杂度,我说O(n^2),他问do you think it is really that simple? 吓到了,然后写了个aaaaaab的worst case,估计是O(n!),说完了他半天没动静。。。这哥们话非常少,必须主动催才有回复。然后我俩纠结了一会,我又硬着头皮问他要hint,他就说了一句让我想想有多少种substring的可能,我说O(n!),感觉他觉得我说的不对但是又继续不说话。。。最后我已经要疯了,说回复杂度是O(n^2),他终于放过我了。
放下电话就知道肯定没戏了,上网搜了下发现是经典DP,就是把每层recursion的结果存hashmap就解决了。。。。这大哥估计是想给我送分,结果我完全掉坑里了。郁闷死了。。。
PS. 地里的各位大神能不能帮我分析下naive算法和DP算法的时空复杂度,这是我的分析,供大家参考
. 1point3acres.com/bbsNaive: worst case 时间复杂度T(n) = T(n – 1) + T(n – 2) + … + T(1) => T(n) = O(2^n), 空间复杂度S(n) = O(n)因为最多会递归n – 1层
DP: 空间复杂度应该是O(n)因为要用hashmap存n – 1个中间结果,时间复杂度目前还没想明白。。。

PPS: 各位都怎么应付这类话少的面试官啊?