男不养猫，女不养犬 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

男不养猫，女不养犬 (转载)

男不养猫，女不养犬 (转载)# Joke - 肚皮舞运动

P*c2011-05-06 07:05

1 楼

1. 给定一串浮点数，要求转成string, 转化完成后要求假如要排序的话，string的顺
序和对应的原来数的排序一样。
2. 给一个string, 比如"facebook", 可以拆成"face"和"book", 对任一string, 找出
最长的可以拆分成其他单词的子串。
3. 给定很多文章，比如google news里的文章，如何快速找到所有相同topic的文章。
4. 有10个unsorted array, 分给10太不同的机器处理，这10台机器之间不能通信，但
可以和总机通信，如何求总的median. 如何减少数据量的传输。
5. 每个电话号码都对应字母，打印出通过按号码能生成的所有valid的英文词，用作号码里的单词用，比如1-800-432-JUNK里面的JUNK.

B*e2011-05-06 07:05

2 楼

【以下文字转载自 Sex 讨论区】
发信人: fuyun2011 (FuYun), 信区: Sex
标题: 男不养猫，女不养犬 (转载)
发信站: BBS 未名空间站 (Fri May 6 09:28:03 2011, 美东)
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标题: 男不养猫，女不养犬
发信站: BBS 未名空间站 (Thu May 5 22:46:23 2011, 美东)
汉末，蜀汉裸眠成风。李郎喜猫，夜必共枕。入夜，李郎春梦，尘根起伏。猫惊为鼠，
捕之，尘根断，吞食。有邻闻之，广为传。故老者多嘱子孙：猫为男患，不可养之。史
记，蜀太监盛，亦猫为之。
汉末，东岳有郎，喜结连理。月余，夫欲差之鲁中，甚忧娇妻，遂购一雄犬，一伴妻
之苦闷，二防贼之淫威。三栽后，夫还，入门闻犬吠，抬首观冷颜。是夜，夫欲行周公
之礼，惊见妻肤旧痕累累，惑，追其由。妻无奈：狗解人意，夜夜同眠。。。
翌日，夫杀犬，然妻念旧情，殉之山崖。

g*y2011-05-06 07:05

3 楼

