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?
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?
【在 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?
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.
d*o
15 楼
哈哈,不就是那个女孩注重相貌的帖子嘛。
【在 c***z 的大作中提到】 : 完全插不上话。。。
p*j
16 楼
太震撼啦~真厉害!妮妮生日快乐~
C*n
17 楼
which one do you refer to?
CareerCup Top 150 Questions 中有。
【在 j***r 的大作中提到】 : CareerCup Top 150 Questions 中有。
c*z
18 楼
对阿,俺木有fashion细胞,当然更重要的是懒。。。
【在 d****o 的大作中提到】 : 哈哈,不就是那个女孩注重相貌的帖子嘛。
q*n
19 楼
祝宝宝生日快乐! 还有妈妈太赞了!
l*a
20 楼
system design and memory limit No.3 chapter 11 or 12
【在 C***n 的大作中提到】 : which one do you refer to? : : CareerCup Top 150 Questions 中有。
l*s
21 楼
妞妞生日快乐! 看着孩子就开心哈
g*i
22 楼
(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?
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.
【在 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.
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?
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***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?