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. 假设词典已给定。
|