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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | |
q****x 发帖数: 7404 | 4 iterative deepen search?
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | |
b******g 发帖数: 1721 | 7 hr 不错,还给你打电话通知结果。一般不是默据吗?
bless for other offers, anyway。 |
s***l 发帖数: 129 | 8 感觉还行啊,怎么就被拒了呢。
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | |
|
|
S*******0 发帖数: 198 | 11 时间复杂度是多少?
O(n)?
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : bless, 多谢分享。 : 第二题用trie吧,先把字典里的单词都放进trie里,然后遍历trie,看是否每一个从 : root到叶节点的中间节点都有单词对应,如果有,记录该条路径的长度,然后,比较以 : 后就可以找到最长的单词了。
|
B*******1 发帖数: 2454 | 12 a -> ba->nba
假设ba,nba都是valid,你的trie每次都从头lookup?
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 嗯,我应该是把题目理解错了。 : 但是,要判断 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。 : 比如这个单词是“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 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | |
a*******6 发帖数: 520 | 24 怎么没人讨论第一题呢?是说O(n)时间求第n个Fibonacci数,还是O(logn)时间啊???
O(n)的话不就两行代码吗?
alphabet
is
that it
in
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题递归来做不就可以了么。 : 首先把字典里的词按照从长到短排序 : 然后对每一个单词检查是否存在一条到长度为1的单词的路径。 : 复杂度为O(Nk) k是 word的平均长度
|
a*******6 发帖数: 520 | 26 不知道问第四题是什么意思?
n<
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理 : 后一次查询只需要O(n)时间复杂度
|
a*******6 发帖数: 520 | 30 。。。不会超过the size of the input。。。而且实际上会远远小于Input Size。。。
当然可以先构造一个N个节点的图
【在 a*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这种DICTIONARY的题目能用TRIE吗?那内存得站多少。。。
|
|
|
i**d 发帖数: 357 | 31 BFS 遍历不是O(n)的。应该是O(V+E)
如果你是的图是个dense graph的话,复杂度可以到O(N^2)
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 字典那题可以先做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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : , : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么没人讨论第一题呢?是说O(n)时间求第n个Fibonacci数,还是O(logn)时间啊??? : O(n)的话不就两行代码吗? : : alphabet : is : that it : in : the
|
r*******n 发帖数: 3020 | 37 应该是看写的是不是漂亮
【在 e*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是考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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : , : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是看写的是不是漂亮
|
|
|
f*******t 发帖数: 7549 | |
m**q 发帖数: 189 | 42 第二题以前讨论过,我觉得火鸡的方法不错
http://www.mitbbs.com/article_t/JobHunting/31952487.html
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是考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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | |
q****x 发帖数: 7404 | 48 iterative deepen search?
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | |
|
|
b******g 发帖数: 1721 | 51 hr 不错,还给你打电话通知结果。一般不是默据吗?
bless for other offers, anyway。 |
s***l 发帖数: 129 | 52 感觉还行啊,怎么就被拒了呢。
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | |
S*******0 发帖数: 198 | 55 时间复杂度是多少?
O(n)?
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : bless, 多谢分享。 : 第二题用trie吧,先把字典里的单词都放进trie里,然后遍历trie,看是否每一个从 : root到叶节点的中间节点都有单词对应,如果有,记录该条路径的长度,然后,比较以 : 后就可以找到最长的单词了。
|
B*******1 发帖数: 2454 | 56 a -> ba->nba
假设ba,nba都是valid,你的trie每次都从头lookup?
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 | 61
n
the complexity wouldn't be more than the total number of words N in
dictionary.
【在 b***e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 嗯,我应该是把题目理解错了。 : 但是,要判断 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。 : 比如这个单词是“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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | |
a*******6 发帖数: 520 | 68 怎么没人讨论第一题呢?是说O(n)时间求第n个Fibonacci数,还是O(logn)时间啊???
O(n)的话不就两行代码吗?
alphabet
is
that it
in
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题递归来做不就可以了么。 : 首先把字典里的词按照从长到短排序 : 然后对每一个单词检查是否存在一条到长度为1的单词的路径。 : 复杂度为O(Nk) k是 word的平均长度
|
a*******6 发帖数: 520 | 70 不知道问第四题是什么意思?
n<
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理 : 后一次查询只需要O(n)时间复杂度
|
a*******6 发帖数: 520 | 74 。。。不会超过the size of the input。。。而且实际上会远远小于Input Size。。。
当然可以先构造一个N个节点的图
【在 a*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这种DICTIONARY的题目能用TRIE吗?那内存得站多少。。。
|
i**d 发帖数: 357 | 75 BFS 遍历不是O(n)的。应该是O(V+E)
如果你是的图是个dense graph的话,复杂度可以到O(N^2)
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 字典那题可以先做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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : , : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 怎么没人讨论第一题呢?是说O(n)时间求第n个Fibonacci数,还是O(logn)时间啊??? : O(n)的话不就两行代码吗? : : alphabet : is : that it : in : the
|
|
|
r*******n 发帖数: 3020 | 81 应该是看写的是不是漂亮
【在 e*****w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是考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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : , : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是看写的是不是漂亮
|
f*******t 发帖数: 7549 | |
m**q 发帖数: 189 | 86 第二题以前讨论过,我觉得火鸡的方法不错
http://www.mitbbs.com/article_t/JobHunting/31952487.html
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是考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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | |
p*****2 发帖数: 21240 | 90 第二题不就是个DP题吗?
把每一个单词过一遍。过的时候
1. 如果单词短于已知最长单词,直接退出。
2. 循环把单词的某一个字母去掉,如果剩下的在字典里,递归调短一个字母的单词
如果有一个pass,则这个单词pass。如果全部fail,则这个单词fail
3.把pass, fail结果放到hashtable里,避免重复计算 |
|
|
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 | |
p*****2 发帖数: 21240 | 93
is
the
我觉得不需要sort,sort还要花nlogn的时间。
【在 g*********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题是: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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题不就是个DP题吗? : 把每一个单词过一遍。过的时候 : 1. 如果单词短于已知最长单词,直接退出。 : 2. 循环把单词的某一个字母去掉,如果剩下的在字典里,递归调短一个字母的单词 : 如果有一个pass,则这个单词pass。如果全部fail,则这个单词fail : 3.把pass, fail结果放到hashtable里,避免重复计算
|
w****o 发帖数: 2260 | 95 顶
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二题不就是个DP题吗? : 把每一个单词过一遍。过的时候 : 1. 如果单词短于已知最长单词,直接退出。 : 2. 循环把单词的某一个字母去掉,如果剩下的在字典里,递归调短一个字母的单词 : 如果有一个pass,则这个单词pass。如果全部fail,则这个单词fail : 3.把pass, fail结果放到hashtable里,避免重复计算
|
g**********y 发帖数: 14569 | 98 新添的字母可以在单词的中间。
【在 r**********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这步不对吧,比如abcd,abcde两个在,而且先扫描到,后来了个a
|
c****p 发帖数: 6474 | 100 插嘴问一句,第一题最好的时间复杂度是多少
is
the
【在 J*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 | 101
是啊,a来了呢,比abcd短,就不会继续了
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 啥意思呀?如果abcd先扫到的话,因为abcde比它长,所以会继续扫。
|
p*****2 发帖数: 21240 | 102
如果已经找到比a长的pass的单词,还需要扫a吗?
【在 r**********1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 是啊,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 直接做效率不高,我当时的解法跟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 | |
r**********1 发帖数: 13 | 106 对的,
偶题意理解错了,还以为可以从几个字母开始往上涨,原来是需要从1个字母开始往上涨
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我还没想明白为什么我那个效率不高。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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 上周五两轮电面,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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我还没想明白为什么我那个效率不高。DP+剪枝应该效率没问题。你这个既然已经按单 : 词长度分类了,是不是应该用binary search呢?
|
j*****j 发帖数: 201 | 109 同不明白,火鸡的做法和dp的做法相比优越在哪里?复杂度是什么?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我还没想明白为什么我那个效率不高。DP+剪枝应该效率没问题。你这个既然已经按单 : 词长度分类了,是不是应该用binary search呢?
|