Dropbox Intern 面经

mchzh 发表于 2016-2-17 13:08
这题也是leetcode上的？

不是。combinations那部分是leetcode上的。

楼主好人，能把search部分的问题描述说得更明白些吗？dictionary里都是什么？让search什么？

ankaiyue 发表于 2016-2-17 16:20
楼主好人，能把search部分的问题描述说得更明白些吗？dictionary里都是什么？让search什么？

dictionary里就是一些字符串。。。phone number能组成一些combinations，然后在dictionary里找出combinations

yhfyhf 发表于 2016-2-18 06:27
dictionary里就是一些字符串。。。phone number能组成一些combinations，然后在dictionary里找出combinat ...

lz请问你说的“一开始给的条件是电话号码长度是7，直接分情况在dictionary里search就行了”，是不是面试官规定了字典里单词的最小长度是3？另外长度不为7的话，得先找出所有可能的单词组合，然后对于每个组合再在dict里搜索？谢谢

letsdoit666 发表于 2016-3-18 14:23
lz请问你说的“一开始给的条件是电话号码长度是7，直接分情况在dictionary里search就行了”，是不是面试 ...

completely right

yhfyhf 发表于 2016-3-19 09:26
completely right

另外求问lz最后一个followup cache一下是啥意思呢？没看懂，谢谢！

用TIRE当然不是说你已经凑好一个单词了，再去TRIE里搜索了，是带着TRIE NODE往下搜，遇到TRIE NODE CHILDREN里完全没有的，直接跳过，可以避免很多无意义的DFS，如果带着TRIE NODE往里搜，那么判断是不是单词也就O(1)，因为就CHECK一下那个ISWORD的BOOLEAN就行

请教一下楼主，
1. dictionary里面是不是从开始到follow up一直都是3位，4位，7位的词组呢
2. follow-up 的话 电话号码就不是7位了, match的话就是word break去dictionary里面找match的

谢谢！

letsdoit666 发表于 2016-3-19 09:38
另外求问lz最后一个followup cache一下是啥意思呢？没看懂，谢谢！

虽然时间有点久远，还是想问问层主这个cache的问题。。。啥叫用个dict把每个结果存起来……谢啦