由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - google电面杯具,贡献题目
相关主题
● 一道Ｇ家店面题● 问个google老题的最佳解法
● Leetcode word ladder 求助！● word ladder II 找所有而不是第一个的最短路径一般咋做的？
● 这段word ladder II怎么改？● String list如何排序
● 这个题能有几种解法？● FB面试题一道 求解
● LeetCode: Word Ladder● 攒RP发A家第一轮电面
● 转划单词题的优解● Groupon 2面 面经
● google 电面● 借人气请教个G题
● leetcode wordladder2 求助！(solved)● 请问facebook末位淘汰是怎样的哦 有offer了但是怕去了不能survive
相关话题的讨论汇总
话题: string话题: word话题: dictionary话题: return话题: dict
进入JobHunting版参与讨论
1 (共1页)
J*********n
发帖数: 370
1
上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
回馈本版，祝大家好运
第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
第二题是：Suppose I give you a dictionary
of words; the size of the dictionary is finite.  Each word in the
dictionary is composed from a set of characters; the size of the alphabet is
finite. Find the longest word in the dictionary with the property that it
can be built one character at a time and at each step is a valid word in the
dictionary.
e.g.  Dictionary = Webster
      Alphabet = A-z
     a -> at -> cat -> chat -> chart -> charts -> …..
估计挂在这道题上面了, 当时说完解法在算复杂度那里纠结了一会儿。先不说解法，打
算面google的自己想一下能不能很快想出解法。
第二轮，第一题MinStack, 我知道可以用两个stack，但是觉得如果直接说显得又是见过了，
所以先说了在每个element里面维持该元素及其以下所有元素的最小值，所有操作O(1),
空间O(n), 面试官说可以，然后写代码。但后来还想再说用两个stack的时候面试官就
直接问下一道了，我也就没提了。第二题是找两个sorted array的intersection，长度m
和n，刚开始差点写成了union，后来意识到改了过来。写完了分析复杂度O(m+n)，
interviewer又问如果一个很长另一个很短，怎么优化，我说对短的array里的元素在长
的元素里binary search，O(nlogm), 因为n << m, 所以应该比O(m+n)要好
希望昨天的twitter和接下来的linkedin能有好结果.
A**u
发帖数: 2458
2
没人感谢？
多些分享
2,3看的眼熟啊，
2是career cup 150上的吧
3 是1337的上面的吧
晚上再来好好学习

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
z***e
发帖数: 209
3
再接再厉,赞面筋
2用A*吗？
q****x
发帖数: 7404
4
iterative deepen search?

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
H*M
发帖数: 1268
5
觉得妮答得都挺好的阿
为什么拒了？
2 用backtracking吧

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
d******y
发帖数: 244
6
thanks
b******g
发帖数: 1721
7
hr 不错，还给你打电话通知结果。一般不是默据吗?
bless for other offers， anyway。
s***l
发帖数: 129
8
感觉还行啊，怎么就被拒了呢。

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
b***e
发帖数: 383
9
bless, 多谢分享。
第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
后就可以找到最长的单词了。
a**********2
发帖数: 340
10
赞面经
bless for T and L
相关主题
● 转划单词题的优解● 问个google老题的最佳解法
● google 电面● word ladder II 找所有而不是第一个的最短路径一般咋做的？
● leetcode wordladder2 求助！(solved)● String list如何排序
进入JobHunting版参与讨论
S*******0
发帖数: 198
11
时间复杂度是多少？
O(n)?

【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
B*******1
发帖数: 2454
12
a -> ba->nba
假设ba,nba都是valid，你的trie每次都从头lookup？

【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
g*********e
发帖数: 14401
13

the problem allows you to go from chat->chart,
by using a trie, you can only add new chars at the tail.
I think the traditional approach would be to use recursion.
If you want to see whether a string is decomposable,
bool foo(string){
return foo(tring) | foo(sring) | foo(sting) | ....
}
Doing this for one string would take O(n), the total runtime is O(n2)
But there should be much faster ways

