l**h
发帖数: 893 | 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********r
发帖数: 58 | |
c********t
发帖数: 5706 | 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**h
发帖数: 893 | 4 第一题bitmap也不行，内存太小
对，第二题找最长substring in dictionary
substring
【在 c********t 的大作中提到】
: 第一题bitmap? 硬盘足够大有啥用？外排序?
: 第二题 没懂 2 4 5 6 8 6 9 6，不就是8个字符吗，难道是找最长的匹配的substring
: in dictionary?
:
: 定。
|
l**h
发帖数: 893 | 5 可不可以展开讲一下？
【在 g********r 的大作中提到】
: 第一题 sort
: 第二题 BFS
|
d**********x
发帖数: 4083 | 6 第一题bitmap只需要跑2^5遍，2^45这个量级，还是在可承受的范围内的
如果用硬盘做存储的话，交换几次就要命了
【在 l**h 的大作中提到】
: 第一题bitmap也不行，内存太小
: 对，第二题找最长substring in dictionary
:
: substring
|
f*******4
发帖数: 64 | 7 1. 第一遍按整数区间进行计数；遍历完判定第一缺属于哪一区间；遍历第二遍只关注
在该区间的数
2. 遍历+剪枝。没想到好办法
【在 l**h 的大作中提到】
: 可不可以展开讲一下？
|
d**********x
发帖数: 4083 | 8 如何计数。。有重复啊
【在 f*******4 的大作中提到】
: 1. 第一遍按整数区间进行计数；遍历完判定第一缺属于哪一区间；遍历第二遍只关注
: 在该区间的数
: 2. 遍历+剪枝。没想到好办法
|
S********o
发帖数: 4 | 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*******3
发帖数: 27 | 10 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
了。
第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
，那么就分段写回硬盘。
比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
将数据写入对应的区间。
第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
IO复杂度，2遍读，一遍写 |
|
|
d**********x
发帖数: 4083 | 11 求问2^40个数，32bit的int如何没有重复
算？
【在 a*******3 的大作中提到】
: 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
: 如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
: 数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
: 了。
: 第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
: ，那么就分段写回硬盘。
: 比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
: 将数据写入对应的区间。
: 第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
: IO复杂度，2遍读，一遍写
|
a*******3
发帖数: 27 | 12 楼主在哪里说了是32bit的int？
楼主的原话是“正整数”，既没有说是32bit，也没说是int，你哪里脑补来的这个数据？
【在 d**********x 的大作中提到】
: 求问2^40个数，32bit的int如何没有重复
:
: 算？
|
d**********x
发帖数: 4083 | 13 太好了
那你如何分区间？正整数范围无限，你如何脑补成有限的范围？
更好玩的是，来一个2^(2^(2^(2^10)))的整数，你计算机如何存储？还正整数，真当自
己数
学家了
据？
【在 a*******3 的大作中提到】
: 楼主在哪里说了是32bit的int？
: 楼主的原话是“正整数”，既没有说是32bit，也没说是int，你哪里脑补来的这个数据？
|
a*******3
发帖数: 27 | 14 我什么时候说过是无限？总是假设别人的立场竖起靶子打有意思么？
我说未必是32位的意思是，是在当下主流计算能表示的范围内（64bit），题目没说的
话，任意范围都可以。你如果见过比这个更牛逼寻址范围，那算我拜服，您是神。
其实不是想跟你吵架，面试遇到这种问题，问清楚面试官到底是什么范围就行。自己闷
头假设一个，只会让人觉的你自己太想当然。
【在 d**********x 的大作中提到】
: 太好了
: 那你如何分区间？正整数范围无限，你如何脑补成有限的范围？
: 更好玩的是，来一个2^(2^(2^(2^10)))的整数，你计算机如何存储？还正整数，真当自
: 己数
: 学家了
:
: 据？
|
c********t
发帖数: 5706 | 15 第二题，find longest substring in dict. 我觉得trie也能做。
算？
【在 a*******3 的大作中提到】
: 第二题是找最长匹配的前缀码？还是说从某个特定位置的开始的数字串匹配到字典也算？
: 如果是第一种的话，可以把词典简称 trie数吧，不是以字母来建，而是以字母对应的
: 数字来建，这样查询数字串直接一遍遍历trie，找到最底层的，是合法word的节点就行
: 了。
: 第一题，2^40的数，如果没有重复的，那么分段计数应该是最好的方法。如果有重复的
: ，那么就分段写回硬盘。
: 比如16M内存，那么分为长度为16M为一个区间，读一遍，将每个区间单独为一个文件。
: 将数据写入对应的区间。
: 第二遍遍历每个文件，用16M做bitmap，只需要找到第一个置0的位就行了。
: IO复杂度，2遍读，一遍写
|
L*********r
发帖数: 9 | 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****e
发帖数: 116 | 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. 假设词典已给定。
|
