两道A家面试题 - 未名空间MITBBS历史存档

l*h2013-03-12 07:03

1 楼

1.硬盘上有2^40个正整数,16M内存, 如何找到第一缺的正整数。假设硬盘足够大。
这个跟通常的那个找missing integer的不大一样。没想到好办法。
2. 手机上的数字一般对应好几个字符，比如
1-> null
2->'a' or 'b' or 'c'
...
9->'w' or 'x' or 'y' or 'z'
现在给你一串数字，比如2 4 5 6 8 6 9 6, 找出最长的匹配的word. 假设词典已给定。

g*r2013-03-12 07:03

2 楼

第一题 sort
第二题 BFS

c*t2013-03-12 07:03

3 楼

第一题bitmap? 硬盘足够大有啥用？外排序?
第二题没懂 2 4 5 6 8 6 9 6，不就是8个字符吗，难道是找最长的匹配的substring
in dictionary?

定。

【在 l**h 的大作中提到】

: 1.硬盘上有2^40个正整数,16M内存, 如何找到第一缺的正整数。假设硬盘足够大。
: 这个跟通常的那个找missing integer的不大一样。没想到好办法。
: 2. 手机上的数字一般对应好几个字符，比如
: 1-> null
: 2->'a' or 'b' or 'c'
: ...
: 9->'w' or 'x' or 'y' or 'z'
: 现在给你一串数字，比如2 4 5 6 8 6 9 6, 找出最长的匹配的word. 假设词典已给定。

l*h2013-03-12 07:03

4 楼

第一题bitmap也不行，内存太小
对，第二题找最长substring in dictionary

substring

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

: 第一题bitmap? 硬盘足够大有啥用？外排序?
: 第二题没懂 2 4 5 6 8 6 9 6，不就是8个字符吗，难道是找最长的匹配的substring
: in dictionary?
:
: 定。

l*h2013-03-12 07:03

5 楼

可不可以展开讲一下？

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

: 第一题 sort
: 第二题 BFS

d*x2013-03-12 07:03

6 楼

第一题bitmap只需要跑2^5遍，2^45这个量级，还是在可承受的范围内的
如果用硬盘做存储的话，交换几次就要命了

【在 l**h 的大作中提到】

: 第一题bitmap也不行，内存太小
: 对，第二题找最长substring in dictionary
:
: substring

f*42013-03-12 07:03

7 楼

1. 第一遍按整数区间进行计数；遍历完判定第一缺属于哪一区间；遍历第二遍只关注
在该区间的数
2. 遍历+剪枝。没想到好办法

【在 l**h 的大作中提到】

: 可不可以展开讲一下？

d*x2013-03-12 07:03

8 楼

如何计数。。有重复啊

【在 f*******4 的大作中提到】

: 1. 第一遍按整数区间进行计数；遍历完判定第一缺属于哪一区间；遍历第二遍只关注
: 在该区间的数
: 2. 遍历+剪枝。没想到好办法

S*o2013-03-12 07:03

9 楼

什么是第一缺？

定。

【在 l**h 的大作中提到】

: 1.硬盘上有2^40个正整数,16M内存, 如何找到第一缺的正整数。假设硬盘足够大。
: 这个跟通常的那个找missing integer的不大一样。没想到好办法。
: 2. 手机上的数字一般对应好几个字符，比如
: 1-> null
: 2->'a' or 'b' or 'c'
: ...
: 9->'w' or 'x' or 'y' or 'z'
: 现在给你一串数字，比如2 4 5 6 8 6 9 6, 找出最长的匹配的word. 假设词典已给定。

a*32013-03-12 07:03

10 楼

第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
了。
第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
，那么就分段写回硬盘。
比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
将数据写入对应的区间。
第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
IO复杂度，2遍读，一遍写

d*x2013-03-12 07:03

11 楼

求问2^40个数，32bit的int如何没有重复

算？

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

: 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
: 如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
: 数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
: 了。
: 第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
: ，那么就分段写回硬盘。
: 比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
: 将数据写入对应的区间。
: 第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
: IO复杂度，2遍读，一遍写

a*32013-03-12 07:03

12 楼

楼主在哪里说了是32bit的int？
楼主的原话是“正整数”，既没有说是32bit，也没说是int，你哪里脑补来的这个数据？

【在 d**********x 的大作中提到】

: 求问2^40个数，32bit的int如何没有重复
:
: 算？

d*x2013-03-12 07:03

13 楼

太好了
那你如何分区间？正整数范围无限，你如何脑补成有限的范围？
更好玩的是，来一个2^(2^(2^(2^10)))的整数，你计算机如何存储？还正整数，真当自
己数
学家了

据？

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

: 楼主在哪里说了是32bit的int？
: 楼主的原话是“正整数”，既没有说是32bit，也没说是int，你哪里脑补来的这个数据？

a*32013-03-12 07:03

14 楼

我什么时候说过是无限？总是假设别人的立场竖起靶子打有意思么？
我说未必是32位的意思是，是在当下主流计算能表示的范围内（64bit），题目没说的
话，任意范围都可以。你如果见过比这个更牛逼寻址范围，那算我拜服，您是神。
其实不是想跟你吵架，面试遇到这种问题，问清楚面试官到底是什么范围就行。自己闷
头假设一个，只会让人觉的你自己太想当然。

【在 d**********x 的大作中提到】

: 太好了
: 那你如何分区间？正整数范围无限，你如何脑补成有限的范围？
: 更好玩的是，来一个2^(2^(2^(2^10)))的整数，你计算机如何存储？还正整数，真当自
: 己数
: 学家了
:
: 据？

c*t2013-03-12 07:03

15 楼

第二题，find longest substring in dict. 我觉得trie也能做。

算？

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

: 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
: 如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
: 数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
: 了。
: 第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
: ，那么就分段写回硬盘。
: 比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
: 将数据写入对应的区间。
: 第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
: IO复杂度，2遍读，一遍写

L*r2013-03-12 07:03

16 楼

I think your solution is good. Thanks for sharing it.

算？

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

: 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
: 如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
: 数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
: 了。
: 第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
: ，那么就分段写回硬盘。
: 比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
: 将数据写入对应的区间。
: 第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
: IO复杂度，2遍读，一遍写

k*e2013-03-12 07:03

17 楼

第二个是BFS？

定。

【在 l**h 的大作中提到】

: 1.硬盘上有2^40个正整数,16M内存, 如何找到第一缺的正整数。假设硬盘足够大。
: 这个跟通常的那个找missing integer的不大一样。没想到好办法。
: 2. 手机上的数字一般对应好几个字符，比如
: 1-> null
: 2->'a' or 'b' or 'c'
: ...
: 9->'w' or 'x' or 'y' or 'z'
: 现在给你一串数字，比如2 4 5 6 8 6 9 6, 找出最长的匹配的word. 假设词典已给定。