【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
a*******d
发帖数: 85
14
tree or trie? I'm confused.
a*******d
发帖数: 85
15
My algorithm:
1. Levelize the words in the dictionary based on the length of the string
incrementally, and compute the signature of the string. (for example, the
signature for "and" is "adn", the signature for "apple" is "aelpp".
2. hash1 contains all the letters in the alphabet.
3. for (level=2; level <= Max; level++)
for each entry w1 in hash1
for each word w2 in level
if the signatures of w1 and w2 only differ one
if the w1 and w2 only differ in one letter
put w2 into hash2;
if (hash2 is not empty)
delete hash1;
hash1 = hash2;
hash2 = an empty hash;
else
break;
4. any entry in hash1 would qualify for the longest word.
b***e
发帖数: 383
16

嗯，我应该是把题目理解错了。
但是，要判断 foo(string)的值，也需要建立一个trie才能判断。
如果按照你的递归，如果这个单词的的长度为n的话，时间复杂度应该是(C_1^n+C_2^n
+ ... + C_n^n)(worst case).

【在 g*********e 的大作中提到】
:
: the problem allows you to go from chat->chart,
: by using a trie, you can only add new chars at the tail.
: I think the traditional approach would be to use recursion.
: If you want to see whether a string is decomposable,
: bool foo(string){
: return foo(tring) | foo(sring) | foo(sting) | ....
: }
: Doing this for one string would take O(n), the total runtime is O(n2)
: But there should be much faster ways
g*********e
发帖数: 14401
17

n
the complexity wouldn't be more than the total number of words N in
dictionary.

【在 b***e 的大作中提到】
:
: 嗯，我应该是把题目理解错了。
: 但是，要判断 foo(string)的值，也需要建立一个trie才能判断。
: 如果按照你的递归，如果这个单词的的长度为n的话，时间复杂度应该是(C_1^n+C_2^n
: + ... + C_n^n)(worst case).
b***e
发帖数: 383
18

我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。
比如这个单词是“cat”, 在它的上一层，你要看是否下列单词在字典里存在:ca, ac,
ct,tc,at,ta。但是这些单词并不一定在字典里存在。如果有一个存在，你要判断它的
上上层是否有相应的词在字典里，所以，上上层的词有：a, c, t. 只要有一层是false
,那么就不符合要求。
所以，如果这个词的长度为n， 要知道它是否可以从一个个字母组成，那么复杂度是：
(P_1^n+P_2^n
+ ... + P_n^n)（worst case）.

【在 g*********e 的大作中提到】
:
: n
: the complexity wouldn't be more than the total number of words N in
: dictionary.
g*********e
发帖数: 14401
19

I could think of an improvement to this. Label all the sub-strings when
doing a foo(). If foo(string) fails, all the intermediate strings are also
not de-composable. This would bring the total runtime to O(n).
Certainly we need to sort the dictionary by length before all these.

【在 g*********e 的大作中提到】
:
: n
: the complexity wouldn't be more than the total number of words N in
: dictionary.
g*********e
发帖数: 14401
20

,
false
I didn't quite understand your post.
I mean
foo(string){
if(strlen(string)==1) {
if string exist return true;
else return false;
}
else if(string don't exist) return false;
else return foo(tring) | foo(sring)...;
}
so if a string "abc" doesn;'t exist, we don't bother to check ab, ac, bc
bas

【在 b***e 的大作中提到】
:
: 我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。
: 比如这个单词是“cat”, 在它的上一层，你要看是否下列单词在字典里存在:ca, ac,
: ct,tc,at,ta。但是这些单词并不一定在字典里存在。如果有一个存在，你要判断它的
: 上上层是否有相应的词在字典里，所以，上上层的词有：a, c, t. 只要有一层是false
: ,那么就不符合要求。
: 所以，如果这个词的长度为n， 要知道它是否可以从一个个字母组成，那么复杂度是：
: (P_1^n+P_2^n
: + ... + P_n^n)（worst case）.
相关主题
● FB面试题一道 求解● 借人气请教个G题
● 攒RP发A家第一轮电面● 请问facebook末位淘汰是怎样的哦 有offer了但是怕去了不能survive
● Groupon 2面 面经● 面筋（已狗家为主，因为其余记不清了）
进入JobHunting版参与讨论
i**d
发帖数: 357
21
第二题递归来做不就可以了么。
首先把字典里的词按照从长到短排序
然后对每一个单词检查是否存在一条到长度为1的单词的路径。
复杂度为O(Nk) k是 word的平均长度
k***t
发帖数: 276
22
Not sure whether apt->trap is allowed though their signatures, i.e. the
anagram, differ in one.

【在 a*******d 的大作中提到】
: My algorithm:
: 1. Levelize the words in the dictionary based on the length of the string
: incrementally, and compute the signature of the string. (for example, the
: signature for "and" is "adn", the signature for "apple" is "aelpp".
: 2. hash1 contains all the letters in the alphabet.
: 3. for (level=2; level <= Max; level++)
: for each entry w1 in hash1
: for each word w2 in level
: if the signatures of w1 and w2 only differ one
: if the w1 and w2 only differ in one letter
h*****n
发帖数: 4747
23
bless
a*******6
发帖数: 520
24
怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
O(n)的话不就两行代码吗？

alphabet
is
that it
in
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
a*******6
发帖数: 520
25
倒过来比较好
相当于BFS一个DAG
如果预存两个tries，一个正的，一个倒的，复杂度是O(NM)，N是字典大小（单词个数），M是字符集
大小

【在 i**d 的大作中提到】
: 第二题递归来做不就可以了么。
: 首先把字典里的词按照从长到短排序
: 然后对每一个单词检查是否存在一条到长度为1的单词的路径。
: 复杂度为O(Nk) k是 word的平均长度
a*******6
发帖数: 520
26
不知道问第四题是什么意思？
n<
is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
w****x
发帖数: 2483
27
字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
后一次查询只需要O(n)时间复杂度
a*****n
发帖数: 158
28
这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
B*******1
发帖数: 2454
29
how many memory you need for this?

【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
a*******6
发帖数: 520
30
。。。不会超过the size of the input。。。而且实际上会远远小于Input Size。。。
当然可以先构造一个N个节点的图

【在 a*****n 的大作中提到】
: 这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
相关主题
● 问道amazon的面试题● Leetcode word ladder 求助！
● Java programming question● 这段word ladder II怎么改？
● 一道Ｇ家店面题● 这个题能有几种解法？
进入JobHunting版参与讨论
i**d
发帖数: 357
31
BFS 遍历不是O(n)的。应该是O(V+E)
如果你是的图是个dense graph的话，复杂度可以到O(N^2)

【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
s****a
发帖数: 528
32
1. build hash table for words in : wordsSet
2. sort the words from shortest to longest: wordsArray
while(!wordsArray.empty())
{
string word = wordsArray.back();
wordsArray.pop_back();
int maxLength = word.length();
if (maxLength == 1) return 1;
if (wordsSet.find(word) == wordsSet.end())
continue; // this word is already tested
wordsSet.erase(word);
WordsStack subWordsStack;
subWordsStack.push(word);
// check if the word can be build up from 1 to maxlength
while(!subWordsStack.empty())
{
string newWord = subWordsStack.top();
subWordsStack.pop();
if (newWord.length() == 1)
return maxLength; // found
for (int i=0; i {
string subword = newWord;
subword.erase(i);
if (wordsSet.find(subword) != wordsSet.end())
{
wordsArray.push_back(subword);
wordsSet.erase(subword);
};
}
} // did not find
}
s****a
发帖数: 528
33
sort the words will cost nLog(n)
search will cost kn, where the k is the average length of the word.
q****x
发帖数: 7404
34
思路？太长。

【在 s****a 的大作中提到】
: 1. build hash table for words in : wordsSet
: 2. sort the words from shortest to longest: wordsArray
: while(!wordsArray.empty())
: {
: string word = wordsArray.back();
: wordsArray.pop_back();
: int maxLength = word.length();
: if (maxLength == 1) return 1;
: if (wordsSet.find(word) == wordsSet.end())
: continue; // this word is already tested
n*******w
发帖数: 687
35
这个感觉比较好点。
乍看是O(m!)，m是input string的长度。
不过查dictionary剪枝了，会很快。
存个O(N^2)的二位数组再dfs有点占空间。算是brute force了。
N是dictionary中words数量。
不白板code可以考虑图，不然不好写。

【在 g*********e 的大作中提到】
:
: ,
: false
: I didn't quite understand your post.
: I mean
: foo(string){
: if(strlen(string)==1) {
: if string exist return true;
: else return false;
: }
e*****w
发帖数: 144
36
应该是考O(log n)的Fib(n)算法吧。

？？

【在 a*******6 的大作中提到】
: 怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
: O(n)的话不就两行代码吗？
:
: alphabet
: is
: that it
: in
: the
r*******n
发帖数: 3020
37
应该是看写的是不是漂亮

【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
r*******n
发帖数: 3020
38
俺给你想法一样,
优化方法, 把中间结果放掉hashtable里,
中间结果是满足条件的word, 不用再调用函数判断了,
如果在hashtable就返回真.
foo(string){
if(strlen(string)==1) {
if string exist return true;
else return false;
}
else if(string don't exist) return false;
else return foo(tring) | foo(sring)...;
}

【在 g*********e 的大作中提到】
:
: ,
: false
: I didn't quite understand your post.
: I mean
: foo(string){
: if(strlen(string)==1) {
: if string exist return true;
: else return false;
: }
w****x
发帖数: 2483
39
图的遍历怎么会是O(n^2)???
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度
a*******6
发帖数: 520
40
O(n)的还有什么漂亮不漂亮一说。。。O(logn)的能写好倒是很漂亮

【在 r*******n 的大作中提到】
: 应该是看写的是不是漂亮
相关主题
● 这个题能有几种解法？● google 电面
● LeetCode: Word Ladder● leetcode wordladder2 求助！(solved)
● 转划单词题的优解● 问个google老题的最佳解法
进入JobHunting版参与讨论
f*******t
发帖数: 7549
41
fib不是有公式吗，O(1)，哈哈
m**q
发帖数: 189
42
第二题以前讨论过，我觉得火鸡的方法不错
http://www.mitbbs.com/article_t/JobHunting/31952487.html

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
r*******g
发帖数: 1335
43
我只知道转化成矩阵相乘的算法可以做大O(logn)，但是面试时要写出来也不容易吧？

【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
z******t
发帖数: 59
44
第二轮的题目O(1)时间找出栈中的最小值，有只需要O(1)辅助空间的解法，见下述博客：
http://codercareer.blogspot.com/2011/09/no-02-stack-with-functi

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
J*********n
发帖数: 370
45
上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
回馈本版，祝大家好运
第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
第二题是：Suppose I give you a dictionary
of words; the size of the dictionary is finite.  Each word in the
dictionary is composed from a set of characters; the size of the alphabet is
finite. Find the longest word in the dictionary with the property that it
can be built one character at a time and at each step is a valid word in the
dictionary.
e.g.  Dictionary = Webster
      Alphabet = A-z
     a -> at -> cat -> chat -> chart -> charts -> …..
估计挂在这道题上面了, 当时说完解法在算复杂度那里纠结了一会儿。先不说解法，打
算面google的自己想一下能不能很快想出解法。
第二轮，第一题MinStack, 我知道可以用两个stack，但是觉得如果直接说显得又是见过了，
所以先说了在每个element里面维持该元素及其以下所有元素的最小值，所有操作O(1),
空间O(n), 面试官说可以，然后写代码。但后来还想再说用两个stack的时候面试官就
直接问下一道了，我也就没提了。第二题是找两个sorted array的intersection，长度m
和n，刚开始差点写成了union，后来意识到改了过来。写完了分析复杂度O(m+n)，
interviewer又问如果一个很长另一个很短，怎么优化，我说对短的array里的元素在长
的元素里binary search，O(nlogm), 因为n << m, 所以应该比O(m+n)要好
希望昨天的twitter和接下来的linkedin能有好结果.
A**u
发帖数: 2458
46
没人感谢？
多些分享
2,3看的眼熟啊，
2是career cup 150上的吧
3 是1337的上面的吧
晚上再来好好学习

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
z***e
发帖数: 209
47
再接再厉,赞面筋
2用A*吗？
q****x
发帖数: 7404
48
iterative deepen search?

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
H*M
发帖数: 1268
49
觉得妮答得都挺好的阿
为什么拒了？
2 用backtracking吧

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
d******y
发帖数: 244
50
thanks
相关主题
● word ladder II 找所有而不是第一个的最短路径一般咋做的？● 攒RP发A家第一轮电面
● String list如何排序● Groupon 2面 面经
● FB面试题一道 求解● 借人气请教个G题
进入JobHunting版参与讨论
b******g
发帖数: 1721
51
hr 不错，还给你打电话通知结果。一般不是默据吗?
bless for other offers， anyway。
s***l
发帖数: 129
52
感觉还行啊，怎么就被拒了呢。

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
b***e
发帖数: 383
53
bless, 多谢分享。
第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
后就可以找到最长的单词了。
a**********2
发帖数: 340
54
赞面经
bless for T and L
S*******0
发帖数: 198
55
时间复杂度是多少？
O(n)?

【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
B*******1
发帖数: 2454
56
a -> ba->nba
假设ba,nba都是valid，你的trie每次都从头lookup？

【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
g*********e
发帖数: 14401
57

the problem allows you to go from chat->chart,
by using a trie, you can only add new chars at the tail.
I think the traditional approach would be to use recursion.
If you want to see whether a string is decomposable,
bool foo(string){
return foo(tring) | foo(sring) | foo(sting) | ....
}
Doing this for one string would take O(n), the total runtime is O(n2)
But there should be much faster ways

【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
a*******d
发帖数: 85
58
tree or trie? I'm confused.
a*******d
发帖数: 85
59
My algorithm:
1. Levelize the words in the dictionary based on the length of the string
incrementally, and compute the signature of the string. (for example, the
signature for "and" is "adn", the signature for "apple" is "aelpp".
2. hash1 contains all the letters in the alphabet.
3. for (level=2; level <= Max; level++)
for each entry w1 in hash1
for each word w2 in level
if the signatures of w1 and w2 only differ one
if the w1 and w2 only differ in one letter
put w2 into hash2;
if (hash2 is not empty)
delete hash1;
hash1 = hash2;
hash2 = an empty hash;
else
break;
4. any entry in hash1 would qualify for the longest word.
b***e
发帖数: 383
60

嗯，我应该是把题目理解错了。
但是，要判断 foo(string)的值，也需要建立一个trie才能判断。
如果按照你的递归，如果这个单词的的长度为n的话，时间复杂度应该是(C_1^n+C_2^n
+ ... + C_n^n)(worst case).

【在 g*********e 的大作中提到】
:
: the problem allows you to go from chat->chart,
: by using a trie, you can only add new chars at the tail.
: I think the traditional approach would be to use recursion.
: If you want to see whether a string is decomposable,
: bool foo(string){
: return foo(tring) | foo(sring) | foo(sting) | ....
: }
: Doing this for one string would take O(n), the total runtime is O(n2)
: But there should be much faster ways
相关主题
● 请问facebook末位淘汰是怎样的哦 有offer了但是怕去了不能survive● Java programming question
● 面筋（已狗家为主，因为其余记不清了）● 一道Ｇ家店面题
● 问道amazon的面试题● Leetcode word ladder 求助！
进入JobHunting版参与讨论
g*********e
发帖数: 14401
61

n
the complexity wouldn't be more than the total number of words N in
dictionary.

【在 b***e 的大作中提到】
:
: 嗯，我应该是把题目理解错了。
: 但是，要判断 foo(string)的值，也需要建立一个trie才能判断。
: 如果按照你的递归，如果这个单词的的长度为n的话，时间复杂度应该是(C_1^n+C_2^n
: + ... + C_n^n)(worst case).
b***e
发帖数: 383
62

我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。
比如这个单词是“cat”, 在它的上一层，你要看是否下列单词在字典里存在:ca, ac,
ct,tc,at,ta。但是这些单词并不一定在字典里存在。如果有一个存在，你要判断它的
上上层是否有相应的词在字典里，所以，上上层的词有：a, c, t. 只要有一层是false
,那么就不符合要求。
所以，如果这个词的长度为n， 要知道它是否可以从一个个字母组成，那么复杂度是：
(P_1^n+P_2^n
+ ... + P_n^n)（worst case）.

【在 g*********e 的大作中提到】
:
: n
: the complexity wouldn't be more than the total number of words N in
: dictionary.
g*********e
发帖数: 14401
63

I could think of an improvement to this. Label all the sub-strings when
doing a foo(). If foo(string) fails, all the intermediate strings are also
not de-composable. This would bring the total runtime to O(n).
Certainly we need to sort the dictionary by length before all these.

【在 g*********e 的大作中提到】
:
: n
: the complexity wouldn't be more than the total number of words N in
: dictionary.
g*********e
发帖数: 14401
64

,
false
I didn't quite understand your post.
I mean
foo(string){
if(strlen(string)==1) {
if string exist return true;
else return false;
}
else if(string don't exist) return false;
else return foo(tring) | foo(sring)...;
}
so if a string "abc" doesn;'t exist, we don't bother to check ab, ac, bc
bas

【在 b***e 的大作中提到】
:
: 我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。
: 比如这个单词是“cat”, 在它的上一层，你要看是否下列单词在字典里存在:ca, ac,
: ct,tc,at,ta。但是这些单词并不一定在字典里存在。如果有一个存在，你要判断它的
: 上上层是否有相应的词在字典里，所以，上上层的词有：a, c, t. 只要有一层是false
: ,那么就不符合要求。
: 所以，如果这个词的长度为n， 要知道它是否可以从一个个字母组成，那么复杂度是：
: (P_1^n+P_2^n
: + ... + P_n^n)（worst case）.
i**d
发帖数: 357
65
第二题递归来做不就可以了么。
首先把字典里的词按照从长到短排序
然后对每一个单词检查是否存在一条到长度为1的单词的路径。
复杂度为O(Nk) k是 word的平均长度
k***t
发帖数: 276
66
Not sure whether apt->trap is allowed though their signatures, i.e. the
anagram, differ in one.

【在 a*******d 的大作中提到】
: My algorithm:
: 1. Levelize the words in the dictionary based on the length of the string
: incrementally, and compute the signature of the string. (for example, the
: signature for "and" is "adn", the signature for "apple" is "aelpp".
: 2. hash1 contains all the letters in the alphabet.
: 3. for (level=2; level <= Max; level++)
: for each entry w1 in hash1
: for each word w2 in level
: if the signatures of w1 and w2 only differ one
: if the w1 and w2 only differ in one letter
h*****n
发帖数: 4747
67
bless
a*******6
发帖数: 520
68
怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
O(n)的话不就两行代码吗？

alphabet
is
that it
in
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
a*******6
发帖数: 520
69
倒过来比较好
相当于BFS一个DAG
如果预存两个tries，一个正的，一个倒的，复杂度是O(NM)，N是字典大小（单词个数），M是字符集
大小

【在 i**d 的大作中提到】
: 第二题递归来做不就可以了么。
: 首先把字典里的词按照从长到短排序
: 然后对每一个单词检查是否存在一条到长度为1的单词的路径。
: 复杂度为O(Nk) k是 word的平均长度
a*******6
发帖数: 520
70
不知道问第四题是什么意思？
n<
is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
相关主题
● Leetcode word ladder 求助！● LeetCode: Word Ladder
● 这段word ladder II怎么改？● 转划单词题的优解
● 这个题能有几种解法？● google 电面
进入JobHunting版参与讨论
w****x
发帖数: 2483
71
字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
后一次查询只需要O(n)时间复杂度
a*****n
发帖数: 158
72
这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
B*******1
发帖数: 2454
73
how many memory you need for this?

【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
a*******6
发帖数: 520
74
。。。不会超过the size of the input。。。而且实际上会远远小于Input Size。。。
当然可以先构造一个N个节点的图

【在 a*****n 的大作中提到】
: 这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
i**d
发帖数: 357
75
BFS 遍历不是O(n)的。应该是O(V+E)
如果你是的图是个dense graph的话，复杂度可以到O(N^2)

【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
s****a
发帖数: 528
76
1. build hash table for words in : wordsSet
2. sort the words from shortest to longest: wordsArray
while(!wordsArray.empty())
{
string word = wordsArray.back();
wordsArray.pop_back();
int maxLength = word.length();
if (maxLength == 1) return 1;
if (wordsSet.find(word) == wordsSet.end())
continue; // this word is already tested
wordsSet.erase(word);
WordsStack subWordsStack;
subWordsStack.push(word);
// check if the word can be build up from 1 to maxlength
while(!subWordsStack.empty())
{
string newWord = subWordsStack.top();
subWordsStack.pop();
if (newWord.length() == 1)
return maxLength; // found
for (int i=0; i {
string subword = newWord;
subword.erase(i);
if (wordsSet.find(subword) != wordsSet.end())
{
wordsArray.push_back(subword);
wordsSet.erase(subword);
};
}
} // did not find
}
s****a
发帖数: 528
77
sort the words will cost nLog(n)
search will cost kn, where the k is the average length of the word.
q****x
发帖数: 7404
78
思路？太长。

【在 s****a 的大作中提到】
: 1. build hash table for words in : wordsSet
: 2. sort the words from shortest to longest: wordsArray
: while(!wordsArray.empty())
: {
: string word = wordsArray.back();
: wordsArray.pop_back();
: int maxLength = word.length();
: if (maxLength == 1) return 1;
: if (wordsSet.find(word) == wordsSet.end())
: continue; // this word is already tested
n*******w
发帖数: 687
79
这个感觉比较好点。
乍看是O(m!)，m是input string的长度。
不过查dictionary剪枝了，会很快。
存个O(N^2)的二位数组再dfs有点占空间。算是brute force了。
N是dictionary中words数量。
不白板code可以考虑图，不然不好写。

【在 g*********e 的大作中提到】
:
: ,
: false
: I didn't quite understand your post.
: I mean
: foo(string){
: if(strlen(string)==1) {
: if string exist return true;
: else return false;
: }
e*****w
发帖数: 144
80
应该是考O(log n)的Fib(n)算法吧。

？？

【在 a*******6 的大作中提到】
: 怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
: O(n)的话不就两行代码吗？
:
: alphabet
: is
: that it
: in
: the
相关主题
● leetcode wordladder2 求助！(solved)● String list如何排序
● 问个google老题的最佳解法● FB面试题一道 求解
● word ladder II 找所有而不是第一个的最短路径一般咋做的？● 攒RP发A家第一轮电面
进入JobHunting版参与讨论
r*******n
发帖数: 3020
81
应该是看写的是不是漂亮

【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
r*******n
发帖数: 3020
82
俺给你想法一样,
优化方法, 把中间结果放掉hashtable里,
中间结果是满足条件的word, 不用再调用函数判断了,
如果在hashtable就返回真.
foo(string){
if(strlen(string)==1) {
if string exist return true;
else return false;
}
else if(string don't exist) return false;
else return foo(tring) | foo(sring)...;
}

【在 g*********e 的大作中提到】
:
: ,
: false
: I didn't quite understand your post.
: I mean
: foo(string){
: if(strlen(string)==1) {
: if string exist return true;
: else return false;
: }
w****x
发帖数: 2483
83
图的遍历怎么会是O(n^2)???
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度
a*******6
发帖数: 520
84
O(n)的还有什么漂亮不漂亮一说。。。O(logn)的能写好倒是很漂亮

【在 r*******n 的大作中提到】
: 应该是看写的是不是漂亮
f*******t
发帖数: 7549
85
fib不是有公式吗，O(1)，哈哈
m**q
发帖数: 189
86
第二题以前讨论过，我觉得火鸡的方法不错
http://www.mitbbs.com/article_t/JobHunting/31952487.html

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
r*******g
发帖数: 1335
87
我只知道转化成矩阵相乘的算法可以做大O(logn)，但是面试时要写出来也不容易吧？

【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
z******t
发帖数: 59
88
第二轮的题目O(1)时间找出栈中的最小值，有只需要O(1)辅助空间的解法，见下述博客：
http://codercareer.blogspot.com/2011/09/no-02-stack-with-functi

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
Y**B
发帖数: 144
89
第二题怎么做,谁能给个解?
p*****2
发帖数: 21240
90
第二题不就是个DP题吗？
把每一个单词过一遍。过的时候
1. 如果单词短于已知最长单词，直接退出。
2. 循环把单词的某一个字母去掉，如果剩下的在字典里，递归调短一个字母的单词
如果有一个pass，则这个单词pass。如果全部fail，则这个单词fail
3.把pass， fail结果放到hashtable里，避免重复计算
相关主题
● Groupon 2面 面经● 面筋（已狗家为主，因为其余记不清了）
● 借人气请教个G题● 问道amazon的面试题
● 请问facebook末位淘汰是怎样的哦 有offer了但是怕去了不能survive● Java programming question
进入JobHunting版参与讨论
g*********e
发帖数: 14401
91
第二题是：Suppose I give you a dictionary
of words; the size of the dictionary is finite. Each word in the
dictionary is composed from a set of characters; the size of the alphabet is
finite. Find the longest word in the dictionary with the property that it
can be built one character at a time and at each step is a valid word in the
dictionary.
e.g. Dictionary = Webster
Alphabet = A-z
a -> at -> cat -> chat -> chart -> charts -> …..
估计挂在这道题上面了, 当时说完解法在算复杂度那里纠结了一会儿。先不说解法，打
算面google的自己想一下能不能很快想出解法。
这题感觉很眼熟啊 记得以前有人面google也说过
我的想法是把所有词按照长度排序，recursively search 比如 [abcd]->search [abc]
[acd] [bcd] [abd]
然后可以对当前search到的词进行标记，要是最终这个[abcd]search到有解，就找到了
最长。
要是没解，被标记的这些断词都没解，今后就不用search他们了。
复杂度是O(n) n=number of total words in the dictionary
g*********e
发帖数: 14401
92
我晕 是个坟
p*****2
发帖数: 21240
93

is
the
我觉得不需要sort，sort还要花nlogn的时间。

【在 g*********e 的大作中提到】
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite. Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
: e.g. Dictionary = Webster
: Alphabet = A-z
: a -> at -> cat -> chat -> chart -> charts -> …..
: 估计挂在这道题上面了, 当时说完解法在算复杂度那里纠结了一会儿。先不说解法，打
g**********y
发帖数: 14569
94
直接做效率不高，我当时的解法跟appleseed说的是一样的，就是分单词长度计算，从
短到长，每一层结果放在set里。计算到没有解时，上一层的任意一个单词都是解。

=======================================================================
这是code:
public void find() {
int N = 30;
String content = FileHelper.readFile(DIR + "/WORD.LST");
String[] words = content.split("\n");
HashSet[] set = new HashSet[30];
HashMap[] map = new HashMap[N];
for (int i=0; i set[i] = new HashSet();
map[i] = new HashMap();
}

for (String word : words) {
set[word.length()].add(word);
}


for (String word : set[1]) {
map[1].put(word, "");
}

int i=2;
while (i < N) {
for (String word : set[i]) {
for (int j=0; j String shrink = word.substring(0, j) + word.substring(j+
1);
if (map[i-1].containsKey(shrink)) {
map[i].put(word, shrink);
break;
}
}
}
if (map[i].size() == 0) break;
i++;
}

String word = map[i-1].keySet().iterator().next();
for (int j=i-1; j>0; j--) {
System.out.print(word + " - ");
word = map[j].get(word);
}
}

【在 p*****2 的大作中提到】
: 第二题不就是个DP题吗？
: 把每一个单词过一遍。过的时候
: 1. 如果单词短于已知最长单词，直接退出。
: 2. 循环把单词的某一个字母去掉，如果剩下的在字典里，递归调短一个字母的单词
: 如果有一个pass，则这个单词pass。如果全部fail，则这个单词fail
: 3.把pass， fail结果放到hashtable里，避免重复计算
w****o
发帖数: 2260
95
顶

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
r**********1
发帖数: 13
96
DP可以这样做吧，就是给定个单词，在其左右不停添加新字母（a-z，26个），看新单
词在不在字典里，取最大长度
int findlongest(string W[], int n){
先建个hashtable包含所有单词
int longest = 0;
for i=1 to n //扫描每个单词
{
string w = W[i]; //当前的单词
int t = 1+max(furthertest(W[i], 0), furthertest(W[i], 1));
longest = max(t, longest);
}
return longest;
}
int furthertest(string s, bool tryleft)
{
int maxcount = 0;
if (tryleft) //if tryleft==1, 往左边添
{
for (int i=0; i < 26; ++i)
{
string newword(1, i+'a');
newword.append(s);
if (hash(newword))
{
maxcount=max(maxcount, 1+max(furthertest(newword, 0),
furthertest(newword, 1));
}
}
}else{ //if tryleft==0, 往右边添
for (int i=0; i < 26; ++i)
{
string newword(s);
newword.append(1, i+'a');
if (hash(newword))
{
maxcount=max(maxcount, 1+max(furthertest(newword, 0),
furthertest(newword, 1));
}
}
}
return maxcount;
}
如果再建个hashtable保存已经测试过的单词，已经测试过，就不再测试，这样行不通
，因为有可能是先测and，再测到an，如果先按单词长度给排个序倒是可以
复杂度应该是O(nm^2)，n是字典中单词个数，m是最长单词长度，因为递归树的高度是m
r**********1
发帖数: 13
97

这步不对吧，比如abcd,abcde两个在，而且先扫描到，后来了个a

【在 p*****2 的大作中提到】
: 第二题不就是个DP题吗？
: 把每一个单词过一遍。过的时候
: 1. 如果单词短于已知最长单词，直接退出。
: 2. 循环把单词的某一个字母去掉，如果剩下的在字典里，递归调短一个字母的单词
: 如果有一个pass，则这个单词pass。如果全部fail，则这个单词fail
: 3.把pass， fail结果放到hashtable里，避免重复计算
g**********y
发帖数: 14569
98
新添的字母可以在单词的中间。

【在 r**********1 的大作中提到】
: DP可以这样做吧，就是给定个单词，在其左右不停添加新字母（a-z，26个），看新单
: 词在不在字典里，取最大长度
: int findlongest(string W[], int n){
: 先建个hashtable包含所有单词
: int longest = 0;
: for i=1 to n //扫描每个单词
: {
: string w = W[i]; //当前的单词
: int t = 1+max(furthertest(W[i], 0), furthertest(W[i], 1));
: longest = max(t, longest);
p*****2
发帖数: 21240
99

啥意思呀？如果abcd先扫到的话，因为abcde比它长，所以会继续扫。

【在 r**********1 的大作中提到】
:
: 这步不对吧，比如abcd,abcde两个在，而且先扫描到，后来了个a
c****p
发帖数: 6474
100
插嘴问一句，第一题最好的时间复杂度是多少

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
相关主题
● 一道Ｇ家店面题● 这个题能有几种解法？
● Leetcode word ladder 求助！● LeetCode: Word Ladder
● 这段word ladder II怎么改？● 转划单词题的优解
进入JobHunting版参与讨论
r**********1
发帖数: 13
101

是啊，a来了呢，比abcd短，就不会继续了

【在 p*****2 的大作中提到】
:
: 啥意思呀？如果abcd先扫到的话，因为abcde比它长，所以会继续扫。
p*****2
发帖数: 21240
102

如果已经找到比a长的pass的单词，还需要扫a吗？

【在 r**********1 的大作中提到】
:
: 是啊，a来了呢，比abcd短，就不会继续了
x*******5
发帖数: 152
103
凑热闹，给个runable的code
/*Descriptoin: given a dictionary of words, 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
Input: Dict& dict, vector v, vector & result
Output: void
K.O.: back tracking
*/
vector String::generate_next_string(string& s, String::Dict& dict){
string t;
vector v;
set temp;
for(int i=0;i<26;i++){

for(int j=0;j<=s.length();j++){
t=s;
t.insert(t.begin()+j,'a'+i);

if(dict.find(t)!=dict.end())
temp.insert(t);
}



}
set::iterator j;
for(j=temp.begin();j!=temp.end();j++)
v.push_back(*j);
return v;

}
void String::find_largest_word_rec(Dict& dict, vector v, vector<
string> & result){
unsigned int i,j,count=0;
for(i=0;i vector t=String::generate_next_string(v[i],dict);
if(!t.size()) {
count++;
if(count==v.size()-1) return;
}
else{

for(j=0;j
result.push_back(t[j]);

find_largest_word_rec(dict,t,result);
}


}
}
string String::find_largest_word(Dict& dict, vector v, vector >& result){
find_largest_word_rec(dict,v,result);
sort(result.begin(),result.end(),String::comparelength);
return result[0];
}
p*****2
发帖数: 21240
104

我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
词长度分类了，是不是应该用binary search呢？

【在 g**********y 的大作中提到】
: 直接做效率不高，我当时的解法跟appleseed说的是一样的，就是分单词长度计算，从
: 短到长，每一层结果放在set里。计算到没有解时，上一层的任意一个单词都是解。
:
: =======================================================================
: 这是code:
: public void find() {
: int N = 30;
: String content = FileHelper.readFile(DIR + "/WORD.LST");
: String[] words = content.split("\n");
: HashSet[] set = new HashSet[30];
l****a
发帖数: 2361
105
good luck!
r**********1
发帖数: 13
106
对的，
偶题意理解错了，还以为可以从几个字母开始往上涨，原来是需要从1个字母开始往上涨

【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
D********g
发帖数: 650
107
第二题，我的code，主要算法是recursion + memoization，有没有人能分析一下这个
算法的复杂度？
static String findLongestDecomposableWord(Set dict) {
String longest = null;
Set mem = new HashSet();
for (String word : dict) {
if (findLongestDecomposableWordInternal(word, mem, dict)) {
if (longest == null || word.length() > longest.length()) {
longest = word;
}
}
}

return longest;
}

static boolean findLongestDecomposableWordInternal(String word, Set<
String> mem, Set dict) {
if (word == null || word.isEmpty() || !dict.contains(word)) {
return false;
}
if (word.length() == 1) {
return dict.contains(word);
}
if (mem.contains(word)) {
return true;
}

for (int i = 0; i < word.length(); ++i) {
String newWord = word.substring(0, i) + word.substring(i+1);
boolean isIn = findLongestDecomposableWordInternal(newWord, mem,
dict);
if (isIn) {
mem.add(word);
return true;
}
}
return false;
}

is
the

【在 J*********n 的大作中提到】
: 上周五两轮电面，back to back, 刚刚在地铁里接到hr的电话，sigh...
: 回馈本版，祝大家好运
: 第一轮: 第一题Fibonacci数,我跟面试官说这个题目我知道，你要不要问其它的问题，
: 他说不用，然后我直接写了迭代的解法, 7~8分钟搞定。
: 第二题是：Suppose I give you a dictionary
: of words; the size of the dictionary is finite.  Each word in the
: dictionary is composed from a set of characters; the size of the alphabet is
: finite. Find the longest word in the dictionary with the property that it
: can be built one character at a time and at each step is a valid word in the
: dictionary.
j*****j
发帖数: 201
108
同不明白，火鸡的做法和dp的做法相比优越在哪里？复杂度是什么？

【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
j*****j
发帖数: 201
109
同不明白，火鸡的做法和dp的做法相比优越在哪里？复杂度是什么？

【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 请问facebook末位淘汰是怎样的哦 有offer了但是怕去了不能survive● LeetCode: Word Ladder
● 面筋（已狗家为主，因为其余记不清了）● 转划单词题的优解
● 问道amazon的面试题● google 电面
● Java programming question● leetcode wordladder2 求助！(solved)
● 一道Ｇ家店面题● 问个google老题的最佳解法
● Leetcode word ladder 求助！● word ladder II 找所有而不是第一个的最短路径一般咋做的？
● 这段word ladder II怎么改？● String list如何排序
● 这个题能有几种解法？● FB面试题一道 求解
相关话题的讨论汇总
话题: string话题: word话题: dictionary话题: return话题: dict

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