雅虎yahoo电面

原帖地址:一亩三分地

刚刚挂了电话的yahoo面经,我真是觉得三哥的口音崩溃了。。我感觉三哥根本就是在家里给我面试的,背景我还听到了小孩子的声音我去。。。
这还是雅虎么疯了。

anyways,我感觉我的题目和地里的都不一样感觉还挺难的,并且我越写越觉得这两个题实在是太贱了
第一题是例如,你有一个list of strings(以下例子是我编的,但是意思是一样的,他给我的是不同的例子):
1.welcome to America have a nice day
2.welcome to Asia
3.wel
所以结果就是wel
他开始和我说的时候还没给我第三个例子,开始只是说“welcome”就是结果,我开始还以为他说的是找重复的word呢,我想那还不简单~然后我和他说了我的想法他说不对,
我们要解决的不是这个问题。。。我心里默默吐槽:那你不早说清楚!最后和我澄清的时候给我加了第三个例子,我才明白要干啥. 他说的例子是this 和thin的common是thi
也就是找到longgest common sequence of letters 的题目,但这个题目不是leetcode longgest common prefix那种那么简单,common的部分不局限于开头部分的重复。然后
我想了半天也没想出来时间度比较好的方法,后来他和我说给我hint 用trie tree,我心想那trie tree找不是同一字头的common sequence的话不也得按照从同一字头来找吗?
如果不是同一node的subtree,那样找下去的不也得增加很多complexity?如果诗同一字头的话那用我们的LCprefix的解法够够的了。trie tree貌似也不能很好解决中间match的情况吧?
那我想既然他说trie tree那我就用trie tree吧就和他说了一下trie tree该怎么做,他说可以但是我们没时间implement就到下一题了。

第二题是
input{1,2,3,4,5}
output{2*3*4*5, 1*3*4*5, 1*2*4*5, 1*2*3*5,1*2*3*4}

意思就是input {一个unsorted的integer array} 问了之后告诉我unsorted
output {每一个output entry的值是input里所有不等于current index的value的乘积}
我问他是不是index从1开始,而且比如说如有{1,1,1,2,3},output第一个entry就是6?
他自告奋勇给我写了output{6,6,6,3,2}
我跟他说可以用除法做就比较省时间,他说你不能用除法
然后给我hint说你可以用another array 然后用这个array去record current index左边所有value的乘积和右边所有value的乘积。
我想了会儿觉得就算按照他说的用another array 也并没有很好的解决这个问题啊,那不还是一样要遍历所有的element去乘,而且还不能用除法。
可能是我早起傻了吧。我质疑他这种方法并不会improve complexity而且还增加space complexity,并且你也没有sorted,遇到duplicate不也需要有效的剔除等等
operation都需要增加复杂度啊。他居然和我说。。。这个方法就是能很好地解决。。我问为啥他也没告诉我为啥。。就是说it works。。。。。
我汗。。。。。这绝对是我见过的最扯的面试官了。
已然崩溃,我去吃点饭压压惊