q*****n
发帖数: 311 | 1 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
的句子中插入空格，使它变成合法的句子。
他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
你的想法写代码吧，上来就没头没尾写了个
int len = strs.lenth
for (int i=0; i
for (int j=0;j<..;j++) {
}
}
问他这是什么代码，说是java，问他signature，input，output是什么。又开始加这些
string addSpaces(string input) {
...
}
想了会，说得必须有服务器什么得可以调辞典。我说不用，就用一个hashmap或者什么
的在本地就行。
string addSpaces（string input，hashmap dict）
丫又想好久，说发现还是用后缀树比较好，这样可以找最长的匹配。就改成
string addSpaces（Tree dict， string input）
想半天还是没有写出来，这时第二个面试着已敲门，我就礼貌的说了句，you are on
the right track. |
d******3
发帖数: 232 | |
f*****s
发帖数: 35 | 3 标准答案是什么？
先用字典分离第一个可能的词，后面的用递归？ |
d**e
发帖数: 6098 | 4 如何定义合法的句子？包括语法正确？
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
l*********8
发帖数: 4642 | 5 这个对没有学过自然语言处理的人太难了吧？ 我觉得能做到每个单词都在词典里面就
可以了。
【在 d**e 的大作中提到】
: 如何定义合法的句子？包括语法正确？
:
: 的。
|
l*********8
发帖数: 4642 | 6 好像可以用dp, O(k*k*n), k是单词最大长度。
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
s*****n
发帖数: 5488 | 7 尼玛这题是靠编程还是算法啊。什么叫做合法的句子。从分词到语法正确到语义？
我觉得烙印蒙掉很正常，及时他写了很多程序。
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
h****7
发帖数: 2350 | 8 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
因为他们不知道天有多高, 地有多厚. |
A**u
发帖数: 2458 | 9 我支持你灭掉烙印
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
t*****o
发帖数: 4919 | 10 狠同意！
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
|
|
y****w
发帖数: 3747 | 11 还是考基础算法比较好，list/bi-tree,是个人就学过，行了． 有没有sense很快就知
道了．不想敷衍的自己琢磨个新题． 有些复杂的玩意儿，其实也考不了多深刻，比如
人家看严伟民的书长大的就不知道你们最喜欢的几个玩意儿－－那些难么？
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
g******7
发帖数: 1532 | |
f*****g
发帖数: 99 | 13 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
要。
做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
facebook上班。
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
N**k
发帖数: 3584 | 14 LZ不用自卑到拿印度人找自信吧？这样的烂题答对又如何？迂腐至极，还自以为多牛逼
，其实就是装逼的傻逼。
★ 发自iPhone App: ChineseWeb 7.3.1
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
y****w
发帖数: 3747 | 15 赫赫，灭烙印俺没意见。对同胞好的才是真的好。
【在 N**k 的大作中提到】
: LZ不用自卑到拿印度人找自信吧？这样的烂题答对又如何？迂腐至极，还自以为多牛逼
: ，其实就是装逼的傻逼。
:
: ★ 发自iPhone App: ChineseWeb 7.3.1
|
X*******8
发帖数: 3895 | 16 不懂，在在facebook上班很牛吗？我这个人只认为自己做的牛，别的都可有可无啊。哈
哈哈。。。。
【在 f*****g 的大作中提到】
: 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
: 种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
: 算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
: 要。
: 做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
: 脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
: facebook上班。
|
h******8
发帖数: 278 | 17 哈啊啊，我站这里，烙印欺软怕硬，就该教训教训丫的
【在 y****w 的大作中提到】
: 赫赫，灭烙印俺没意见。对同胞好的才是真的好。
|
j****n
发帖数: 4358 | 18 对烙印这么好，给这么多提示，干脆直接招了吧
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
s***c
发帖数: 50 | 19 这个a3夸夸其谈，完全支持你灭了他!
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
d********f
发帖数: 43471 | 20 你认为这题怎么了？中国人的wf情节还真他妈的天下奇观阿，不但女的舔，男的也有这
个爱好的
【在 N**k 的大作中提到】
: LZ不用自卑到拿印度人找自信吧？这样的烂题答对又如何？迂腐至极，还自以为多牛逼
: ，其实就是装逼的傻逼。
:
: ★ 发自iPhone App: ChineseWeb 7.3.1
|
|
|
t*******d
发帖数: 1186 | 21 这么高深阿，话说我曾经的一份工作，唯一用到的算法就是binary search. |
y***1
发帖数: 450 | 22 agree on 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。
disagree on 算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计算科
学这门学科很重要。但是在广阔的应用领域，算法并不重要
【在 f*****g 的大作中提到】
: 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
: 种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
: 算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
: 要。
: 做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
: 脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
: facebook上班。
|
l*********u
发帖数: 19053 | 23 +1
【在 A**u 的大作中提到】
: 我支持你灭掉烙印
:
: 的。
|
y****w
发帖数: 3747 | 24 分明是在调戏丫。。
【在 j****n 的大作中提到】
: 对烙印这么好，给这么多提示，干脆直接招了吧
:
: 的。
|
g******7
发帖数: 1532 | 25 以后大家有机会面试LY,不知道怎么淘汰,请向LZ学习.
【在 y****w 的大作中提到】
: 分明是在调戏丫。。
|
a*****t
发帖数: 822 | 26 LZ变态，典型的马工猥琐男。当然码工有很多好样的，但 lz绝对不是。 |
vn
发帖数: 6191 | 27 强烈的re
曾经算法学的很多 2年过去一干二净 也不过是熟能生巧的东西 做个web啥的完全木用啊
★ 发自iPhone App: ChineseWeb 7.3.1
【在 f*****g 的大作中提到】
: 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
: 种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
: 算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
: 要。
: 做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
: 脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
: facebook上班。
|
i***h
发帖数: 12655 | 28 LZ本来想说他怎么调戏三哥的
没想到大家的屁股都坐在了苦B找工者的一边
经济基础决定上层意识, 就是这样 |
A*******1
发帖数: 985 | 29 精辟的鉴定
【在 i***h 的大作中提到】
: LZ本来想说他怎么调戏三哥的
: 没想到大家的屁股都坐在了苦B找工者的一边
: 经济基础决定上层意识, 就是这样
|
d*s
发帖数: 699 | 30 这个题怎么解呢？有谁能说说？lz公布答案吧，不要是那种语言处理的lib就行 |
|
|
q***y
发帖数: 24 | 31 就是个图
dfs找个路径就行
【在 d*s 的大作中提到】
: 这个题怎么解呢？有谁能说说？lz公布答案吧，不要是那种语言处理的lib就行
|
d*s
发帖数: 699 | 32 能详细说说吗？
怎么保证match所有的word呢？这点我一直不解
用字典查找可能一语义可能完全是错的，二最后可能会剩下一个不在字典里的东西
【在 q***y 的大作中提到】
: 就是个图
: dfs找个路径就行
|
H****r
发帖数: 2801 | 33 这题目可以理解为这样吗：
句读之不知，何解？
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
s***n
发帖数: 442 | 34 你给老印出的这道题，包括类似的，沾边的，哪怕有一定点沾边的，我工作多年从来没
用上过。。。。
干了4，5年码农了，用的最多的就是if else switch。 稍微写的复杂一点的，就一堆
人跳出来骂娘。
至于算法，对于做产品的公司来说，最好的解决方案就是买或者用开源的，自己写算法
费时费力，还得维护，完全费力不讨好。 |
l*****a
发帖数: 14598 | 35 跟我们说没用，去面试的时候直接跟面世官说好了
也许Q的软工不需要问算法？
【在 s***n 的大作中提到】
: 你给老印出的这道题，包括类似的，沾边的，哪怕有一定点沾边的，我工作多年从来没
: 用上过。。。。
: 干了4，5年码农了，用的最多的就是if else switch。 稍微写的复杂一点的，就一堆
: 人跳出来骂娘。
: 至于算法，对于做产品的公司来说，最好的解决方案就是买或者用开源的，自己写算法
: 费时费力，还得维护，完全费力不讨好。
|
y****w
发帖数: 3747 | 36 不问点"难"的怎么好意思说我们找的是genius
【在 l*****a 的大作中提到】
: 跟我们说没用，去面试的时候直接跟面世官说好了
: 也许Q的软工不需要问算法？
|
s*****n
发帖数: 956 | 37 请教一下，这个题目如果不管语法的话，好像输出不一定是唯一的吧？
比如一个单词的前半截本身是个单词，而后半截和后面的单词又组成一个单词。
appleslight 应该 apples light 还是 apple slight？ （只是个比方，语法不正
确） |
b*********e
发帖数: 26 | 38 楼上骂楼主的人以后被老印欺负了别出来诉苦
看来还是被老印玩的不够爽 |
c********l
发帖数: 3254 | |
l********y
发帖数: 185 | 40 最后招这个烙印了没?
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
|
|
l*****z
发帖数: 3022 | 41 这题还算正常，不过是比较难的，我在google就栽在这个题上了。后来回来好好想了想
，其实就是个递归，每层里for loop to increase the length of the current word
by one, if it is a word goto the next recursion, but prepare to further
increase if the next recursion return false. |
s*****n
发帖数: 956 | 42 这相不相当于
插0个空格 1 种情况
插1个空格 m-1 种情况
插2个空格 (m-1)(m-2) / 2 种情况
.
.
.
插n-1个空格 1
一般来说没插到n-1个空格就返回了。
word
【在 l*****z 的大作中提到】
: 这题还算正常，不过是比较难的，我在google就栽在这个题上了。后来回来好好想了想
: ，其实就是个递归，每层里for loop to increase the length of the current word
: by one, if it is a word goto the next recursion, but prepare to further
: increase if the next recursion return false.
|
g******7
发帖数: 1532 | 43 看来本贴更适合Working版.
【在 A*******1 的大作中提到】
: 精辟的鉴定
|
g*****g
发帖数: 34805 | 44 楼主很厚道，这题不算难，又没要求多高效率，就是考coding，我来写。
void spacing(String prefix, String sen, HashMap dict) {
if(dict.get(sen)!=null) {
print((prefix + " " + sen).trim());
}
if(sen.length() <= 1) return;
for(int i = 1; i < sen.length(); i++) {
String word = sen.substring(0, i);
if(dict.get(word)!=null) {
spaceSentence(prefix + " " + word, sen.substring(i);
}
}
}
void spaceSentence(String sentence, HashMap dict) {
if(sentence == null || sentence.length() ==0) return;
spacing("", sentence, dict);
}
复杂度可以得到递推公式
T(N) = N + T(N-1) + ... +T(1), T(1) = 1。
看似O(N!)
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
l****u
发帖数: 199 | 45 Indian insulted too many Chinese, and we need to fight back. |
I*****8
发帖数: 37 | 46 这道题很多人都说简单，其实好像似乎简单，但。。但 就是递归递归写出问题了，好
吧，面道这题估计比这烙印还悲剧，赶紧想把。 |
q***y
发帖数: 24 | 47 我不是说了是图，找两点间路径即可么？
dfs就可以了
【在 I*****8 的大作中提到】
: 这道题很多人都说简单，其实好像似乎简单，但。。但 就是递归递归写出问题了，好
: 吧，面道这题估计比这烙印还悲剧，赶紧想把。
|
t*****h
发帖数: 137 | 48 #include
#include
#include
using namespace std;
bool find_begin_word(string &sentence, vector &dict, vector &
space_pos, int pos)
{
int new_pos = 0;
bool found = false;
for ( int i = 0; i < dict.size() && !found; ++i )
{
int w_len = dict[i].length();
if ( pos + w_len <= sentence.length() && sentence.substr(pos, w_len) ==
dict[i] )
{
new_pos = pos + w_len;
if ( new_pos == sentence.length() )
{
space_pos.push_back(pos);
return true;
}
else
{
if ( find_begin_word(sentence, dict, space_pos, new_pos) )
{
space_pos.push_back(pos);
return true;
}
}
}
}
return false;
}
int main()
{
vector dict;
dict.push_back("a");
dict.push_back("ab");
dict.push_back("c");
string sentence("abcab");
vector space_pos;
if ( find_begin_word(sentence, dict, space_pos, 0) )
{
for ( int i = 0; i < space_pos.size(); ++i )
cout << space_pos[i] << endl;
}
} |
t*****h
发帖数: 137 | 49 The computation cost is much smaller if we could map a dictionary to a
prefix code and then generate sentence. |
s****x
发帖数: 326 | 50 LZ前面表现的都很好，就是最后一句话不应该说。
你总是心太软。
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
|
|
c****e
发帖数: 26 | 51 人家只不过分享一个面试经验，没想到还有人这么骂自己人。 |
c****e
发帖数: 26 | 52 人家只不过分享一个面试经验，没想到还有人这么骂自己人。 |
s*****3
发帖数: 1673 | 53 国人不团结一下子暴露出来了。。。
LZ只是给阿三出个题而已 |
z*********n
发帖数: 203 | 54 递归比较简单：
string addSpaces(string input, unordered_set &dict) |
d***n
发帖数: 65 | 55 大哥们，这题是google已经淘汰的一道经典题，得出最优解有点难度，但是老印思路完
全没上路，前面还夸夸其谈，这才是lz想要鄙视的。题目本身确实是一道很好的题。合
法句子的要求只是拆分后所有单词都在词典里即可，跟什么自言语言处理毫无关系。 |
d***n
发帖数: 65 | 56 大哥们，这题是google已经淘汰的一道经典题，得出最优解有点难度，但是老印思路完
全没上路，前面还夸夸其谈，这才是lz想要鄙视的。题目本身确实是一道很好的题。合
法句子的要求只是拆分后所有单词都在词典里即可，跟什么自言语言处理毫无关系。 |
m****l
发帖数: 222 | 57 cool
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
j********x
发帖数: 2330 | 58 我不得不说无论一个道理多么明显易懂，总会有人跳出来发一写莫名其妙的奇谈怪论
面试的题目都是稍微tricky但是编写简单的代码，因为这样的方式可以考察基础算法、
代码编写能力；没有人在任何场合告诉candidate，你在面试中写的代码会用到
production code里面。。。
不要在这里卖萌了可以么，全世界面试都是这样，你不喜欢可以自己发明一种么，只要
不让人笑话就行。。。
【在 s***n 的大作中提到】
: 你给老印出的这道题，包括类似的，沾边的，哪怕有一定点沾边的，我工作多年从来没
: 用上过。。。。
: 干了4，5年码农了，用的最多的就是if else switch。 稍微写的复杂一点的，就一堆
: 人跳出来骂娘。
: 至于算法，对于做产品的公司来说，最好的解决方案就是买或者用开源的，自己写算法
: 费时费力，还得维护，完全费力不讨好。
|
q*****n
发帖数: 311 | 59 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
的句子中插入空格，使它变成合法的句子。
他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
你的想法写代码吧，上来就没头没尾写了个
int len = strs.lenth
for (int i=0; i
for (int j=0;j<..;j++) {
}
}
问他这是什么代码，说是java，问他signature，input，output是什么。又开始加这些
string addSpaces(string input) {
...
}
想了会，说得必须有服务器什么得可以调辞典。我说不用，就用一个hashmap或者什么
的在本地就行。
string addSpaces（string input，hashmap dict）
丫又想好久，说发现还是用后缀树比较好，这样可以找最长的匹配。就改成
string addSpaces（Tree dict， string input）
想半天还是没有写出来，这时第二个面试着已敲门，我就礼貌的说了句，you are on
the right track. |
d******3
发帖数: 232 | |
|
|
f*****s
发帖数: 35 | 61 标准答案是什么？
先用字典分离第一个可能的词，后面的用递归？ |
d**e
发帖数: 6098 | 62 如何定义合法的句子？包括语法正确？
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
l*********8
发帖数: 4642 | 63 这个对没有学过自然语言处理的人太难了吧？ 我觉得能做到每个单词都在词典里面就
可以了。
【在 d**e 的大作中提到】
: 如何定义合法的句子？包括语法正确？
:
: 的。
|
l*********8
发帖数: 4642 | 64 好像可以用dp, O(k*k*n), k是单词最大长度。
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
s*****n
发帖数: 5488 | 65 尼玛这题是靠编程还是算法啊。什么叫做合法的句子。从分词到语法正确到语义？
我觉得烙印蒙掉很正常，及时他写了很多程序。
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
h****7
发帖数: 2350 | 66 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
因为他们不知道天有多高, 地有多厚. |
A**u
发帖数: 2458 | 67 我支持你灭掉烙印
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
t*****o
发帖数: 4919 | 68 狠同意！
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
y****w
发帖数: 3747 | 69 还是考基础算法比较好，list/bi-tree,是个人就学过，行了． 有没有sense很快就知
道了．不想敷衍的自己琢磨个新题． 有些复杂的玩意儿，其实也考不了多深刻，比如
人家看严伟民的书长大的就不知道你们最喜欢的几个玩意儿－－那些难么？
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
g******7
发帖数: 1532 | |
|
|
f*****g
发帖数: 99 | 71 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
要。
做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
facebook上班。
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
N**k
发帖数: 3584 | 72 LZ不用自卑到拿印度人找自信吧？这样的烂题答对又如何？迂腐至极，还自以为多牛逼
，其实就是装逼的傻逼。
★ 发自iPhone App: ChineseWeb 7.3.1
【在 h****7 的大作中提到】
: 傻 X 程序员就喜欢摆弄算法这些东西来显摆, 跟孔乙己的茴香豆有四种写法差不多.
: 真让他们去研究算法么, 一个个都傻 X 了, 脑子都不够使了, 理论研究太枯燥了...
: 喜欢装 B 玩算法的, 基本都是一瓶水不满半瓶水晃荡的主.
: 因为他们不知道天有多高, 地有多厚.
|
y****w
发帖数: 3747 | 73 赫赫，灭烙印俺没意见。对同胞好的才是真的好。
【在 N**k 的大作中提到】
: LZ不用自卑到拿印度人找自信吧？这样的烂题答对又如何？迂腐至极，还自以为多牛逼
: ，其实就是装逼的傻逼。
:
: ★ 发自iPhone App: ChineseWeb 7.3.1
|
X*******8
发帖数: 3895 | 74 不懂，在在facebook上班很牛吗？我这个人只认为自己做的牛，别的都可有可无啊。哈
哈哈。。。。
【在 f*****g 的大作中提到】
: 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
: 种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
: 算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
: 要。
: 做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
: 脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
: facebook上班。
|
h******8
发帖数: 278 | 75 哈啊啊，我站这里，烙印欺软怕硬，就该教训教训丫的
【在 y****w 的大作中提到】
: 赫赫，灭烙印俺没意见。对同胞好的才是真的好。
|
j****n
发帖数: 4358 | 76 对烙印这么好，给这么多提示，干脆直接招了吧
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
s***c
发帖数: 50 | 77 这个a3夸夸其谈，完全支持你灭了他!
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
d********f
发帖数: 43471 | 78 你认为这题怎么了？中国人的wf情节还真他妈的天下奇观阿，不但女的舔，男的也有这
个爱好的
【在 N**k 的大作中提到】
: LZ不用自卑到拿印度人找自信吧？这样的烂题答对又如何？迂腐至极，还自以为多牛逼
: ，其实就是装逼的傻逼。
:
: ★ 发自iPhone App: ChineseWeb 7.3.1
|
t*******d
发帖数: 1186 | 79 这么高深阿，话说我曾经的一份工作，唯一用到的算法就是binary search. |
y***1
发帖数: 450 | 80 agree on 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。
disagree on 算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计算科
学这门学科很重要。但是在广阔的应用领域，算法并不重要
【在 f*****g 的大作中提到】
: 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
: 种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
: 算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
: 要。
: 做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
: 脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
: facebook上班。
|
|
|
l*********u
发帖数: 19053 | 81 +1
【在 A**u 的大作中提到】
: 我支持你灭掉烙印
:
: 的。
|
y****w
发帖数: 3747 | 82 分明是在调戏丫。。
【在 j****n 的大作中提到】
: 对烙印这么好，给这么多提示，干脆直接招了吧
:
: 的。
|
g******7
发帖数: 1532 | 83 以后大家有机会面试LY,不知道怎么淘汰,请向LZ学习.
【在 y****w 的大作中提到】
: 分明是在调戏丫。。
|
a*****t
发帖数: 822 | 84 LZ变态，典型的马工猥琐男。当然码工有很多好样的，但 lz绝对不是。 |
vn
发帖数: 6191 | 85 强烈的re
曾经算法学的很多 2年过去一干二净 也不过是熟能生巧的东西 做个web啥的完全木用啊
★ 发自iPhone App: ChineseWeb 7.3.1
【在 f*****g 的大作中提到】
: 用一些tricky questions来测试一个人的能力，的确没有什么可以称道的。遗憾的是这
: 种做法还广为流行。算法重要吗，重要，在某些领域是很重要。说他重要指的是对于计
: 算科学这门学科很重要。但是在广阔的应用领域，算法并不重要，或正变得越来越不重
: 要。
: 做电脑的人都有自大的倾向，自大的旁边站着目光狭隘。所以就不难理解为什么众多电
: 脑高手们都在给一个20多岁的毛头小伙干活，同时还会漫不经心地透露一下，哥在
: facebook上班。
|
i***h
发帖数: 12655 | 86 LZ本来想说他怎么调戏三哥的
没想到大家的屁股都坐在了苦B找工者的一边
经济基础决定上层意识, 就是这样 |
A*******1
发帖数: 985 | 87 精辟的鉴定
【在 i***h 的大作中提到】
: LZ本来想说他怎么调戏三哥的
: 没想到大家的屁股都坐在了苦B找工者的一边
: 经济基础决定上层意识, 就是这样
|
d*s
发帖数: 699 | 88 这个题怎么解呢？有谁能说说？lz公布答案吧，不要是那种语言处理的lib就行 |
q***y
发帖数: 24 | 89 就是个图
dfs找个路径就行
【在 d*s 的大作中提到】
: 这个题怎么解呢？有谁能说说？lz公布答案吧，不要是那种语言处理的lib就行
|
d*s
发帖数: 699 | 90 能详细说说吗？
怎么保证match所有的word呢？这点我一直不解
用字典查找可能一语义可能完全是错的，二最后可能会剩下一个不在字典里的东西
【在 q***y 的大作中提到】
: 就是个图
: dfs找个路径就行
|
|
|
H****r
发帖数: 2801 | 91 这题目可以理解为这样吗：
句读之不知，何解？
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
s***n
发帖数: 442 | 92 你给老印出的这道题，包括类似的，沾边的，哪怕有一定点沾边的，我工作多年从来没
用上过。。。。
干了4，5年码农了，用的最多的就是if else switch。 稍微写的复杂一点的，就一堆
人跳出来骂娘。
至于算法，对于做产品的公司来说，最好的解决方案就是买或者用开源的，自己写算法
费时费力，还得维护，完全费力不讨好。 |
l*****a
发帖数: 14598 | 93 跟我们说没用，去面试的时候直接跟面世官说好了
也许Q的软工不需要问算法？
【在 s***n 的大作中提到】
: 你给老印出的这道题，包括类似的，沾边的，哪怕有一定点沾边的，我工作多年从来没
: 用上过。。。。
: 干了4，5年码农了，用的最多的就是if else switch。 稍微写的复杂一点的，就一堆
: 人跳出来骂娘。
: 至于算法，对于做产品的公司来说，最好的解决方案就是买或者用开源的，自己写算法
: 费时费力，还得维护，完全费力不讨好。
|
y****w
发帖数: 3747 | 94 不问点"难"的怎么好意思说我们找的是genius
【在 l*****a 的大作中提到】
: 跟我们说没用，去面试的时候直接跟面世官说好了
: 也许Q的软工不需要问算法？
|
s*****n
发帖数: 956 | 95 请教一下，这个题目如果不管语法的话，好像输出不一定是唯一的吧？
比如一个单词的前半截本身是个单词，而后半截和后面的单词又组成一个单词。
appleslight 应该 apples light 还是 apple slight？ （只是个比方，语法不正
确） |
b*********e
发帖数: 26 | 96 楼上骂楼主的人以后被老印欺负了别出来诉苦
看来还是被老印玩的不够爽 |
c********l
发帖数: 3254 | |
l********y
发帖数: 185 | 98 最后招这个烙印了没?
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
l*****z
发帖数: 3022 | 99 这题还算正常，不过是比较难的，我在google就栽在这个题上了。后来回来好好想了想
，其实就是个递归，每层里for loop to increase the length of the current word
by one, if it is a word goto the next recursion, but prepare to further
increase if the next recursion return false. |
s*****n
发帖数: 956 | 100 这相不相当于
插0个空格 1 种情况
插1个空格 m-1 种情况
插2个空格 (m-1)(m-2) / 2 种情况
.
.
.
插n-1个空格 1
一般来说没插到n-1个空格就返回了。
word
【在 l*****z 的大作中提到】
: 这题还算正常，不过是比较难的，我在google就栽在这个题上了。后来回来好好想了想
: ，其实就是个递归，每层里for loop to increase the length of the current word
: by one, if it is a word goto the next recursion, but prepare to further
: increase if the next recursion return false.
|
|
|
g******7
发帖数: 1532 | 101 看来本贴更适合Working版.
【在 A*******1 的大作中提到】
: 精辟的鉴定
|
g*****g
发帖数: 34805 | 102 楼主很厚道，这题不算难，又没要求多高效率，就是考coding，我来写。
void spacing(String prefix, String sen, HashMap dict) {
if(dict.get(sen)!=null) {
print((prefix + " " + sen).trim());
}
if(sen.length() <= 1) return;
for(int i = 1; i < sen.length(); i++) {
String word = sen.substring(0, i);
if(dict.get(word)!=null) {
spaceSentence(prefix + " " + word, sen.substring(i);
}
}
}
void spaceSentence(String sentence, HashMap dict) {
if(sentence == null || sentence.length() ==0) return;
spacing("", sentence, dict);
}
复杂度可以得到递推公式
T(N) = N + T(N-1) + ... +T(1), T(1) = 1。
看似O(N!)
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
l****u
发帖数: 199 | 103 Indian insulted too many Chinese, and we need to fight back. |
I*****8
发帖数: 37 | 104 这道题很多人都说简单，其实好像似乎简单，但。。但 就是递归递归写出问题了，好
吧，面道这题估计比这烙印还悲剧，赶紧想把。 |
q***y
发帖数: 24 | 105 我不是说了是图，找两点间路径即可么？
dfs就可以了
【在 I*****8 的大作中提到】
: 这道题很多人都说简单，其实好像似乎简单，但。。但 就是递归递归写出问题了，好
: 吧，面道这题估计比这烙印还悲剧，赶紧想把。
|
t*****h
发帖数: 137 | 106 #include
#include
#include
using namespace std;
bool find_begin_word(string &sentence, vector &dict, vector &
space_pos, int pos)
{
int new_pos = 0;
bool found = false;
for ( int i = 0; i < dict.size() && !found; ++i )
{
int w_len = dict[i].length();
if ( pos + w_len <= sentence.length() && sentence.substr(pos, w_len) ==
dict[i] )
{
new_pos = pos + w_len;
if ( new_pos == sentence.length() )
{
space_pos.push_back(pos);
return true;
}
else
{
if ( find_begin_word(sentence, dict, space_pos, new_pos) )
{
space_pos.push_back(pos);
return true;
}
}
}
}
return false;
}
int main()
{
vector dict;
dict.push_back("a");
dict.push_back("ab");
dict.push_back("c");
string sentence("abcab");
vector space_pos;
if ( find_begin_word(sentence, dict, space_pos, 0) )
{
for ( int i = 0; i < space_pos.size(); ++i )
cout << space_pos[i] << endl;
}
} |
t*****h
发帖数: 137 | 107 The computation cost is much smaller if we could map a dictionary to a
prefix code and then generate sentence. |
s****x
发帖数: 326 | 108 LZ前面表现的都很好，就是最后一句话不应该说。
你总是心太软。
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
c****e
发帖数: 26 | 109 人家只不过分享一个面试经验，没想到还有人这么骂自己人。 |
c****e
发帖数: 26 | 110 人家只不过分享一个面试经验，没想到还有人这么骂自己人。 |
|
|
s*****3
发帖数: 1673 | 111 国人不团结一下子暴露出来了。。。
LZ只是给阿三出个题而已 |
z*********n
发帖数: 203 | 112 递归比较简单：
string addSpaces(string input, unordered_set &dict) |
d***n
发帖数: 65 | 113 大哥们，这题是google已经淘汰的一道经典题，得出最优解有点难度，但是老印思路完
全没上路，前面还夸夸其谈，这才是lz想要鄙视的。题目本身确实是一道很好的题。合
法句子的要求只是拆分后所有单词都在词典里即可，跟什么自言语言处理毫无关系。 |
d***n
发帖数: 65 | 114 大哥们，这题是google已经淘汰的一道经典题，得出最优解有点难度，但是老印思路完
全没上路，前面还夸夸其谈，这才是lz想要鄙视的。题目本身确实是一道很好的题。合
法句子的要求只是拆分后所有单词都在词典里即可，跟什么自言语言处理毫无关系。 |
m****l
发帖数: 222 | 115 cool
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
j********x
发帖数: 2330 | 116 我不得不说无论一个道理多么明显易懂，总会有人跳出来发一写莫名其妙的奇谈怪论
面试的题目都是稍微tricky但是编写简单的代码，因为这样的方式可以考察基础算法、
代码编写能力；没有人在任何场合告诉candidate，你在面试中写的代码会用到
production code里面。。。
不要在这里卖萌了可以么，全世界面试都是这样，你不喜欢可以自己发明一种么，只要
不让人笑话就行。。。
【在 s***n 的大作中提到】
: 你给老印出的这道题，包括类似的，沾边的，哪怕有一定点沾边的，我工作多年从来没
: 用上过。。。。
: 干了4，5年码农了，用的最多的就是if else switch。 稍微写的复杂一点的，就一堆
: 人跳出来骂娘。
: 至于算法，对于做产品的公司来说，最好的解决方案就是买或者用开源的，自己写算法
: 费时费力，还得维护，完全费力不讨好。
|
c********r
发帖数: 286 | 117 i++;
【在 l*********u 的大作中提到】
: +1
|
h****a
发帖数: 23 | 118 这题是用经典算法啊，一点都不tricky，递归/DP基本功吧。
我被问过painter高级版，那才叫变态。 |
n***e
发帖数: 723 | 119 这个能求一下标准答案吗？
我只能粗浅的把dictionary排成树，然后recursive查词。。。
但是如果插入空格错误造成后面单词无法识别的我就不知道怎么办。。。
比如：
converterase
可以断成
convert erase
但如果断成
converter ase 就不行了。
这个可以求个思路么？ |
t*********h
发帖数: 941 | 120 good one. dp or recursion+memoization
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
|
|
s********l
发帖数: 998 | 121 你是说 用back tracking?
word
【在 l*****z 的大作中提到】
: 这题还算正常，不过是比较难的，我在google就栽在这个题上了。后来回来好好想了想
: ，其实就是个递归，每层里for loop to increase the length of the current word
: by one, if it is a word goto the next recursion, but prepare to further
: increase if the next recursion return false.
|
h****n
发帖数: 1093 | 122 我只会用DFS暴力找出来
我也不赞成过分追求算法多么复杂。，工作中那些算法有几个能用得到
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
x****o
发帖数: 29677 | |
z**l
发帖数: 113 | |
v*******e
发帖数: 326 | 125 seems like many chinese doesn't know how to answer |
h*******0
发帖数: 270 | 126 这题出得不简单。。 但是大家也没必要对楼主冷嘲热讽。 楼主灭烙印难道不是在为同
胞着想吗？ 现在coding这个行当，烙印可比中国人吃香多了。 大家想过什么原因吗？
就是中国人自己不团结，窝里斗。 所以，不要通过指责楼主来突出自己的优越感，这
没意思啊。。 |
m*****t
发帖数: 3477 | 127 bug你还挺认真。
我看到阿三的简历直接pass，面试机会都不给。
【在 g*****g 的大作中提到】
: 楼主很厚道，这题不算难，又没要求多高效率，就是考coding，我来写。
: void spacing(String prefix, String sen, HashMap dict) {
: if(dict.get(sen)!=null) {
: print((prefix + " " + sen).trim());
: }
: if(sen.length() <= 1) return;
:
: for(int i = 1; i < sen.length(); i++) {
:
: String word = sen.substring(0, i);
|
S******y
发帖数: 1330 | 128 LOL, do not look down on us magong
【在 H****r 的大作中提到】
: 这题目可以理解为这样吗：
: 句读之不知，何解？
:
: 的。
|
c********e
发帖数: 1209 | 129 支持楼主一下，这个要看职位的要求的。如果是level合适的的程序员这个应该能写出
来，否则那些有点技术的活谁来干啊。打着旗号是CS编程，也要有点料啊，否则我们EE
也可以上了哦，
的。
【在 q*****n 的大作中提到】
: 简历不象写过多少代码，一见面自我介绍后让他简要介绍，这厮开始夸夸其谈，说其做
: 的东西如何如何牛逼，三四个产品都已经放到product，并准备了打印好得ppt图片给我
: 看，听起来没完没了，很细节，我不得不礼貌得差了一句问你写得这些代码，丫自信满
: 满说是，就问了一个递归的编程题，类似于spellchecker，就是用词典在一个没有空格
: 的句子中插入空格，使它变成合法的句子。
: 他一开始先说用贪婪法找到最长的匹配，然后停止接着找，经我提示发觉这法不对。
: 又说用后缀树，我提示说词典以给你，不用超心怎么实现，可以是hashset／map什么的。
: 他又开始说统计词典里的词的长度，找到平均长度，然后用这来决定什么时候停止。我
: 说如果词典的api不受你控制，或者又加了新词，怎么办？他说数据必须得有办法获得
: 。后来又回到贪心法，找最长的在词典中的匹配词。怎么提示实在没辙了，后来就说用
|
b*w
发帖数: 14917 | 130 看了这个帖子，三观彻底混乱了：到底面试时夸夸其谈好，还是谦虚谨慎好？ |
