[合集] 问个google面试题# JobHunting - 待字闺中
S*I
1 楼
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Thu Sep 15 15:17:21 2011, 美东) 提到:
careercup上面看到的，g得phone interiview
Suppose you are given a dictionary of words based on an alphabet with a
fixed number of characters. Please write a method / function which will find
the longest word in the dictionary such that it can be built from
successively adding a single character to an existing word in the dictionary
(in any location). For instance, "a" -> "at" -> "cat" -> "chat" -> "chart".
☆─────────────────────────────────────☆
taras (taras) 于 (Thu Sep 15 15:24:04 2011, 美东) 提到:
介个是trie？
find
dictionary
".
☆─────────────────────────────────────☆
dinohound (dino) 于 (Thu Sep 15 15:26:17 2011, 美东) 提到:
trie 里面找最深节点，path上每个点都是个词。
☆─────────────────────────────────────☆
vanmark (controlled aggression) 于 (Thu Sep 15 15:37:16 2011, 美东) 提到:
不行吧，at->cat不在一条path上
☆─────────────────────────────────────☆
dinohound (dino) 于 (Thu Sep 15 15:44:20 2011, 美东) 提到:
哦，我题目没看仔细。
那就用hashset.
☆─────────────────────────────────────☆
bluepuppy (每天爱你多一些) 于 (Thu Sep 15 15:45:42 2011, 美东) 提到:
有向图，从原点(一个字母开始)找最长的path?
find
dictionary
".
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Thu Sep 15 16:08:49 2011, 美东) 提到:
我也是这么想的，建立一个图 ，但是觉得不是最优的。
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Thu Sep 15 16:21:42 2011, 美东) 提到:
1. 把字典按字长分进数组
2. 单字 -> map[1](key, "")
3. 从 i = 2 开始循环，找长度为 i, 减去一个字母后在map[i-1]的keySet里的单词，
放进map[i](key, shrinked)
4. 重复3，直到map[i]为空。
从map[i-1]任挑一个就是最长的可变化的词。英语里好象就一个解: carrousel.
carrousel - carousel - carouse - arouse - rouse - ruse - use - us - s
用本更大的字典找的：
complecting - completing - competing - compting - comping - coping - oping - ping - pig - pi - i
☆─────────────────────────────────────☆
airplane1022 (Pan) 于 (Thu Sep 15 16:48:31 2011, 美东) 提到:
谁能给个字典文件，想测试一下，多谢
☆─────────────────────────────────────☆
raullen (raullen) 于 (Fri Sep 16 18:50:53 2011, 美东) 提到:
http://www.mediafire.com/?djzgrn1eong
找到了如下chain：
abranchiate -- 无鳃动物
abranchiate-branchiate-branchiae-branchia-branchi-branch-ranch-rach-ach-ah-h
全是些诡异单词 不知道这是个啥dic。。。
和gloomyturkey的结果一样 这个chain长11
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Fri Sep 16 19:40:17 2011, 美东) 提到:
你的方法是从短的到长的.
从长到短效率相比之下如何? 对一个长词,如果发现最后不能分解,那么一路上所有的变
种都可以不在考虑了
- ping - pig - pi - i
☆─────────────────────────────────────☆
maxq (zf) 于 (Mon Oct 10 11:03:04 2011, 美东) 提到:
考个古。火鸡的思路很不错，保证了每次在寻找长度为i+1词的时候，
长度为i的有效词都已经计算出来了，只需要查找这些有效词，类似
于DP。
我觉得从长到短会有很多的重复计算，当然也可以用记事本的方法
不过空间开销比较大
Bayesian1 (Jason) 于 (Thu Sep 15 15:17:21 2011, 美东) 提到:
careercup上面看到的，g得phone interiview
Suppose you are given a dictionary of words based on an alphabet with a
fixed number of characters. Please write a method / function which will find
the longest word in the dictionary such that it can be built from
successively adding a single character to an existing word in the dictionary
(in any location). For instance, "a" -> "at" -> "cat" -> "chat" -> "chart".
☆─────────────────────────────────────☆
taras (taras) 于 (Thu Sep 15 15:24:04 2011, 美东) 提到:
介个是trie？
find
dictionary
".
☆─────────────────────────────────────☆
dinohound (dino) 于 (Thu Sep 15 15:26:17 2011, 美东) 提到:
trie 里面找最深节点，path上每个点都是个词。
☆─────────────────────────────────────☆
vanmark (controlled aggression) 于 (Thu Sep 15 15:37:16 2011, 美东) 提到:
不行吧，at->cat不在一条path上
☆─────────────────────────────────────☆
dinohound (dino) 于 (Thu Sep 15 15:44:20 2011, 美东) 提到:
哦，我题目没看仔细。
那就用hashset.
☆─────────────────────────────────────☆
bluepuppy (每天爱你多一些) 于 (Thu Sep 15 15:45:42 2011, 美东) 提到:
有向图，从原点(一个字母开始)找最长的path?
find
dictionary
".
☆─────────────────────────────────────☆
Bayesian1 (Jason) 于 (Thu Sep 15 16:08:49 2011, 美东) 提到:
我也是这么想的，建立一个图 ，但是觉得不是最优的。
☆─────────────────────────────────────☆
gloomyturkey (一只郁闷的火鸡) 于 (Thu Sep 15 16:21:42 2011, 美东) 提到:
1. 把字典按字长分进数组
2. 单字 -> map[1](key, "")
3. 从 i = 2 开始循环，找长度为 i, 减去一个字母后在map[i-1]的keySet里的单词，
放进map[i](key, shrinked)
4. 重复3，直到map[i]为空。
从map[i-1]任挑一个就是最长的可变化的词。英语里好象就一个解: carrousel.
carrousel - carousel - carouse - arouse - rouse - ruse - use - us - s
用本更大的字典找的：
complecting - completing - competing - compting - comping - coping - oping - ping - pig - pi - i
☆─────────────────────────────────────☆
airplane1022 (Pan) 于 (Thu Sep 15 16:48:31 2011, 美东) 提到:
谁能给个字典文件，想测试一下，多谢
☆─────────────────────────────────────☆
raullen (raullen) 于 (Fri Sep 16 18:50:53 2011, 美东) 提到:
http://www.mediafire.com/?djzgrn1eong
找到了如下chain：
abranchiate -- 无鳃动物
abranchiate-branchiate-branchiae-branchia-branchi-branch-ranch-rach-ach-ah-h
全是些诡异单词 不知道这是个啥dic。。。
和gloomyturkey的结果一样 这个chain长11
☆─────────────────────────────────────☆
guangyi ( 光一) 于 (Fri Sep 16 19:40:17 2011, 美东) 提到:
你的方法是从短的到长的.
从长到短效率相比之下如何? 对一个长词,如果发现最后不能分解,那么一路上所有的变
种都可以不在考虑了
- ping - pig - pi - i
☆─────────────────────────────────────☆
maxq (zf) 于 (Mon Oct 10 11:03:04 2011, 美东) 提到:
考个古。火鸡的思路很不错，保证了每次在寻找长度为i+1词的时候，
长度为i的有效词都已经计算出来了，只需要查找这些有效词，类似
于DP。
我觉得从长到短会有很多的重复计算，当然也可以用记事本的方法
不过空间开销比较大