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?
|
