square 电面一面

原帖地址:一亩三分地

EST 3点刚结束的,本来原定skype面试,但是Skype杂音极其严重,改打电话了。在coderPad.io做题,偶尔也用skype的message交流一下。

上题目:类似leetcode上word search II,但是简化了一些。输入有一个vector作为字典,至于另一个输入原题输入是一个vector>来找单词,这里是一个string作为单词pattern来match。输出是可能match到的所有单词。pattern只有小写字母a-z,还有一个『*』可以match任何一个且仅一个字母。

在开始写之前,先让我针对『*』的情况来对trie做优化,因为这个情境里n个『*』就有26^n的复杂度。我就说给trie的每个child*都设立一个对应的vector表示这个child下面可能会有长度为多少的单词来match。这样遇到20个『*』的情况,这个child*没有对应20长度的单词,这个child*就跳过了。

幸亏昨晚做了一遍word search II!基本上按照word search II的套路就会做出来,先建trie,然后我recursive的方式给pattern里面的char挨个去match。

一开始我想iterative的方法去match,但是觉得对『*』处理起来比较麻烦,iterative一半改了recursive,导致一部分代码没适应改过来。。出了segment fault。。不过面试官对写的代码和思路还是认可的,看时间块到了,最后和我分析了一下代码bug可能地方,说应该只是一个很小的地方,只是时间不够来不及改了,然后让我问问题了。随便问了些他对square的喜爱程度,然后我在过程中口头膜拜了他的工作,然后就结束了。

退出前复制了所有代码,然后在xcode跑一遍马上意识到了问题,面试结束5分钟后通过skype给他留言了我改的能通过的代码,不知道会不会有加分~ 虽然有个fault,但是貌似这个面试官挺满意的。。希望能有下一轮电面。。
这是我为数不多的面试,希望能撑到onsite~