J*n
2 楼
上周五两轮电面，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能有好结果.
回馈本版，祝大家好运
第一轮: 第一题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能有好结果.
z*r
3 楼
根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
排名不分先后，奖励不重复:
beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
tangbohu GentleWen
以上ID每人5个包子，提名截止时间今晚东部11点
排名不分先后，奖励不重复:
beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
tangbohu GentleWen
以上ID每人5个包子，提名截止时间今晚东部11点
L*y
4 楼
【在 L****y 的大作中提到】
: macys 180 块一个， martha stewart, 是不是和你们说的神锅差不多？
A*u
5 楼
没人感谢？
多些分享
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.
多些分享
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.
b*7
6 楼
算了我两次是不是给10个包子啊？
L*y
7 楼
【在 L****y 的大作中提到】
: macys 180 块一个， martha stewart, 是不是和你们说的神锅差不多？
z*e
8 楼
再接再厉,赞面筋
2用A*吗？
2用A*吗？
d*3
9 楼
现在流行说：带来正能量！
另外，小老虎兄弟一定要算一个吧
另外，小老虎兄弟一定要算一个吧
c*h
10 楼
木有staub和LC好
【在 L****y 的大作中提到】
: macys 180 块一个， martha stewart, 是不是和你们说的神锅差不多？
【在 L****y 的大作中提到】
: macys 180 块一个， martha stewart, 是不是和你们说的神锅差不多？
q*x
11 楼
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.
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.
g*1
12 楼
赫然看到两个rock888
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
L*y
13 楼
你说的这种那里有卖， 店里看不到？
【在 c*****h 的大作中提到】
: 木有staub和LC好
【在 c*****h 的大作中提到】
: 木有staub和LC好
H*M
14 楼
觉得妮答得都挺好的阿
为什么拒了？
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.
为什么拒了？
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.
z*r
15 楼
对，请给出ID，俺回头专门弄个汇总贴
【在 d********3 的大作中提到】
: 现在流行说：带来正能量！
: 另外，小老虎兄弟一定要算一个吧
【在 d********3 的大作中提到】
: 现在流行说：带来正能量！
: 另外，小老虎兄弟一定要算一个吧
t*r
16 楼
你去的店没有。你去williams sonoma 看看
d*y
17 楼
thanks
z*r
18 楼
人工统计，厚厚。俺补充一下，不重复
【在 g*******1 的大作中提到】
: 赫然看到两个rock888
:
: fatboyslim
【在 g*******1 的大作中提到】
: 赫然看到两个rock888
:
: fatboyslim
i*e
19 楼
我在梅西见过LC
【在 t*******r 的大作中提到】
: 你去的店没有。你去williams sonoma 看看
【在 t*******r 的大作中提到】
: 你去的店没有。你去williams sonoma 看看
b*g
20 楼
hr 不错，还给你打电话通知结果。一般不是默据吗?
bless for other offers， anyway。
bless for other offers， anyway。
a*n
21 楼
十马是正面的支持呀
是不是长期坚持不懈地和果轮做输死地斗争呀
哇哈哈
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
是不是长期坚持不懈地和果轮做输死地斗争呀
哇哈哈
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
s*l
22 楼
感觉还行啊，怎么就被拒了呢。
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.
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*r
23 楼
然后你转给俺5个也行
【在 b********7 的大作中提到】
: 算了我两次是不是给10个包子啊？
【在 b********7 的大作中提到】
: 算了我两次是不是给10个包子啊？
b*e
24 楼
bless, 多谢分享。
第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
后就可以找到最长的单词了。
第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
后就可以找到最长的单词了。
L*e
25 楼
我老一放假就挖俩大坑，应该酌情奖励双份吧？
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
a*2
26 楼
赞面经
bless for T and L
bless for T and L
r*8
27 楼
那我拿双份?
【在 g*******1 的大作中提到】
: 赫然看到两个rock888
:
: fatboyslim
【在 g*******1 的大作中提到】
: 赫然看到两个rock888
:
: fatboyslim
S*0
28 楼
时间复杂度是多少？
O(n)?
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
O(n)?
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
g*1
29 楼
可以给我转一份，哈哈
【在 r*****8 的大作中提到】
: 那我拿双份?
【在 r*****8 的大作中提到】
: 那我拿双份?
B*1
30 楼
a -> ba->nba
假设ba,nba都是valid，你的trie每次都从头lookup？
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
假设ba,nba都是valid，你的trie每次都从头lookup？
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
r*8
31 楼
完了, 版主说不重复, 你要是不指出来, 说不定还可以分你一点, 现在应该罚你包子了
【在 g*******1 的大作中提到】
: 可以给我转一份，哈哈
【在 g*******1 的大作中提到】
: 可以给我转一份，哈哈
g*e
32 楼
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到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
p*c
33 楼
我呢？我一向坚定不移地支持pda板块
a*d
34 楼
tree or trie? I'm confused.
z*r
35 楼
已加入
【在 p***c 的大作中提到】
: 我呢？我一向坚定不移地支持pda板块
【在 p***c 的大作中提到】
: 我呢？我一向坚定不移地支持pda板块
a*d
36 楼
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.
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.
z*r
37 楼
哪天提醒俺一下，俺个人再奖励你一次不就行了
【在 L*****e 的大作中提到】
: 我老一放假就挖俩大坑，应该酌情奖励双份吧？
:
: fatboyslim
【在 L*****e 的大作中提到】
: 我老一放假就挖俩大坑，应该酌情奖励双份吧？
:
: fatboyslim
b*e
38 楼
嗯，我应该是把题目理解错了。
但是，要判断 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
r*e
39 楼
吃包子。多谢老大。
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
g*e
40 楼
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).
L*e
41 楼
多谢版大！
【在 z**r 的大作中提到】
: 哪天提醒俺一下，俺个人再奖励你一次不就行了
【在 z**r 的大作中提到】
: 哪天提醒俺一下，俺个人再奖励你一次不就行了
b*e
42 楼
我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。
比如这个单词是“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.
A*D
43 楼
泪流满面啊
g*e
44 楼
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.
z*3
45 楼
这算是进了PDA中央委员会了，
作为委员坚决拥护以zher同志为核心的常委领导，并向新上任的担任殖民地特首的老范
表示祝贺
作为委员坚决拥护以zher同志为核心的常委领导，并向新上任的担任殖民地特首的老范
表示祝贺
g*e
46 楼
,
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）.
c*h
47 楼
我也灌水多多啊。
i*d
48 楼
第二题递归来做不就可以了么。
首先把字典里的词按照从长到短排序
然后对每一个单词检查是否存在一条到长度为1的单词的路径。
复杂度为O(Nk) k是 word的平均长度
首先把字典里的词按照从长到短排序
然后对每一个单词检查是否存在一条到长度为1的单词的路径。
复杂度为O(Nk) k是 word的平均长度
b*l
49 楼
你是不是捣乱了？:)
【在 c*h 的大作中提到】
: 我也灌水多多啊。
【在 c*h 的大作中提到】
: 我也灌水多多啊。
k*t
50 楼
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
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
s*o
51 楼
最近我也码了不少字啦
h*n
52 楼
bless
T*g
53 楼
我呀！ 我一直和老大穿一条裤子啊！
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
a*6
54 楼
怎么没人讨论第一题呢？是说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.
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.
c*4
55 楼
赞老大~正好没吃饭呢.. 吃包子~~ :D
a*6
56 楼
倒过来比较好
相当于BFS一个DAG
如果预存两个tries，一个正的，一个倒的，复杂度是O(NM)，N是字典大小（单词个数），M是字符集
大小
【在 i**d 的大作中提到】
: 第二题递归来做不就可以了么。
: 首先把字典里的词按照从长到短排序
: 然后对每一个单词检查是否存在一条到长度为1的单词的路径。
: 复杂度为O(Nk) k是 word的平均长度
相当于BFS一个DAG
如果预存两个tries，一个正的，一个倒的，复杂度是O(NM)，N是字典大小（单词个数），M是字符集
大小
【在 i**d 的大作中提到】
: 第二题递归来做不就可以了么。
: 首先把字典里的词按照从长到短排序
: 然后对每一个单词检查是否存在一条到长度为1的单词的路径。
: 复杂度为O(Nk) k是 word的平均长度
y*b
57 楼
还有我，支持好几个月了
a*6
58 楼
不知道问第四题是什么意思？
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.
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.
d*3
59 楼
tangbohu
【在 z**r 的大作中提到】
: 对，请给出ID，俺回头专门弄个汇总贴
【在 z**r 的大作中提到】
: 对，请给出ID，俺回头专门弄个汇总贴
w*x
60 楼
字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
后一次查询只需要O(n)时间复杂度
后一次查询只需要O(n)时间复杂度
r*e
61 楼
可不可以提名自己啊。我的贴都很有营养啊。
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
a*n
62 楼
这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
F*y
63 楼
多谢版大
B*1
64 楼
how many memory you need for this?
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
u*d
65 楼
tangbohu
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
a*6
66 楼
。。。不会超过the size of the input。。。而且实际上会远远小于Input Size。。。
当然可以先构造一个N个节点的图
【在 a*****n 的大作中提到】
: 这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
当然可以先构造一个N个节点的图
【在 a*****n 的大作中提到】
: 这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
f*0
67 楼
哈，多谢版大！
i*d
68 楼
BFS 遍历不是O(n)的。应该是O(V+E)
如果你是的图是个dense graph的话，复杂度可以到O(N^2)
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
如果你是的图是个dense graph的话，复杂度可以到O(N^2)
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
G*n
69 楼
我很震惊木有我！！！！！！！！！！！！！！！！！！！
s*a
70 楼
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
}
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
}
c*4
71 楼
提名唐伯虎
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
fatboyslim
【在 z**r 的大作中提到】
: 根据最近版面情况，感谢以下ID对本版的长期的正面的支持。如有遗漏，请大家提名。
: 排名不分先后，奖励不重复:
: beattie furthermore FatherJoey Subbus McGrady rottenapple chance04 rock888
: ft3499100 clc photonth zjhzhou upload veggie huangshiren derk zhizunbao123
: autumnworm plus lychx guohun dachouchou creeper TheSun diandian23 fatboyslim
: ppgame buzhidao77 daye520 wsninmit superdmv flatbean5 LeftEye AMEXCARD
: goodbug ablution GoTouch danielfeng mmd weidong tjhaven arthury shuihaizi
: Zhane Lizi gjg dsb zjn paulc cr2069 antee goback211 crh shubiao TimeBug yanb
: tangbohu GentleWen
: 以上ID每人5个包子，提名截止时间今晚东部11点
s*a
72 楼
sort the words will cost nLog(n)
search will cost kn, where the k is the average length of the word.
search will cost kn, where the k is the average length of the word.
t*n
73 楼
也有份啊。多谢
q*x
74 楼
思路？太长。
【在 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
【在 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
t*n
75 楼
是啊。老虎兄的都是精华，而且有问必答。
【在 c******4 的大作中提到】
: 提名唐伯虎
:
: fatboyslim
【在 c******4 的大作中提到】
: 提名唐伯虎
:
: fatboyslim
n*w
76 楼
这个感觉比较好点。
乍看是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;
: }
乍看是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;
: }
F*y
77 楼
同推荐唐伯虎兄
e*w
78 楼
应该是考O(log n)的Fib(n)算法吧。
？？
【在 a*******6 的大作中提到】
: 怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
: O(n)的话不就两行代码吗？
:
: alphabet
: is
: that it
: in
: the
？？
【在 a*******6 的大作中提到】
: 怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
: O(n)的话不就两行代码吗？
:
: alphabet
: is
: that it
: in
: the
L*e
79 楼
那你是不是只顾遮挡自己，把老大的PG露出来了？
【在 T*****g 的大作中提到】
: 我呀！ 我一直和老大穿一条裤子啊！
:
: fatboyslim
【在 T*****g 的大作中提到】
: 我呀！ 我一直和老大穿一条裤子啊！
:
: fatboyslim
r*n
80 楼
应该是看写的是不是漂亮
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
w*t
81 楼
真的？几尺腰围啊您？
【在 T*****g 的大作中提到】
: 我呀！ 我一直和老大穿一条裤子啊！
:
: fatboyslim
【在 T*****g 的大作中提到】
: 我呀！ 我一直和老大穿一条裤子啊！
:
: fatboyslim
r*n
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;
: }
优化方法, 把中间结果放掉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
83 楼
图的遍历怎么会是O(n^2)???
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度
a*6
84 楼
O(n)的还有什么漂亮不漂亮一说。。。O(logn)的能写好倒是很漂亮
【在 r*******n 的大作中提到】
: 应该是看写的是不是漂亮
【在 r*******n 的大作中提到】
: 应该是看写的是不是漂亮
f*t
85 楼
fib不是有公式吗，O(1)，哈哈
m*q
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.
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
87 楼
我只知道转化成矩阵相乘的算法可以做大O(logn)，但是面试时要写出来也不容易吧？
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
z*t
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.
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
89 楼
上周五两轮电面，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能有好结果.
回馈本版，祝大家好运
第一轮: 第一题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
90 楼
没人感谢？
多些分享
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.
多些分享
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
91 楼
再接再厉,赞面筋
2用A*吗？
2用A*吗？
q*x
92 楼
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.
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
93 楼
觉得妮答得都挺好的阿
为什么拒了？
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.
为什么拒了？
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
94 楼
thanks
b*g
95 楼
hr 不错，还给你打电话通知结果。一般不是默据吗?
bless for other offers， anyway。
bless for other offers， anyway。
s*l
96 楼
感觉还行啊，怎么就被拒了呢。
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.
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
97 楼
bless, 多谢分享。
第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
后就可以找到最长的单词了。
第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
后就可以找到最长的单词了。
a*2
98 楼
赞面经
bless for T and L
bless for T and L
S*0
99 楼
时间复杂度是多少？
O(n)?
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
O(n)?
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
B*1
100 楼
a -> ba->nba
假设ba,nba都是valid，你的trie每次都从头lookup？
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
假设ba,nba都是valid，你的trie每次都从头lookup？
【在 b***e 的大作中提到】
: bless, 多谢分享。
: 第二题用trie吧，先把字典里的单词都放进trie里，然后遍历trie，看是否每一个从
: root到叶节点的中间节点都有单词对应，如果有，记录该条路径的长度，然后，比较以
: 后就可以找到最长的单词了。
g*e
101 楼
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
102 楼
tree or trie? I'm confused.
a*d
103 楼
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.
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
104 楼
嗯，我应该是把题目理解错了。
但是，要判断 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
105 楼
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
106 楼
我不知道我是否理解清楚了你解题的思路。我对你的解法的是这么看的。
比如这个单词是“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
107 楼
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
108 楼
,
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
109 楼
第二题递归来做不就可以了么。
首先把字典里的词按照从长到短排序
然后对每一个单词检查是否存在一条到长度为1的单词的路径。
复杂度为O(Nk) k是 word的平均长度
首先把字典里的词按照从长到短排序
然后对每一个单词检查是否存在一条到长度为1的单词的路径。
复杂度为O(Nk) k是 word的平均长度
k*t
110 楼
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
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
111 楼
bless
a*6
112 楼
怎么没人讨论第一题呢？是说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.
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
113 楼
倒过来比较好
相当于BFS一个DAG
如果预存两个tries，一个正的，一个倒的，复杂度是O(NM)，N是字典大小（单词个数），M是字符集
大小
【在 i**d 的大作中提到】
: 第二题递归来做不就可以了么。
: 首先把字典里的词按照从长到短排序
: 然后对每一个单词检查是否存在一条到长度为1的单词的路径。
: 复杂度为O(Nk) k是 word的平均长度
相当于BFS一个DAG
如果预存两个tries，一个正的，一个倒的，复杂度是O(NM)，N是字典大小（单词个数），M是字符集
大小
【在 i**d 的大作中提到】
: 第二题递归来做不就可以了么。
: 首先把字典里的词按照从长到短排序
: 然后对每一个单词检查是否存在一条到长度为1的单词的路径。
: 复杂度为O(Nk) k是 word的平均长度
a*6
114 楼
不知道问第四题是什么意思？
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.
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
115 楼
字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
后一次查询只需要O(n)时间复杂度
后一次查询只需要O(n)时间复杂度
a*n
116 楼
这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
B*1
117 楼
how many memory you need for this?
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
a*6
118 楼
。。。不会超过the size of the input。。。而且实际上会远远小于Input Size。。。
当然可以先构造一个N个节点的图
【在 a*****n 的大作中提到】
: 这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
当然可以先构造一个N个节点的图
【在 a*****n 的大作中提到】
: 这种DICTIONARY的题目能用TRIE吗？那内存得站多少。。。
i*d
119 楼
BFS 遍历不是O(n)的。应该是O(V+E)
如果你是的图是个dense graph的话，复杂度可以到O(N^2)
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
如果你是的图是个dense graph的话，复杂度可以到O(N^2)
【在 w****x 的大作中提到】
: 字典那题可以先做pre-processing, O(N^2)把word变成图, 然后每次再做便利, 预处理
: 后一次查询只需要O(n)时间复杂度
s*a
120 楼
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
}
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
121 楼
sort the words will cost nLog(n)
search will cost kn, where the k is the average length of the word.
search will cost kn, where the k is the average length of the word.
q*x
122 楼
思路？太长。
【在 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
【在 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
123 楼
这个感觉比较好点。
乍看是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;
: }
乍看是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
124 楼
应该是考O(log n)的Fib(n)算法吧。
？？
【在 a*******6 的大作中提到】
: 怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
: O(n)的话不就两行代码吗？
:
: alphabet
: is
: that it
: in
: the
？？
【在 a*******6 的大作中提到】
: 怎么没人讨论第一题呢？是说O(n)时间求第n个Fibonacci数，还是O(logn)时间啊？？？
: O(n)的话不就两行代码吗？
:
: alphabet
: is
: that it
: in
: the
r*n
125 楼
应该是看写的是不是漂亮
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
r*n
126 楼
俺给你想法一样,
优化方法, 把中间结果放掉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;
: }
优化方法, 把中间结果放掉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
127 楼
图的遍历怎么会是O(n^2)???
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度
图可以用邻接表表示, 不一定非要用矩阵...
一次O(n^2)的预处理， 剩下每次查询都是O(n)的最坏复杂度， 从同一节点开始遍历的
查询， 实际问题远远没到O(n)的程度
a*6
128 楼
O(n)的还有什么漂亮不漂亮一说。。。O(logn)的能写好倒是很漂亮
【在 r*******n 的大作中提到】
: 应该是看写的是不是漂亮
【在 r*******n 的大作中提到】
: 应该是看写的是不是漂亮
f*t
129 楼
fib不是有公式吗，O(1)，哈哈
m*q
130 楼
第二题以前讨论过，我觉得火鸡的方法不错
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.
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
131 楼
我只知道转化成矩阵相乘的算法可以做大O(logn)，但是面试时要写出来也不容易吧？
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
【在 e*****w 的大作中提到】
: 应该是考O(log n)的Fib(n)算法吧。
:
: ？？
z*t
132 楼
第二轮的题目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.
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
133 楼
第二题怎么做,谁能给个解?
p*2
134 楼
第二题不就是个DP题吗？
把每一个单词过一遍。过的时候
1. 如果单词短于已知最长单词，直接退出。
2. 循环把单词的某一个字母去掉，如果剩下的在字典里，递归调短一个字母的单词
如果有一个pass，则这个单词pass。如果全部fail，则这个单词fail
3.把pass， fail结果放到hashtable里，避免重复计算
把每一个单词过一遍。过的时候
1. 如果单词短于已知最长单词，直接退出。
2. 循环把单词的某一个字母去掉，如果剩下的在字典里，递归调短一个字母的单词
如果有一个pass，则这个单词pass。如果全部fail，则这个单词fail
3.把pass， fail结果放到hashtable里，避免重复计算
g*e
135 楼
第二题是：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
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
136 楼
我晕 是个坟
p*2
137 楼
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
138 楼
直接做效率不高，我当时的解法跟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();
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
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里，避免重复计算
短到长，每一层结果放在set里。计算到没有解时，上一层的任意一个单词都是解。
=======================================================================
这是code:
public void find() {
int N = 30;
String content = FileHelper.readFile(DIR + "/WORD.LST");
String[] words = content.split("\n");
HashSet
HashMap
for (int i=0; i
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
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
139 楼
顶
【在 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 的大作中提到】
: 上周五两轮电面，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
140 楼
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
词在不在字典里，取最大长度
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
141 楼
这步不对吧，比如abcd,abcde两个在，而且先扫描到，后来了个a
【在 p*****2 的大作中提到】
: 第二题不就是个DP题吗？
: 把每一个单词过一遍。过的时候
: 1. 如果单词短于已知最长单词，直接退出。
: 2. 循环把单词的某一个字母去掉，如果剩下的在字典里，递归调短一个字母的单词
: 如果有一个pass，则这个单词pass。如果全部fail，则这个单词fail
: 3.把pass， fail结果放到hashtable里，避免重复计算
g*y
142 楼
新添的字母可以在单词的中间。
【在 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);
【在 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
143 楼
啥意思呀？如果abcd先扫到的话，因为abcde比它长，所以会继续扫。
【在 r**********1 的大作中提到】
:
: 这步不对吧，比如abcd,abcde两个在，而且先扫描到，后来了个a
c*p
144 楼
插嘴问一句，第一题最好的时间复杂度是多少
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.
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*1
145 楼
是啊，a来了呢，比abcd短，就不会继续了
【在 p*****2 的大作中提到】
:
: 啥意思呀？如果abcd先扫到的话，因为abcde比它长，所以会继续扫。
p*2
146 楼
如果已经找到比a长的pass的单词，还需要扫a吗？
【在 r**********1 的大作中提到】
:
: 是啊，a来了呢，比abcd短，就不会继续了
x*5
147 楼
凑热闹，给个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 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
find_largest_word_rec(dict,v,result);
sort(result.begin(),result.end(),String::comparelength);
return result[0];
}
/*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
Output: void
K.O.: back tracking
*/
vector
string t;
vector
set
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
for(j=temp.begin();j!=temp.end();j++)
v.push_back(*j);
return v;
}
void String::find_largest_word_rec(Dict& dict, vector
string> & result){
unsigned int i,j,count=0;
for(i=0;i
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
find_largest_word_rec(dict,v,result);
sort(result.begin(),result.end(),String::comparelength);
return result[0];
}
p*2
148 楼
我还没想明白为什么我那个效率不高。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
l*a
149 楼
good luck!
r*1
150 楼
对的，
偶题意理解错了，还以为可以从几个字母开始往上涨，原来是需要从1个字母开始往上涨
【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
偶题意理解错了，还以为可以从几个字母开始往上涨，原来是需要从1个字母开始往上涨
【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
D*g
151 楼
第二题，我的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.
算法的复杂度？
static String findLongestDecomposableWord(Set
String longest = null;
Set
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
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
152 楼
同不明白，火鸡的做法和dp的做法相比优越在哪里？复杂度是什么？
【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
j*j
153 楼
同不明白，火鸡的做法和dp的做法相比优越在哪里？复杂度是什么？
【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
【在 p*****2 的大作中提到】
:
: 我还没想明白为什么我那个效率不高。DP＋剪枝应该效率没问题。你这个既然已经按单
: 词长度分类了，是不是应该用binary search呢？
相关阅读
N7 229.99 buydig alive！现在att或者verizon店里能买到off contract的iphone 4s吗我如果买920就只关注3个关键因素软软吃憋十年，完全是ceo不够种的结果。1920X1200和1280x800差别还是很大的chinese input on 920为啥板子上的风行速度慢S3免费了tmobile的bill问题ATT---14天内退货的问题N4没有LTE这个是致命缺点用过三星exhibit的谈谈感受吧木收到N4，得等周一了，郁闷。。。Samsung ATIV phone vs Nokia 920I got FREE Lumia 920 by calling ATT too !t mobile Samsung Note II $49 MIR with business advantage programSprint Galaxy S3 tethering 效果如何？Note 2 v.s. GS3??tmobile$30planN4很好啊