r*t
2 楼
好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间
z*s
3 楼
觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
吗？为了自己把一个生命带到这个世界上来，到底应不应该？
到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
吗？为了自己把一个生命带到这个世界上来，到底应不应该？
m*i
4 楼
corned beef
水煮
【在 f******r 的大作中提到】
: 单位食堂吃得比较好吃
: 买了,可是不知道怎么做
: 是不是考阿?多谢
水煮
【在 f******r 的大作中提到】
: 单位食堂吃得比较好吃
: 买了,可是不知道怎么做
: 是不是考阿?多谢
n*t
5 楼
好难，一个都不会，呵呵
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
n*y
6 楼
点儿背不要赖社会
EA
7 楼
包装上不是有写吗？你自己读读。
w*o
8 楼
好难啊。。。。。。。
i*8
9 楼
this sounds like depression...
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
c*w
10 楼
二次函数先算出对称轴,对左右两边的分别计算好之后merge?
R*i
11 楼
还是等你准备好了再要孩子吧。
c*e
12 楼
先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
的距离决定。
【在 c******w 的大作中提到】
: 二次函数先算出对称轴,对左右两边的分别计算好之后merge?
的距离决定。
【在 c******w 的大作中提到】
: 二次函数先算出对称轴,对左右两边的分别计算好之后merge?
h*e
13 楼
30年河东，30年河西。
你命运不好或者你觉得自己命不会，没准到你孩子这儿就变好了。
所以你如果有30了，由河东变河西了，是可以考虑要孩子了。
有了孩子后，教他乐观点，别让你的负面情绪影响孩子。
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
你命运不好或者你觉得自己命不会，没准到你孩子这儿就变好了。
所以你如果有30了，由河东变河西了，是可以考虑要孩子了。
有了孩子后，教他乐观点，别让你的负面情绪影响孩子。
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
j*u
14 楼
看起来挺难的。。
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing?
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing?
z*s
15 楼
孩子长大了点儿背可以赖父母吗？
【在 n****y 的大作中提到】
: 点儿背不要赖社会
【在 n****y 的大作中提到】
: 点儿背不要赖社会
j*x
16 楼
单词的那个没有任何思路啊。。。
x*t
17 楼
我觉得想开了人这一辈子就像走一段旅程，不到最后都不知道之间会发生什么，一帆风
顺固然好，到最后回头一看，也许经历的坎坷倒让这一辈子更丰富和宝贵。所以别在意
这些小事。
如果你总这样想就太悲观了，也许有点Depression？这样的话还是调整好再要孩子，家
长的情绪和思维习惯以及人生观会直接引导孩子的成长方向。你每天心里想什么，嘴里
说什么，对孩子说什么，他就会成长成那样的人。
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
顺固然好，到最后回头一看，也许经历的坎坷倒让这一辈子更丰富和宝贵。所以别在意
这些小事。
如果你总这样想就太悲观了，也许有点Depression？这样的话还是调整好再要孩子，家
长的情绪和思维习惯以及人生观会直接引导孩子的成长方向。你每天心里想什么，嘴里
说什么，对孩子说什么，他就会成长成那样的人。
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
j*x
18 楼
定义一个函数collapse(word) {
return sort(unique(word)); //返回经过排序的独一字符
}
处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
的单词长度的最大值。然后查询吧
对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
度O(n)
return sort(unique(word)); //返回经过排序的独一字符
}
处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
的单词长度的最大值。然后查询吧
对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
度O(n)
z*c
19 楼
想太多这日子就没法过了。
c*w
20 楼
二次函数的值先算还是后算没区别.不过你这样要多做几次减法
【在 c*****e 的大作中提到】
: 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
: 的距离决定。
【在 c*****e 的大作中提到】
: 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
: 的距离决定。
c*e
21 楼
养孩子是个很大的责任, 还是准备好了以后再要好一些.
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
炼。
【在 z****s 的大作中提到】
: 觉得生活不容易，有太多痛苦和挫折。小时候被淘气的男生欺负，工作了被领导欺负。
: 到美国读书被老板剥削，被实验室师姐欺负。生离死别各种的痛苦时不时就在生活中发
: 生。经常觉得这一切都只是为了生下来了就得要活下去，应了那句话：活着是一种修炼。
: 我有时候会想，如果当初我没有被生下来，这些痛苦的过程就不会发生，为什么我就被
: 生下来了呢？我父母经常在说我应该有小孩了，可是他/她真的就想要我把他/她生下来
: 吗？为了自己把一个生命带到这个世界上来，到底应不应该？
h*n
22 楼
do u assume char set is "a" - "z"? why it is 24 instead of 26?
if the char set is unicode, this solution seems incur high cost, right?
aslo, do u know any application of this problem?
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
if the char set is unicode, this solution seems incur high cost, right?
aslo, do u know any application of this problem?
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
R*9
23 楼
我以前也是这样想的，真的! 所以拖到很大龄才要小孩，还是在老公以离婚相逼的情况
下要的孩子。
可是，自从有了儿子，我整个的世界观都变了，觉得生命是多么美好. 以前觉得多活一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
我非常地感谢我的老公的坚持，孩子真是上帝的礼物！
下要的孩子。
可是，自从有了儿子，我整个的世界观都变了，觉得生命是多么美好. 以前觉得多活一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
我非常地感谢我的老公的坚持，孩子真是上帝的礼物！
j*x
24 楼
26搞错了，假设'a'-'z'
unicode的不懂
不管怎么说第一步的collapse一定是有用的
of 26?
high cost, right?
【在 h***n 的大作中提到】
: do u assume char set is "a" - "z"? why it is 24 instead of 26?
: if the char set is unicode, this solution seems incur high cost, right?
: aslo, do u know any application of this problem?
unicode的不懂
不管怎么说第一步的collapse一定是有用的
of 26?
high cost, right?
【在 h***n 的大作中提到】
: do u assume char set is "a" - "z"? why it is 24 instead of 26?
: if the char set is unicode, this solution seems incur high cost, right?
: aslo, do u know any application of this problem?
k*n
25 楼
that's what you feel, can't gaurantee what your kid will feel
一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
【在 R****9 的大作中提到】
: 我以前也是这样想的，真的! 所以拖到很大龄才要小孩，还是在老公以离婚相逼的情况
: 下要的孩子。
: 可是，自从有了儿子，我整个的世界观都变了，觉得生命是多么美好. 以前觉得多活一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
: 我非常地感谢我的老公的坚持，孩子真是上帝的礼物！
一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
【在 R****9 的大作中提到】
: 我以前也是这样想的，真的! 所以拖到很大龄才要小孩，还是在老公以离婚相逼的情况
: 下要的孩子。
: 可是，自从有了儿子，我整个的世界观都变了，觉得生命是多么美好. 以前觉得多活一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
: 我非常地感谢我的老公的坚持，孩子真是上帝的礼物！
h*n
26 楼
it seems I understand your solution correctly
the only concern is that, when the character set is large (say unicode which
has chars more than 109,000), we can no longer take advantage of trie, but
instead, we just have to compare them directly, which lead to O(n^2) solutio
n
【在 j********x 的大作中提到】
: 26搞错了，假设'a'-'z'
: unicode的不懂
: 不管怎么说第一步的collapse一定是有用的
:
: of 26?
: high cost, right?
the only concern is that, when the character set is large (say unicode which
has chars more than 109,000), we can no longer take advantage of trie, but
instead, we just have to compare them directly, which lead to O(n^2) solutio
n
【在 j********x 的大作中提到】
: 26搞错了，假设'a'-'z'
: unicode的不懂
: 不管怎么说第一步的collapse一定是有用的
:
: of 26?
: high cost, right?
p*l
27 楼
LZ你需要专业的心理咨询
f*g
28 楼
看了上面的回复，受到启发。
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧
D*R
29 楼
小时候也被欺负，但是有朋友站出来撑腰，让我在3岁多的年纪就体会到了友谊的可贵；
上学了也遇到各种各样的老师，优点缺点交织，让我知道了人可以这么复杂，心胸可以
这么宽广；
上班了被领导批评过，被同事责备过，让我学会了做事先为他人考虑，把自己的工作放
到整个项目的高度去考虑，更好的合作，更好地生存；
刚出人世的小bb以为他就是世界的中心，只有不断碰壁，才能把自己塑成合适的社会人
，同时也塑造着身边的社会。
上学了也遇到各种各样的老师，优点缺点交织，让我知道了人可以这么复杂，心胸可以
这么宽广；
上班了被领导批评过，被同事责备过，让我学会了做事先为他人考虑，把自己的工作放
到整个项目的高度去考虑，更好的合作，更好地生存；
刚出人世的小bb以为他就是世界的中心，只有不断碰壁，才能把自己塑成合适的社会人
，同时也塑造着身边的社会。
c*e
30 楼
No need to compare the function value.
【在 c******w 的大作中提到】
: 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
【在 c******w 的大作中提到】
: 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
B*W
31 楼
Nothing is more precious than the gift of life.
As a matter of fact, most young kids are very happy as long as they receive
attention and love besides basic needs. If they are not happy, it is not
because they don't get the best food, the best education, whatsoever; it is
because they don't feel the love from their parents.
!!
【在 k***n 的大作中提到】
: that's what you feel, can't gaurantee what your kid will feel
:
: 一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
As a matter of fact, most young kids are very happy as long as they receive
attention and love besides basic needs. If they are not happy, it is not
because they don't get the best food, the best education, whatsoever; it is
because they don't feel the love from their parents.
!!
【在 k***n 的大作中提到】
: that's what you feel, can't gaurantee what your kid will feel
:
: 一天少活一天没有什么区别，现在觉得每天都要好好地活着。It is just so great!!!
f*g
32 楼
写了个测试下，用了一个常用字典
结果是：
foresightedness
blackjack
有点意思，就是不知道这个变态的题目有什么实际意义
结果是：
foresightedness
blackjack
有点意思，就是不知道这个变态的题目有什么实际意义
k*n
33 楼
you can only have some influence when the kid is young, once he's grown up,
the parents rarely have any control what the kid will experience and feel
receive
is
【在 B**W 的大作中提到】
: Nothing is more precious than the gift of life.
: As a matter of fact, most young kids are very happy as long as they receive
: attention and love besides basic needs. If they are not happy, it is not
: because they don't get the best food, the best education, whatsoever; it is
: because they don't feel the love from their parents.
:
: !!
the parents rarely have any control what the kid will experience and feel
receive
is
【在 B**W 的大作中提到】
: Nothing is more precious than the gift of life.
: As a matter of fact, most young kids are very happy as long as they receive
: attention and love besides basic needs. If they are not happy, it is not
: because they don't get the best food, the best education, whatsoever; it is
: because they don't feel the love from their parents.
:
: !!
l*a
34 楼
my solution:
1.create hash for each word
2.sort the dictionary by word length.
assume the dictionary become
a[0],a[1]......
find the largest k so that hash(a[0])&hash(a[k])==0,
get max=len(a[0])*len(a[k])
find max i in [2,k-1] so that hash(a[1])&hash(a[i])==0,
compare max and len(a[1])*len(a[i])
next step find max j in [3,i-1]....
【在 f***g 的大作中提到】
: 看了上面的回复，受到启发。
: 也说一个想法：
: Assumption: ASCII
: 对于每一个单词，利用bitset原理
: 用一个int就可以表示出其字母出现的模式。
: 假设用最低位表示z，最高的第7位表示a
: 预处理
: 1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
: 2.在每个数组中的保存符合当前模式的最长的单词。
: 找最大：
1.create hash for each word
2.sort the dictionary by word length.
assume the dictionary become
a[0],a[1]......
find the largest k so that hash(a[0])&hash(a[k])==0,
get max=len(a[0])*len(a[k])
find max i in [2,k-1] so that hash(a[1])&hash(a[i])==0,
compare max and len(a[1])*len(a[i])
next step find max j in [3,i-1]....
【在 f***g 的大作中提到】
: 看了上面的回复，受到启发。
: 也说一个想法：
: Assumption: ASCII
: 对于每一个单词，利用bitset原理
: 用一个int就可以表示出其字母出现的模式。
: 假设用最低位表示z，最高的第7位表示a
: 预处理
: 1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
: 2.在每个数组中的保存符合当前模式的最长的单词。
: 找最大：
y*a
35 楼
"准备好"的标准是什么啊？等大家准备好了，可能青春就一晃而过了。
是有不少人后悔当初生了孩子，但是有更多的人后悔没有生孩子或者早生孩子。
是有不少人后悔当初生了孩子，但是有更多的人后悔没有生孩子或者早生孩子。
i*s
36 楼
B*W
37 楼
That's exactly why we need families. Whenever you think of your parents,
your children, who trust you, support you, and share their love with you,
you will feel strong no matter how hard times are. Of course, if your
parents are not like what you wished, that is a different story.
Plus, grow up, please. Don't behave like a baby. Your parents have no
obligation to take care of you all the time, even though they always love
you and support you. Take on your own responsibility.
,
【在 k***n 的大作中提到】
: you can only have some influence when the kid is young, once he's grown up,
: the parents rarely have any control what the kid will experience and feel
:
: receive
: is
your children, who trust you, support you, and share their love with you,
you will feel strong no matter how hard times are. Of course, if your
parents are not like what you wished, that is a different story.
Plus, grow up, please. Don't behave like a baby. Your parents have no
obligation to take care of you all the time, even though they always love
you and support you. Take on your own responsibility.
,
【在 k***n 的大作中提到】
: you can only have some influence when the kid is young, once he's grown up,
: the parents rarely have any control what the kid will experience and feel
:
: receive
: is
y*2
38 楼
同感……
k*n
39 楼
you're really funny, the parents don't have obligation for their kids when
they grow up that's true, but how can you make sure that it won't be better
for them if they were not born in the first place? you give birth to the
kids out of selfish reasons, not from the children's angle.
【在 B**W 的大作中提到】
: That's exactly why we need families. Whenever you think of your parents,
: your children, who trust you, support you, and share their love with you,
: you will feel strong no matter how hard times are. Of course, if your
: parents are not like what you wished, that is a different story.
: Plus, grow up, please. Don't behave like a baby. Your parents have no
: obligation to take care of you all the time, even though they always love
: you and support you. Take on your own responsibility.
:
: ,
they grow up that's true, but how can you make sure that it won't be better
for them if they were not born in the first place? you give birth to the
kids out of selfish reasons, not from the children's angle.
【在 B**W 的大作中提到】
: That's exactly why we need families. Whenever you think of your parents,
: your children, who trust you, support you, and share their love with you,
: you will feel strong no matter how hard times are. Of course, if your
: parents are not like what you wished, that is a different story.
: Plus, grow up, please. Don't behave like a baby. Your parents have no
: obligation to take care of you all the time, even though they always love
: you and support you. Take on your own responsibility.
:
: ,
g*s
40 楼
What's this? Given class bst, design a class iterator to do the following?
for (bst::in_order_iterator it = bst.root(); it != bst.end(); ++ it) {
it->print();
}
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
B*W
41 楼
I have no problem if you hate your parents who "gave" you a miserable life,
but I would never think that way.
Plus, it is kinda funny to say parents are more selfish than those who don't
want to sacrifice their money, time, energy, and career to raise kids, in
the name of giving their baby better life. Their "babies" don't even have
life, what does better life mean then?
Last words.
better
【在 k***n 的大作中提到】
: you're really funny, the parents don't have obligation for their kids when
: they grow up that's true, but how can you make sure that it won't be better
: for them if they were not born in the first place? you give birth to the
: kids out of selfish reasons, not from the children's angle.
but I would never think that way.
Plus, it is kinda funny to say parents are more selfish than those who don't
want to sacrifice their money, time, energy, and career to raise kids, in
the name of giving their baby better life. Their "babies" don't even have
life, what does better life mean then?
Last words.
better
【在 k***n 的大作中提到】
: you're really funny, the parents don't have obligation for their kids when
: they grow up that's true, but how can you make sure that it won't be better
: for them if they were not born in the first place? you give birth to the
: kids out of selfish reasons, not from the children's angle.
g*s
42 楼
If m words, length of words are L_1, L_2,..., L_m. O(m^2+sum(L_i))?
Is O(mlg(m)) possible?
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
k*n
43 楼
it's not just me, do you know how many people suffer from depression? if you
're not aware of the sufferings of the wide population, you're simply
ignorant. you brought a life to the world and refuse to be responsible for
the consequences, what can i say? you're just an irresponsible person.
,
't
【在 B**W 的大作中提到】
: I have no problem if you hate your parents who "gave" you a miserable life,
: but I would never think that way.
: Plus, it is kinda funny to say parents are more selfish than those who don't
: want to sacrifice their money, time, energy, and career to raise kids, in
: the name of giving their baby better life. Their "babies" don't even have
: life, what does better life mean then?
: Last words.
:
: better
're not aware of the sufferings of the wide population, you're simply
ignorant. you brought a life to the world and refuse to be responsible for
the consequences, what can i say? you're just an irresponsible person.
,
't
【在 B**W 的大作中提到】
: I have no problem if you hate your parents who "gave" you a miserable life,
: but I would never think that way.
: Plus, it is kinda funny to say parents are more selfish than those who don't
: want to sacrifice their money, time, energy, and career to raise kids, in
: the name of giving their baby better life. Their "babies" don't even have
: life, what does better life mean then?
: Last words.
:
: better
r*t
44 楼
好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间
phone interview
给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
排好序的
onsite
1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
3. 写一个二叉树遍历的iterator
4. design一个middle layer，在客户端跟搜索服务器之间
D*a
45 楼
那你努力做富一代，你孩子不就不会怪你了。
n*t
46 楼
好难，一个都不会，呵呵
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
w*o
47 楼
好难啊。。。。。。。
c*w
48 楼
二次函数先算出对称轴,对左右两边的分别计算好之后merge?
c*e
49 楼
先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
的距离决定。
【在 c******w 的大作中提到】
: 二次函数先算出对称轴,对左右两边的分别计算好之后merge?
的距离决定。
【在 c******w 的大作中提到】
: 二次函数先算出对称轴,对左右两边的分别计算好之后merge?
j*u
50 楼
看起来挺难的。。
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing?
单个文件里没有conflict吧。2 way merge sort?
只想到build一个char->word的inverted index，复杂度可以减到O(n*AVG(#words_
share_no_letter)), worse case还是O(n^2)
有什么更好的方法？
还好这个不难，如果用C#做traversal的时候yield return就行了
middle tier要做什么：requirement是啥？e.g. load balancing? logging?
preprocessing?
j*x
51 楼
单词的那个没有任何思路啊。。。
j*x
52 楼
定义一个函数collapse(word) {
return sort(unique(word)); //返回经过排序的独一字符
}
处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
的单词长度的最大值。然后查询吧
对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
度O(n)
return sort(unique(word)); //返回经过排序的独一字符
}
处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
的单词长度的最大值。然后查询吧
对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
度O(n)
c*w
53 楼
二次函数的值先算还是后算没区别.不过你这样要多做几次减法
【在 c*****e 的大作中提到】
: 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
: 的距离决定。
【在 c*****e 的大作中提到】
: 先找到对称轴（或者最小的包含区间）,然后从两个不同的方向扩展，顺序由到对称轴
: 的距离决定。
h*n
54 楼
do u assume char set is "a" - "z"? why it is 24 instead of 26?
if the char set is unicode, this solution seems incur high cost, right?
aslo, do u know any application of this problem?
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
if the char set is unicode, this solution seems incur high cost, right?
aslo, do u know any application of this problem?
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
j*x
55 楼
26搞错了，假设'a'-'z'
unicode的不懂
不管怎么说第一步的collapse一定是有用的
of 26?
high cost, right?
【在 h***n 的大作中提到】
: do u assume char set is "a" - "z"? why it is 24 instead of 26?
: if the char set is unicode, this solution seems incur high cost, right?
: aslo, do u know any application of this problem?
unicode的不懂
不管怎么说第一步的collapse一定是有用的
of 26?
high cost, right?
【在 h***n 的大作中提到】
: do u assume char set is "a" - "z"? why it is 24 instead of 26?
: if the char set is unicode, this solution seems incur high cost, right?
: aslo, do u know any application of this problem?
h*n
56 楼
it seems I understand your solution correctly
the only concern is that, when the character set is large (say unicode which
has chars more than 109,000), we can no longer take advantage of trie, but
instead, we just have to compare them directly, which lead to O(n^2) solutio
n
【在 j********x 的大作中提到】
: 26搞错了，假设'a'-'z'
: unicode的不懂
: 不管怎么说第一步的collapse一定是有用的
:
: of 26?
: high cost, right?
the only concern is that, when the character set is large (say unicode which
has chars more than 109,000), we can no longer take advantage of trie, but
instead, we just have to compare them directly, which lead to O(n^2) solutio
n
【在 j********x 的大作中提到】
: 26搞错了，假设'a'-'z'
: unicode的不懂
: 不管怎么说第一步的collapse一定是有用的
:
: of 26?
: high cost, right?
f*g
57 楼
看了上面的回复，受到启发。
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧
c*e
58 楼
No need to compare the function value.
【在 c******w 的大作中提到】
: 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
【在 c******w 的大作中提到】
: 二次函数的值先算还是后算没区别.不过你这样要多做几次减法
f*g
59 楼
写了个测试下，用了一个常用字典
结果是：
foresightedness
blackjack
有点意思，就是不知道这个变态的题目有什么实际意义
结果是：
foresightedness
blackjack
有点意思，就是不知道这个变态的题目有什么实际意义
l*a
60 楼
my solution:
1.create hash for each word
2.sort the dictionary by word length.
assume the dictionary become
a[0],a[1]......
find the largest k so that hash(a[0])&hash(a[k])==0,
get max=len(a[0])*len(a[k])
find max i in [2,k-1] so that hash(a[1])&hash(a[i])==0,
compare max and len(a[1])*len(a[i])
next step find max j in [3,i-1]....
【在 f***g 的大作中提到】
: 看了上面的回复，受到启发。
: 也说一个想法：
: Assumption: ASCII
: 对于每一个单词，利用bitset原理
: 用一个int就可以表示出其字母出现的模式。
: 假设用最低位表示z，最高的第7位表示a
: 预处理
: 1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
: 2.在每个数组中的保存符合当前模式的最长的单词。
: 找最大：
1.create hash for each word
2.sort the dictionary by word length.
assume the dictionary become
a[0],a[1]......
find the largest k so that hash(a[0])&hash(a[k])==0,
get max=len(a[0])*len(a[k])
find max i in [2,k-1] so that hash(a[1])&hash(a[i])==0,
compare max and len(a[1])*len(a[i])
next step find max j in [3,i-1]....
【在 f***g 的大作中提到】
: 看了上面的回复，受到启发。
: 也说一个想法：
: Assumption: ASCII
: 对于每一个单词，利用bitset原理
: 用一个int就可以表示出其字母出现的模式。
: 假设用最低位表示z，最高的第7位表示a
: 预处理
: 1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
: 2.在每个数组中的保存符合当前模式的最长的单词。
: 找最大：
i*s
61 楼
y*2
62 楼
同感……
g*s
63 楼
What's this? Given class bst, design a class iterator to do the following?
for (bst::in_order_iterator it = bst.root(); it != bst.end(); ++ it) {
it->print();
}
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
g*s
64 楼
If m words, length of words are L_1, L_2,..., L_m. O(m^2+sum(L_i))?
Is O(mlg(m)) possible?
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
m*q
65 楼
创建trie没问题，查询怎么查啊，比如 查找和单词hello 没有
共同字母的单词，貌似trie无法有效支持这种类型的查询啊，
感觉只能遍历。
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
共同字母的单词，貌似trie无法有效支持这种类型的查询啊，
感觉只能遍历。
【在 j********x 的大作中提到】
: 定义一个函数collapse(word) {
: return sort(unique(word)); //返回经过排序的独一字符
: }
: 处理每个单词，collapse(word)，同时将返回值插入一个trie，叶子节点记录目前插入
: 的单词长度的最大值。然后查询吧
: 对于每个单吃，查询时间是O(24-length(word'))，word'是collapse以后的单词。复杂
: 度O(n)
r*g
66 楼
re
g*y
67 楼
radiochromatogram * suspensefulnesses = 289
public class WordProduct {
private final static String DIR = "src/test/resources/com/practice/
search";
public void search() {
int N = 30;
String content = FileHelper.readFile(DIR + "/WORD.LST");
String[] words = content.split("\n");
HashSet[] set = new HashSet[30];
HashMap map = new HashMap();
for (int i=0; i();
}
for (String word : words) {
set[word.length()].add(word);
map.put(word, score(word));
}
ArrayList pairs = new ArrayList();
for (int i=1; i<30; i++) {
for (int j=i; j<30; j++) {
pairs.add(new Pair(j, i));
}
}
Collections.sort(pairs, new Comparator(){
public int compare(Pair a, Pair b) {
return b.x * b.y - a.x * a.y;
}
});
for (Pair p : pairs) {
for (String w1 : set[p.x]) {
for (String w2 : set[p.y]) {
if ((map.get(w1) & map.get(w2)) == 0) {
System.out.println(w1 + " * " + w2 + " = " + p.x*p.y
);
return;
}
}
}
}
}
private int score(String word) {
int score = 0;
for (int i=0; i
}
return score;
}
private class Pair {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
new WordProduct().search();
}
}
public class WordProduct {
private final static String DIR = "src/test/resources/com/practice/
search";
public void search() {
int N = 30;
String content = FileHelper.readFile(DIR + "/WORD.LST");
String[] words = content.split("\n");
HashSet
HashMap
for (int i=0; i
}
for (String word : words) {
set[word.length()].add(word);
map.put(word, score(word));
}
ArrayList
for (int i=1; i<30; i++) {
for (int j=i; j<30; j++) {
pairs.add(new Pair(j, i));
}
}
Collections.sort(pairs, new Comparator
public int compare(Pair a, Pair b) {
return b.x * b.y - a.x * a.y;
}
});
for (Pair p : pairs) {
for (String w1 : set[p.x]) {
for (String w2 : set[p.y]) {
if ((map.get(w1) & map.get(w2)) == 0) {
System.out.println(w1 + " * " + w2 + " = " + p.x*p.y
);
return;
}
}
}
}
}
private int score(String word) {
int score = 0;
for (int i=0; i
}
return score;
}
private class Pair {
int x, y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
public static void main(String[] args) {
new WordProduct().search();
}
}
g*y
68 楼
想法：
1. 把每个单词的score算出来，放在hashmap里。score的定义是：26位，某个字母出现
则该位为1. 判断两个单词是否有共同字母 = score(w1) & score(w2) > 0
2. 把单词长度对按乘积从高到低排序，然后按这个顺序搜单词库，找到的第一组满组
的单词对就是解。
Code在楼上
1. 把每个单词的score算出来，放在hashmap里。score的定义是：26位，某个字母出现
则该位为1. 判断两个单词是否有共同字母 = score(w1) & score(w2) > 0
2. 把单词长度对按乘积从高到低排序，然后按这个顺序搜单词库，找到的第一组满组
的单词对就是解。
Code在楼上
c*m
69 楼
2词函数那个可以先算拐点（拐点之间的区间都是单调的），然后几次MERGE SORT 就好
了。
了。
a*1
70 楼
没人讨论一下4 怎么做？
很没头绪，我估计会先问问 search server本身提供哪些功能，
replicate和index update再哪里做啊？
middle layer大概会做load balance 和cache ?
哪位大拿谈谈这一题
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
很没头绪，我估计会先问问 search server本身提供哪些功能，
replicate和index update再哪里做啊？
middle layer大概会做load balance 和cache ?
哪位大拿谈谈这一题
【在 r*****t 的大作中提到】
: 好久之前面的了……onsite了之后就感觉不怎么行，最后果然悲剧……
: phone interview
: 给一个二次函数以及一个排好序的数组，计算数组中每个元素的函数值，要求输出也是
: 排好序的
: onsite
: 1. 两个文件里面存着行程安排，开始时间以及结束时间，设计算法找conflicts
: 2. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大
: 3. 写一个二叉树遍历的iterator
: 4. design一个middle layer，在客户端跟搜索服务器之间
r*n
71 楼
不考虑unicode 我觉得trie还是比较可行的做法：
1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
2、对于第二层结点开始的subtrees, 找各自的maxheight
3、选出两个height最大的substree 就是答案
1. O(n), where n is the number of words in the dictionary
2. O(|E|*m), where m is the (average) total number of nodes in each substree
and |E| is the size of the alphabetic set.
3. O(1)
1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
2、对于第二层结点开始的subtrees, 找各自的maxheight
3、选出两个height最大的substree 就是答案
1. O(n), where n is the number of words in the dictionary
2. O(|E|*m), where m is the (average) total number of nodes in each substree
and |E| is the size of the alphabetic set.
3. O(1)
g*y
72 楼
computer, haul
没有一层字母一样，但是有共同字母u
substree
【在 r*****n 的大作中提到】
: 不考虑unicode 我觉得trie还是比较可行的做法：
: 1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
: 2、对于第二层结点开始的subtrees, 找各自的maxheight
: 3、选出两个height最大的substree 就是答案
: 1. O(n), where n is the number of words in the dictionary
: 2. O(|E|*m), where m is the (average) total number of nodes in each substree
: and |E| is the size of the alphabetic set.
: 3. O(1)
没有一层字母一样，但是有共同字母u
substree
【在 r*****n 的大作中提到】
: 不考虑unicode 我觉得trie还是比较可行的做法：
: 1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
: 2、对于第二层结点开始的subtrees, 找各自的maxheight
: 3、选出两个height最大的substree 就是答案
: 1. O(n), where n is the number of words in the dictionary
: 2. O(|E|*m), where m is the (average) total number of nodes in each substree
: and |E| is the size of the alphabetic set.
: 3. O(1)
r*n
73 楼
恩 make sense
题意理解有误
这个题有比O(n^2)好的算法么？
写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
return:
stekelenburg,hohohohohoho
代码如下
int myfunc(string a, string b){
return a.size()>b.size();
}
void foo(vector arr){
if(!arr.size())
return;
//step 1. sort w.r.t. lentgh of each word O(nlogn)
sort(arr.begin(), arr.end(), myfunc);
//step 2. compute signature for each word
vector sig;
for(long i=0; i
for(long j=0; j
tmp |= (1<}
sig.push_back(tmp);
}
//step 2. compare each other O(n^2)
int mymax = 0;
string maxstr1, maxstr2;
for(long i=0; i
int tmp = int(arr[i].size()*arr[j].size());
if(mymax
maxstr2 = arr[j];
mymax = tmp;
}
}
}
}
//step 3. get the two words
cout<
int main(){
vector arr;
//http://www.math.sjsu.edu/~foster/dictionary.txt
ifstream fin;
fin.open("dictionary.txt", ifstream::in);
while(fin.good()){
string sztmp;
getline(fin, sztmp);
arr.push_back(sztmp);
}
cout<
foo(arr);
return 1;
}
【在 g**********y 的大作中提到】
: computer, haul
: 没有一层字母一样，但是有共同字母u
:
: substree
题意理解有误
这个题有比O(n^2)好的算法么？
写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
return:
stekelenburg,hohohohohoho
代码如下
int myfunc(string a, string b){
return a.size()>b.size();
}
void foo(vector
if(!arr.size())
return;
//step 1. sort w.r.t. lentgh of each word O(nlogn)
sort(arr.begin(), arr.end(), myfunc);
//step 2. compute signature for each word
vector
for(long i=0; i
for(long j=0; j
tmp |= (1<}
sig.push_back(tmp);
}
//step 2. compare each other O(n^2)
int mymax = 0;
string maxstr1, maxstr2;
for(long i=0; i
int tmp = int(arr[i].size()*arr[j].size());
if(mymax
maxstr2 = arr[j];
mymax = tmp;
}
}
}
}
//step 3. get the two words
cout<
int main(){
vector
//http://www.math.sjsu.edu/~foster/dictionary.txt
ifstream fin;
fin.open("dictionary.txt", ifstream::in);
while(fin.good()){
string sztmp;
getline(fin, sztmp);
arr.push_back(sztmp);
}
cout<
foo(arr);
return 1;
}
【在 g**********y 的大作中提到】
: computer, haul
: 没有一层字母一样，但是有共同字母u
:
: substree
g*y
74 楼
不需要O(n^2), 可以用加速的办法，用你的字典，也可以1秒钟内出答案。
1. 我给的code里就用了：从大算到小，可以避免算很多无用的。
2. 对长度L的单词，每个score只留一个，可以减少很多计算。
3. 算等长的两个词时，循环上可以优化。
【在 r*****n 的大作中提到】
: 恩 make sense
: 题意理解有误
: 这个题有比O(n^2)好的算法么？
: 写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
: return:
: stekelenburg,hohohohohoho
: 代码如下
: int myfunc(string a, string b){
: return a.size()>b.size();
: }
1. 我给的code里就用了：从大算到小，可以避免算很多无用的。
2. 对长度L的单词，每个score只留一个，可以减少很多计算。
3. 算等长的两个词时，循环上可以优化。
【在 r*****n 的大作中提到】
: 恩 make sense
: 题意理解有误
: 这个题有比O(n^2)好的算法么？
: 写了一下O(n^2) 测了一下349901词的一个dichttp://www.math.sjsu.edu/~foster/dictionary.txt 要跑5-6分钟
: return:
: stekelenburg,hohohohohoho
: 代码如下
: int myfunc(string a, string b){
: return a.size()>b.size();
: }
相关阅读
全才孩子美国的幼儿园都用哪些教材呢？12"自行车有用吗?是不是一开始就应该从14"开始买?支持北滩法律求助-如何洗刷遗弃及危害儿童并有返回意图的犯罪指控医院和保险的糊涂帐找谁解决？关于小男孩一起玩的事情在美国生小孩的有保存脐带血吗？我还见过生小孩之前就打算把孩子送回国的求出路 (转载)一般娃闹到什么程度才可以去安慰她？问题：情人节，娃daycare要求给班上小朋友送卡片大家都看看这个youtube吧大家的意见：一人带宝宝回国的可行性？请大家推荐一口炒菜的锅子吧！谁有奶粉coupon？第一张全满分的报告卡Ipad太神奇了陪孩子学琴的同时自己能否也“偷学”到？求给toddler(2 years old)蒸鱼用的source (转载)