C***n 发帖数: 452 | 1 given a set of numbers randing from 0 to 4G,
also a memory of 640 bytes
how to find the numbers between 0 to 4G that are not in the set?
with 640 bytes of memeory, how could we find those absent numbers out? |
K*********a 发帖数: 210 | 2 use each bit in the 640 bytes to represent each number from 1 to 4G. Set the
bit to 1 if the number exists in the set.
640bytes > 4G bits
The question is how can very large numbers (e.g., 4G) fit in memory? |
n*******r 发帖数: 22 | 3 640 bytes = 640 * 8 = 5120 bits
只能表示5120个数啊。
这个应该是要分段处理,用类似mapreduce的方法。
the
【在 K*********a 的大作中提到】 : use each bit in the 640 bytes to represent each number from 1 to 4G. Set the : bit to 1 if the number exists in the set. : 640bytes > 4G bits : The question is how can very large numbers (e.g., 4G) fit in memory?
|
j***r 发帖数: 69 | 4 CareerCup Top 150 Questions 中有。 |
K*********a 发帖数: 210 | 5 my bad, for some reason, i thought 4G was 4000.
I guess you can repeat the bit setting process until go through all 4G
numbers. |
C***n 发帖数: 452 | 6 which one do you refer to?
CareerCup Top 150 Questions 中有。
【在 j***r 的大作中提到】 : CareerCup Top 150 Questions 中有。
|
l*****a 发帖数: 14598 | 7 system design and memory limit No.3
chapter 11 or 12
【在 C***n 的大作中提到】 : which one do you refer to? : : CareerCup Top 150 Questions 中有。
|
g*****i 发帖数: 19 | 8 (1) set up an integer matrix D(9 * 10), every cell used as a counter of one digital from (0,1,2 ...9) in 10^0, 10^1, 10^2 .... 10^9 respectivly,
so totally use 4*9*10=360Bytes.
(2) intialize all cells to what a digital should appear totally if all numbers from 0 ~ 4G are scaned. when a number is read, update the respective cells. for
example, with 4723, cells D[0][3], D[1][2], D[2][7], D[3][4] are counted down one, D[5][0] to D[9][0] also.
(3) after all numbers are scaned, build the missing numbers through the inforation in the matrix D, simatanously update D untill all cell is 0.
【在 C***n 的大作中提到】 : given a set of numbers randing from 0 to 4G, : also a memory of 640 bytes : how to find the numbers between 0 to 4G that are not in the set? : with 640 bytes of memeory, how could we find those absent numbers out?
|
n*******t 发帖数: 77 | 9 suppose we finally find the missing digits are 1 and 2 for 10^0, and 3
and 4 for 10^1. The missing numbers should be 13 and 24, or 14 and 23?
of one digital from (0,1,2 ...9) in 10^0, 10^1, 10^2 .... 10^9
respectivly,
all numbers from 0 ~ 4G are scaned. when a number is read, update the
respective cells. for
counted down one, D[5][0] to D[9][0] also.
the inforation in the matrix D, simatanously update D untill all cell
is 0.
【在 g*****i 的大作中提到】 : (1) set up an integer matrix D(9 * 10), every cell used as a counter of one digital from (0,1,2 ...9) in 10^0, 10^1, 10^2 .... 10^9 respectivly, : so totally use 4*9*10=360Bytes. : (2) intialize all cells to what a digital should appear totally if all numbers from 0 ~ 4G are scaned. when a number is read, update the respective cells. for : example, with 4723, cells D[0][3], D[1][2], D[2][7], D[3][4] are counted down one, D[5][0] to D[9][0] also. : (3) after all numbers are scaned, build the missing numbers through the inforation in the matrix D, simatanously update D untill all cell is 0.
|
g*****i 发帖数: 19 | 10 根据矩阵D的信息,确实没法确定。 只能对所有的组合,再scan给定的数组找来排除。
时间复杂度可能大点, 不知是否有更好的办法,谢谢楼上的提醒。
【在 n*******t 的大作中提到】 : suppose we finally find the missing digits are 1 and 2 for 10^0, and 3 : and 4 for 10^1. The missing numbers should be 13 and 24, or 14 and 23? : : of one digital from (0,1,2 ...9) in 10^0, 10^1, 10^2 .... 10^9 : respectivly, : all numbers from 0 ~ 4G are scaned. when a number is read, update the : respective cells. for : counted down one, D[5][0] to D[9][0] also. : the inforation in the matrix D, simatanously update D untill all cell : is 0.
|
|
|
b****u 发帖数: 16 | 11 640*8=5120 bits
把0到4G分成长度为5120个数的小段,如[0-5119],[5120,10239],...
对每个小段扫描一遍集合,输入小段中不存在的数。复杂度是O(4G*4G/5120)。 |
s*****y 发帖数: 897 | 12 How about the number 4000 is missed in the first segment, but appear in the
second segment?
【在 b****u 的大作中提到】 : 640*8=5120 bits : 把0到4G分成长度为5120个数的小段,如[0-5119],[5120,10239],... : 对每个小段扫描一遍集合,输入小段中不存在的数。复杂度是O(4G*4G/5120)。
|
b****u 发帖数: 16 | 13
the
你没看懂我的意思,算法写出来比较清楚
for i = 0 ... 4g/5120
do
start = i*5120
end = (i+1)*5120-1
memset(memory, 5120, 0)
for each number j in the 4g set
do
if start <= j <= end
then
memory[j-start] = 1
fi
done
for k = 0 ... 5120
do
if memory[k] == 0 && k+start <= 4g
then
print k+start
fi
done
done
【在 s*****y 的大作中提到】 : How about the number 4000 is missed in the first segment, but appear in the : second segment?
|
b****u 发帖数: 16 | 14 careercup上的解法比较快,请忽略我的解法 |
m**q 发帖数: 189 | 15 Careercup上的题目 11.3和这个题不一样:
- careercup上说明了文件中只有4billion个整数,小于2^32,
所以才能确定找到一个block包含missing的元素,这个在本题
中不适用啊。
- careercup上的方法只能找到一个missing,本题是要找所有
的missing。
我觉得你的解法没问题啊。如果题目允许用中间文件,可以把
原来的文件按范围分成5120大小的block,每个block一个文件,
然后按顺序依次把这些block load到内存里,这样只需要
扫描原文件两遍。
【在 b****u 的大作中提到】 : careercup上的解法比较快,请忽略我的解法
|
s*****y 发帖数: 897 | 16 我还是没有看懂啊
可否用C, C++ 或者java写啊。
我主要的问题是譬如你有好几个block
假设第一个block miss了 2,18,19
2 在block 23出现
18在 block 40出现
19在block 51出现
那么你跑完一个block后以为丢的数还会在后面找回来啊。
thanks
【在 b****u 的大作中提到】 : careercup上的解法比较快,请忽略我的解法
|
k*******p 发帖数: 219 | 17 这个解法要求这4g的数字是排序的吧。
【在 b****u 的大作中提到】 : careercup上的解法比较快,请忽略我的解法
|
s*****y 发帖数: 897 | 18 我看着也觉得是排好序的
【在 k*******p 的大作中提到】 : 这个解法要求这4g的数字是排序的吧。
|
g***s 发帖数: 3811 | 19 if you need time O(4G*4G/5120),
if (N < 4G)
why not sort them O(N * log N)
if (N >= 4G), then we can use swap to get O(N) algorithm.
【在 b****u 的大作中提到】 : 640*8=5120 bits : 把0到4G分成长度为5120个数的小段,如[0-5119],[5120,10239],... : 对每个小段扫描一遍集合,输入小段中不存在的数。复杂度是O(4G*4G/5120)。
|
m**q 发帖数: 189 | 20 Could you explain a bit more on the O(N) algorithm
based on swap when N >= 4G?
O(4G)?
【在 g***s 的大作中提到】 : if you need time O(4G*4G/5120), : if (N < 4G) : why not sort them O(N * log N): if (N >= 4G), then we can use swap to get O(N) algorithm.
|
|
|
c********0 发帖数: 112 | 21 有个trick是
从头scan碰到n就换到第n个位置
有点像radix sort
之后再scan 第n个数不是n就是miss的
【在 m**q 的大作中提到】 : Could you explain a bit more on the O(N) algorithm : based on swap when N >= 4G? : : O(4G)?
|
g***s 发帖数: 3811 | 22 yes.
不过,前提是这n个数字都在内存里面。
如果这题这n个数是在文件里,只让一个一个读,那就不行了。
如果是在内存里面(这内存也要够大啊,4G×4bytes=16G),因为是找missing,N好歹
有2G以上
吧?(否则一办以上都missing,不太合理)
那用这个方法走两遍(保持到前面2G的空间里面)。第一遍找2G以内的,第二遍找大于
2G的。也
是O(n)的时间。
【在 c********0 的大作中提到】 : 有个trick是 : 从头scan碰到n就换到第n个位置 : 有点像radix sort : 之后再scan 第n个数不是n就是miss的
|
m**q 发帖数: 189 | 23 哦,多谢...是把A[n]放到位置n的那个方法吧,内存足够的
话是个好主意啊
这个题目里内存只有640B,现在我想到的只有external sort
或者用区间划分,不知道还有什么更好的方法不
【在 g***s 的大作中提到】 : yes. : 不过,前提是这n个数字都在内存里面。 : 如果这题这n个数是在文件里,只让一个一个读,那就不行了。 : 如果是在内存里面(这内存也要够大啊,4G×4bytes=16G),因为是找missing,N好歹 : 有2G以上 : 吧?(否则一办以上都missing,不太合理) : 那用这个方法走两遍(保持到前面2G的空间里面)。第一遍找2G以内的,第二遍找大于 : 2G的。也 : 是O(n)的时间。
|
g*****i 发帖数: 19 | 24 这题最好给出数组大概大小,是否有重复元素。
【在 C***n 的大作中提到】 : given a set of numbers randing from 0 to 4G, : also a memory of 640 bytes : how to find the numbers between 0 to 4G that are not in the set? : with 640 bytes of memeory, how could we find those absent numbers out?
|