1不清楚题意，要求排序的话，先排序再转换？
2, 5都是Trie的应用
2. L[i] = longest length of substring can split into words, starting from
position i (0<=ifor i = N-1 -> 0 {
L[i] = max(L[i+word.length] + word.length, for all valid word starting at
i)
}
return max(L[])
5. DFS
3好象需要问很多问题，才能开始解，这个描述太泛了。
4可以用二分，我以前贴过code。可能有更好的解法，搬板凳坐等。

P*c2011-05-06 07:05

4 楼

1的题意不是说要排序，是说通过某种转换，转换之后的string假设要排序的话，排出来的顺序应该跟原来数字排出来的顺序一样。这个转换可以是任意的转换，不是简单的把数转成string即可。因为那样的话假如排序，就不一样了。比如string排序，123应该排在32的前面。但是数字排序，123应该排在32后面，所以要求的转换，要转成string之后，123对应的string还能排在32的后面。
5. DFS可以吗？单词里面可能某个字母会重复出现的，不是visit一次就够了。

at

【在 g**********y 的大作中提到】

: 1不清楚题意，要求排序的话，先排序再转换？
: 2, 5都是Trie的应用
: 2. L[i] = longest length of substring can split into words, starting from
: position i (0<=i: for i = N-1 -> 0 {
: L[i] = max(L[i+word.length] + word.length, for all valid word starting at
: i)
: }
: return max(L[])
: 5. DFS

g*y2011-05-06 07:05

5 楼

字母重不重复出现没关系，大致code:
public void dfs(String str, Trie trie) {
if (str.length() == 0) {
if (trie.isWord()) print(trie.word);
}

char number = str.charAt(0);
for (c : getCharacter(number)) {
Trie next = trie.get(c);
if (next != null) dfs(str.substring(1), next);
}
}

【在 P**********c 的大作中提到】

: 1的题意不是说要排序，是说通过某种转换，转换之后的string假设要排序的话，排出来的顺序应该跟原来数字排出来的顺序一样。这个转换可以是任意的转换，不是简单的把数转成string即可。因为那样的话假如排序，就不一样了。比如string排序，123应该排在32的前面。但是数字排序，123应该排在32后面，所以要求的转换，要转成string之后，123对应的string还能排在32的后面。
: 5. DFS可以吗？单词里面可能某个字母会重复出现的，不是visit一次就够了。
:
: at

P*c2011-05-06 07:05

6 楼

这个只是判断给定str是不是在trie里吧。用电话号码构建str呢？这个才是主要的吧。

【在 g**********y 的大作中提到】

: 字母重不重复出现没关系，大致code:
: public void dfs(String str, Trie trie) {
: if (str.length() == 0) {
: if (trie.isWord()) print(trie.word);
: }
:
: char number = str.charAt(0);
: for (c : getCharacter(number)) {
: Trie next = trie.get(c);
: if (next != null) dfs(str.substring(1), next);

g*y2011-05-06 07:05

7 楼

电话号码转str都在那个函数getCharacter(number)里，那个实现很简单，就是个hard
code的映射

【在 P**********c 的大作中提到】

: 这个只是判断给定str是不是在trie里吧。用电话号码构建str呢？这个才是主要的吧。

P*c2011-05-06 07:05

8 楼

我的意思是，题目是让打出所有的通过按号码可生成的valid的words, 你给的这个函数，str这个input怎么产生？是要把所有可能的情况都遍历一遍吗？
另外，题意更清楚一些，这个是找那种简化号码，就是比如1－800－352－JUNK. 所以一个数字可以当作3个字母，但是不出现按两次按三次不同的情况

hard

【在 g**********y 的大作中提到】

: 电话号码转str都在那个函数getCharacter(number)里，那个实现很简单，就是个hard
: code的映射

g*y2011-05-06 07:05

9 楼

这个函数输入就是18003525865, 打印的就是这个数对应的所有valid的word

数，str这个input怎么产生？是要把所有可能的情况都遍历一遍吗？
以一个数字可以当作3个字母，但是不出现按两次按三次不同的情况

【在 P**********c 的大作中提到】

: 我的意思是，题目是让打出所有的通过按号码可生成的valid的words, 你给的这个函数，str这个input怎么产生？是要把所有可能的情况都遍历一遍吗？
: 另外，题意更清楚一些，这个是找那种简化号码，就是比如1－800－352－JUNK. 所以一个数字可以当作3个字母，但是不出现按两次按三次不同的情况
:
: hard

a*22011-05-06 07:05

10 楼

1.是分配一个float最多位数（38-（-38））大小的string，然后左右分别补零吗？
4.可以10个机器分别排序再归并到总机吗？
5.是说找出前三位，或者中间三位，或者后四位能组成的单词？能给个input，ouput的
例子吗？

出来的顺序应该跟原来数字排出来的顺序一样。这个转换可以是任意的转换，不是简单
的把数转成string即可。因为那样的话假如排序，就不一样了。比如string排序，123
应该排在32的前面。但是数字排序，123应该排在32后面，所以要求的转换，要转成
string之后，123对应的string还能排在32的后面。

【在 P**********c 的大作中提到】

P*c2011-05-06 07:05

11 楼

5没有什么input, 就是要打印出所有可用的单词。目的是从这里面挑选想用的号码。
不是给你一个特定的号码找单词。当然你可以遍历所有号码一个一个找，但是不知道那
个是不是最好解法。

【在 a**********2 的大作中提到】

: 1.是分配一个float最多位数（38-（-38））大小的string，然后左右分别补零吗？
: 4.可以10个机器分别排序再归并到总机吗？
: 5.是说找出前三位，或者中间三位，或者后四位能组成的单词？能给个input，ouput的
: 例子吗？
:
: 出来的顺序应该跟原来数字排出来的顺序一样。这个转换可以是任意的转换，不是简单
: 的把数转成string即可。因为那样的话假如排序，就不一样了。比如string排序，123
: 应该排在32的前面。但是数字排序，123应该排在32后面，所以要求的转换，要转成
: string之后，123对应的string还能排在32的后面。

a*22011-05-06 07:05

12 楼

那么按照字母转数字的规则建立一个数字字典树，以后每次判断起来就快了

g*y2011-05-06 07:05

13 楼

对10位的电话号码，找 x1 + ... + xk = 10 的所有解，然后对每个xi, 遍历字典里长
度为xi的单词

【在 P**********c 的大作中提到】

: 5没有什么input, 就是要打印出所有可用的单词。目的是从这里面挑选想用的号码。
: 不是给你一个特定的号码找单词。当然你可以遍历所有号码一个一个找，但是不知道那
: 个是不是最好解法。

P*c2011-05-06 07:05

14 楼

1能详细讲讲你的想法吗？我当时完全没思路, 后来在提示下想到对整数可以用32位二进制来表示，但是没想明白负数应该怎么办。对浮点数的二进制表示也不是很清楚。希望有牛人讲一下。
4. 分别排序不行，具体怎么不行忘记了。好像是因为传输的信息过多。排除了几种可能后，最后我的解法是先在范围内挑一个中间数，然后十台机器分别数自己机器里比这个数大的个数，和比这个数小的个数。然后传给总机让总机加起来，如果比这个数大的数多，那么就在后半部分找，比过比这个数小的数多，就在前半部分找。这样每次总机只需要传一个target给各台机器，各台机器只需要传两个数给总机。他似乎觉得这个是可以的。但是后面又讨论了一些减少数据传输的方法，我云里雾里的，记不清了。

123

【在 a**********2 的大作中提到】

P*c2011-05-06 07:05

15 楼

补充：这些是做search的某公司的面试题。

号码里的单词用，比如1-800-432-JUNK里面的JUNK.

【在 P**********c 的大作中提到】

: 1. 给定一串浮点数，要求转成string, 转化完成后要求假如要排序的话，string的顺
: 序和对应的原来数的排序一样。
: 2. 给一个string, 比如"facebook", 可以拆成"face"和"book", 对任一string, 找出
: 最长的可以拆分成其他单词的子串。
: 3. 给定很多文章，比如google news里的文章，如何快速找到所有相同topic的文章。
: 4. 有10个unsorted array, 分给10太不同的机器处理，这10台机器之间不能通信，但
: 可以和总机通信，如何求总的median. 如何减少数据量的传输。
: 5. 每个电话号码都对应字母，打印出通过按号码能生成的所有valid的英文词，用作号码里的单词用，比如1-800-432-JUNK里面的JUNK.

t*r2011-05-06 07:05

16 楼

http://kipirvine.com/asm/workbook/floating_tut.htm
float binary可以看看这个
我觉得用二进制是个好思路。

P*c2011-05-06 07:05

17 楼

1. 想了一下，把正数的最高一位换成1, 负数的最高一位换成0，对整数应该是可行的
。负数最小的原本是1000....0, 也就是-2^31最高位换成0后就变成0.....0了，还是排在最前面。
正数(含0)最高位换成1之后，都会排在负数后面，而且本身的顺序也没有变化。
不过面试的时候没有想到，唉。

二进制来表示，但是没想明白负数应该怎么办。对浮点数的二进制表示也不是很清楚。
希望有牛人讲一下。
可能后，最后我的解法是先在范围内挑一个中间数，然后十台机器分别数自己机器里比
这个数大的个数，和比这个数小的个数。然后传给总机让总机加起来，如果比这个数大
的数多，那么就在后半部分找，比过比这个数小的数多，就在前半部分找。这样每次总
机只需要传一个target给各台机器，各台机器只需要传两个数给总机。他似乎觉得这个
是可以的。但是后面又讨论了一些减少数据传输的方法，我云里雾里的，记不清了。

【在 P**********c 的大作中提到】

: 1能详细讲讲你的想法吗？我当时完全没思路, 后来在提示下想到对整数可以用32位二进制来表示，但是没想明白负数应该怎么办。对浮点数的二进制表示也不是很清楚。希望有牛人讲一下。
: 4. 分别排序不行，具体怎么不行忘记了。好像是因为传输的信息过多。排除了几种可能后，最后我的解法是先在范围内挑一个中间数，然后十台机器分别数自己机器里比这个数大的个数，和比这个数小的个数。然后传给总机让总机加起来，如果比这个数大的数多，那么就在后半部分找，比过比这个数小的数多，就在前半部分找。这样每次总机只需要传一个target给各台机器，各台机器只需要传两个数给总机。他似乎觉得这个是可以的。但是后面又讨论了一些减少数据传输的方法，我云里雾里的，记不清了。
:
: 123

k*j2011-05-06 07:05

18 楼

电话号码里0和1没有对应的字母。如果是1－＊＊＊－＊＊＊－＊＊＊的电话号码应该
只考虑后9位。

【在 g**********y 的大作中提到】

: 对10位的电话号码，找 x1 + ... + xk = 10 的所有解，然后对每个xi, 遍历字典里长
: 度为xi的单词

k*j2011-05-06 07:05

19 楼

G家?感觉挺像的。

【在 P**********c 的大作中提到】

: 补充：这些是做search的某公司的面试题。
:
: 号码里的单词用，比如1-800-432-JUNK里面的JUNK.

w*r2011-05-06 07:05

20 楼

没有很明白
那不是就找到一个想要的单词，然后转换成数字不就行了？

【在 P**********c 的大作中提到】

g*y2011-05-06 07:05

21 楼

对所有浮点数的整数位取绝对值，求最长位数，假设是k
对正数，整数部分左填充0，到k位。
对负数，全部数字 x 翻转为 9 - x, 整数位左填充0，到k位，最左边加 -
(1) asc('-') < asc('0'), 所有负数在前
(2) 负数数字翻转后，顺序就跟正数排法一样

排在最前面。

【在 P**********c 的大作中提到】

: 1. 想了一下，把正数的最高一位换成1, 负数的最高一位换成0，对整数应该是可行的
: 。负数最小的原本是1000....0, 也就是-2^31最高位换成0后就变成0.....0了，还是排在最前面。
: 正数(含0)最高位换成1之后，都会排在负数后面，而且本身的顺序也没有变化。
: 不过面试的时候没有想到，唉。
:
: 二进制来表示，但是没想明白负数应该怎么办。对浮点数的二进制表示也不是很清楚。
: 希望有牛人讲一下。
: 可能后，最后我的解法是先在范围内挑一个中间数，然后十台机器分别数自己机器里比
: 这个数大的个数，和比这个数小的个数。然后传给总机让总机加起来，如果比这个数大
: 的数多，那么就在后半部分找，比过比这个数小的数多，就在前半部分找。这样每次总

l*m2011-05-06 07:05

22 楼

第一题用科学计数法吧，把order作为string的第一个字符，这样最多能存(10^255)的
range，对32-bit floating point应该够用了。不够用就用两个字符，依次类推。。。
考虑负数的话，在前面再加一个符号位，然后取补(base 10)。

b*a2011-05-06 07:05

23 楼

看看我的想法有没有问题，谢谢。
1. 给定一串浮点数，要求转成string, 转化完成后要求假如要排序的话，string的顺
序和对应的原来数的排序一样。
浮点数字符串排序关键是比较函数，或者转换回数字比较，或者直接比较，只要是普通
的表达方法（即不是科学计数法之类），先处理+/-，然后比较小数点所在位置，最后
若位置相同，则依次比较数字字符不就可以了？
4. 有10个unsorted array, 分给10太不同的机器处理，这10台机器之间不能通信，但
可以和总机通信，如何求总的median. 如何减少数据量的传输。
每个node先遍历一遍，统计数字落在不同区间（可根据需要划分）的个数,然后各node
将此信息送到master，master就可以确定golbal medium在哪个区间，再回到各node,各
node进行第二遍scan，把此区间的数字送到master，master再划分更细区间，最后排序。
5. 每个电话号码都对应字母，打印出通过按号码能生成的所有valid的英文词，用作号
码里的单词用，比如1-800-432-JUNK里面的JUNK.
此题目似乎不是很清晰，如果是如下思路，too expensive
For each phone number
For each sub-number of this phone number
For each enumerate string of this sub-number
Search Tire
可以反过来吗？遍历字典，对每个单词，判断是否合法电话号码的一部分即可。因为电
话键盘上从字母到数字的映射是1:1，所以这样很快。

P*c2011-05-06 07:05

24 楼

这个目的只是interviewer随口一说比如可以用在这上面。题目要求是如何打印出所有
的单词，不是用其他方法实现这个目的。

【在 w****r 的大作中提到】

: 没有很明白
: 那不是就找到一个想要的单词，然后转换成数字不就行了？

P*c2011-05-06 07:05

25 楼

第1题不是让你找一种排序方法让它跟原来的顺序一样，是让你想一种转换方法，转换
成string之后用通用的string排序排出来的结果应该跟原数字一样。

node

【在 b*******a 的大作中提到】

: 看看我的想法有没有问题，谢谢。
: 1. 给定一串浮点数，要求转成string, 转化完成后要求假如要排序的话，string的顺
: 序和对应的原来数的排序一样。
: 浮点数字符串排序关键是比较函数，或者转换回数字比较，或者直接比较，只要是普通
: 的表达方法（即不是科学计数法之类），先处理+/-，然后比较小数点所在位置，最后
: 若位置相同，则依次比较数字字符不就可以了？
: 4. 有10个unsorted array, 分给10太不同的机器处理，这10台机器之间不能通信，但
: 可以和总机通信，如何求总的median. 如何减少数据量的传输。
: 每个node先遍历一遍，统计数字落在不同区间（可根据需要划分）的个数,然后各node
: 将此信息送到master，master就可以确定golbal medium在哪个区间，再回到各node,各

r*g2011-05-06 07:05

26 楼

第5题是要你把所有可能形成的英文单词都打印出来，是吧，一个个遍历号码的话似乎
开销总是很大啊，坐等更好的方法。

号码里的单词用，比如1-800-432-JUNK里面的JUNK.

【在 P**********c 的大作中提到】

f*i2011-05-06 07:05

27 楼

先把10个字母以下单词对应该的number都找出来，做成multi_hash_map, key是number,
value是单词，
然后number的suffix tree里每一个对着hash_map查

【在 r*******g 的大作中提到】

: 第5题是要你把所有可能形成的英文单词都打印出来，是吧，一个个遍历号码的话似乎
: 开销总是很大啊，坐等更好的方法。
:
: 号码里的单词用，比如1-800-432-JUNK里面的JUNK.

m*q2011-05-06 07:05

28 楼

好思路。一个小地方：
对于负数，应该先整数位填充0到k位，然后再翻转
举例:
-35, -7 => 填充0 => 35,07 => 翻转 => 64,92
-35，-7 => 翻转 => 64, 2 => 填充0 => 64,02

【在 g**********y 的大作中提到】

: 对所有浮点数的整数位取绝对值，求最长位数，假设是k
: 对正数，整数部分左填充0，到k位。
: 对负数，全部数字 x 翻转为 9 - x, 整数位左填充0，到k位，最左边加 -
: (1) asc('-') < asc('0'), 所有负数在前
: (2) 负数数字翻转后，顺序就跟正数排法一样
:
: 排在最前面。

j*x2011-05-06 07:05

29 楼

没有字典怎么定义单词？

【在 P**********c 的大作中提到】

: 这个目的只是interviewer随口一说比如可以用在这上面。题目要求是如何打印出所有
: 的单词，不是用其他方法实现这个目的。