Dropbox电面面经 - ┅☆心随风飞 - 博客频道 - CSDN.NET
MIT小白面的,感觉比较寡言少语,面试的时候不怎么说话,就安安静静看我写代码。
第一问:给一个电话号码,并且提供一个字典,要求给出所有与号码对应的单词。这个题目跟LeetCode里的letter Combinations of a Phone Number比较类似,DFS秒掉。简单分析了下时间复杂度。
第二问:如果dropbox这种单词不在字典里,但是drop和box都在,那么dropbox也算,这种情况怎么办。我首先思路是沿袭第一问的方案,在DFS的函数里,除了一个string作为当前的string,多加了一个string参数作为merged string。思路稍作修改,对于一个字母,有两个选择:1)可以append到当前string上;2)如果当前的string本身是一个合法单词,可以把当前string设置为空字符串,在之后重新匹配。
第三问:我说第二问的解法可能会产生重复的解,小白就问如何解决。我说了最简单的方法是用set去装结果,然后说想想其它解法。之后沿着这种思路想不下去了,决定换一种思路。思路应该和LeetCode里的Word Break不多,大致就是使用DP或者recursion + memorization。如果整个单词在字典里,就标记下。如果不是,尝试所有的划分方法,把单词划分为2个子单词,再递归下去。说了思路后本来想写的,应该之前做过这种题目,结果小白估计怕我写代码时间太久,就直接到下个问题了。
第四问:如果给了dict,而不仅仅是给了一个函数接口,能不能换种思路。我想大概是要我从dict出发,枚举出所有组合词,直到组合词的长度超过电话号码长度吧。我实现的时候做了一些剪枝,因为每次寻找下一个单词时,都是需要跟下一块号码子字符串对应的(用到了第一问实现的方法),如果不对应,那么就不用继续递归下去了。
第五问:问从字典出发的方法和从号码出发的方法,哪种好。我觉得这个问题比较复杂,就说字典小的时候从字典出发有优势,不然就从号码出发。
第六问:我在解题的时候说字典如果能用字典树构造而不是set,那么解法可以被优化。然后小白就顺藤摸瓜,问如果让我用字典树,怎么写代码。
我写了下,发现要改的地方不少。一大半都得重写,写了一半,然后小白说时间到了。
除开开始10分钟问简历,后面5分钟让我问下问题,余下45分钟感觉根本不可能把所有的题目都写代码,后面2问其实也就够时间写下伪代码。
感觉这一面还是很顺利的,个人觉得combination,enumeration一类的题目一般都不难,唯一难的地方是如何去重,但小白的问题里基本都回避掉了这个难点。
Read full article from Dropbox电面面经 - ┅☆心随风飞 - 博客频道 - CSDN.NET