c*n
2 楼
常见的。 为严谨起见我逐字抄下来
given a sequential file that contains ____ at most four billion 32-bit
integers -_____ in random order, find a 32-bit integer that isn't in the
file
简单的办法，如果有4G内存， 就做一个bitmap 可以找到。 书里讨论如果只有几百
byte内存， 但可以写文件， 怎么弄。
下面剧透。
书上说，把要找的range 分两半 ， scan 过整个文件，看每一个range 里有多少， 肯
定有一个range 不够满，那就继续找那个range, 这样range 指数变小，最后为size 1,
就是要找的missing number.
我开始理解错，以为是有N numbers,N>2^32, but only 2^32-m of them are
distinct, where 1<=m < 2^32. 这样的话对每个小range 计数就不能认定是否有
missing number. 比如
input is
[0, 1 , 3 ]
(assume input range is 2^2 instead of 2^32 )
最开始range 是0--3
先在 0--1 range 找， 有两个数 （0，1）， 再去2--3 找， 有一个数， range 就变
为2--3
然后找到2 missing.
如果是说条件只是限制unique numbers, 总数不管， 那sample input 变成
[0,1,3,3]
这样两个sub range 都有足够的数，就不行了。
用前面bitmap , 新的条件也可以解， 但binary search 的思路办法似乎就不成了。
given a sequential file that contains ____ at most four billion 32-bit
integers -_____ in random order, find a 32-bit integer that isn't in the
file
简单的办法，如果有4G内存， 就做一个bitmap 可以找到。 书里讨论如果只有几百
byte内存， 但可以写文件， 怎么弄。
下面剧透。
书上说，把要找的range 分两半 ， scan 过整个文件，看每一个range 里有多少， 肯
定有一个range 不够满，那就继续找那个range, 这样range 指数变小，最后为size 1,
就是要找的missing number.
我开始理解错，以为是有N numbers,N>2^32, but only 2^32-m of them are
distinct, where 1<=m < 2^32. 这样的话对每个小range 计数就不能认定是否有
missing number. 比如
input is
[0, 1 , 3 ]
(assume input range is 2^2 instead of 2^32 )
最开始range 是0--3
先在 0--1 range 找， 有两个数 （0，1）， 再去2--3 找， 有一个数， range 就变
为2--3
然后找到2 missing.
如果是说条件只是限制unique numbers, 总数不管， 那sample input 变成
[0,1,3,3]
这样两个sub range 都有足够的数，就不行了。
用前面bitmap , 新的条件也可以解， 但binary search 的思路办法似乎就不成了。
l*o
3 楼
【 以下文字转载自 Military 讨论区 】
发信人: liangmaomao (Amy Bishop 拿不到tenure就杀人的生物AP), 信区: Military
标 题: 中共国奇巴用语何时休：剥夺政治权利XX年
发信站: BBS 未名空间站 (Wed May 28 01:31:24 2014, 美东)
还有剥夺政治权利终身,多在宣判时同判处有期（无期）徒刑一起使用。
Where does it come from? Who gives it a shit?
发信人: liangmaomao (Amy Bishop 拿不到tenure就杀人的生物AP), 信区: Military
标 题: 中共国奇巴用语何时休：剥夺政治权利XX年
发信站: BBS 未名空间站 (Wed May 28 01:31:24 2014, 美东)
还有剥夺政治权利终身,多在宣判时同判处有期（无期）徒刑一起使用。
Where does it come from? Who gives it a shit?
s*l
4 楼
还支持iphone了，哈哈
【在 n****Z 的大作中提到】
: 在办公室里直接浏览器上lava太惹人耳目了，在outlook里看RSS feed就好多了，人家
: 以为我在看信
【在 n****Z 的大作中提到】
: 在办公室里直接浏览器上lava太惹人耳目了，在outlook里看RSS feed就好多了，人家
: 以为我在看信
h*c
5 楼
算连续数的sha1，n^2
a*e
6 楼
禁止杀人犯出书介绍杀人经验你也有意见？
Military
★ 发自iPhone App: ChineseWeb 8.7
【在 l*********o 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: liangmaomao (Amy Bishop 拿不到tenure就杀人的生物AP), 信区: Military
: 标 题: 中共国奇巴用语何时休：剥夺政治权利XX年
: 发信站: BBS 未名空间站 (Wed May 28 01:31:24 2014, 美东)
: 还有剥夺政治权利终身,多在宣判时同判处有期（无期）徒刑一起使用。
: Where does it come from? Who gives it a shit?
Military
★ 发自iPhone App: ChineseWeb 8.7
【在 l*********o 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: liangmaomao (Amy Bishop 拿不到tenure就杀人的生物AP), 信区: Military
: 标 题: 中共国奇巴用语何时休：剥夺政治权利XX年
: 发信站: BBS 未名空间站 (Wed May 28 01:31:24 2014, 美东)
: 还有剥夺政治权利终身,多在宣判时同判处有期（无期）徒刑一起使用。
: Where does it come from? Who gives it a shit?
h*c
7 楼
n! mod \bigpi a_i equal to the missed number.
n! needs nlogn bits
n! needs nlogn bits
d*f
8 楼
不好意思你的美帝祖国很多州重罪犯也是不能投票的
Military
【在 l*********o 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: liangmaomao (Amy Bishop 拿不到tenure就杀人的生物AP), 信区: Military
: 标 题: 中共国奇巴用语何时休：剥夺政治权利XX年
: 发信站: BBS 未名空间站 (Wed May 28 01:31:24 2014, 美东)
: 还有剥夺政治权利终身,多在宣判时同判处有期（无期）徒刑一起使用。
: Where does it come from? Who gives it a shit?
Military
【在 l*********o 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: liangmaomao (Amy Bishop 拿不到tenure就杀人的生物AP), 信区: Military
: 标 题: 中共国奇巴用语何时休：剥夺政治权利XX年
: 发信站: BBS 未名空间站 (Wed May 28 01:31:24 2014, 美东)
: 还有剥夺政治权利终身,多在宣判时同判处有期（无期）徒刑一起使用。
: Where does it come from? Who gives it a shit?
c*n
9 楼
first of all mul and div are too slow
even if u agree to use mul and div, this method is still only as good as the
one given in the book, and can't handle duplicate numbers , which is the
further case I raised
【在 h**********c 的大作中提到】
: n! mod \bigpi a_i equal to the missed number.
: n! needs nlogn bits
even if u agree to use mul and div, this method is still only as good as the
one given in the book, and can't handle duplicate numbers , which is the
further case I raised
【在 h**********c 的大作中提到】
: n! mod \bigpi a_i equal to the missed number.
: n! needs nlogn bits
z*n
10 楼
有的是有期徒刑10年，剥夺政治权利三年，也就是，第四年就可以投票结社了？
【在 d********f 的大作中提到】
: 不好意思你的美帝祖国很多州重罪犯也是不能投票的
:
: Military
【在 d********f 的大作中提到】
: 不好意思你的美帝祖国很多州重罪犯也是不能投票的
:
: Military
c*n
11 楼
more details please ?
【在 h**********c 的大作中提到】
: 算连续数的sha1，n^2
【在 h**********c 的大作中提到】
: 算连续数的sha1，n^2
d*f
12 楼
理论上是，实践我不知道
【在 z*********n 的大作中提到】
: 有的是有期徒刑10年，剥夺政治权利三年，也就是，第四年就可以投票结社了？
【在 z*********n 的大作中提到】
: 有的是有期徒刑10年，剥夺政治权利三年，也就是，第四年就可以投票结社了？
h*c
13 楼
还没想清楚，先站个坑
不过假设你只有4k内寸，可以先捞1~k
没有missed，再捞k+1~8K
【在 c******n 的大作中提到】
: more details please ?
不过假设你只有4k内寸，可以先捞1~k
没有missed，再捞k+1~8K
【在 c******n 的大作中提到】
: more details please ?
i*g
14 楼
天朝屁民没有投票结社自由，不过可以劫色了
【在 z*********n 的大作中提到】
: 有的是有期徒刑10年，剥夺政治权利三年，也就是，第四年就可以投票结社了？
【在 z*********n 的大作中提到】
: 有的是有期徒刑10年，剥夺政治权利三年，也就是，第四年就可以投票结社了？
c*n
15 楼
【在 h**********c 的大作中提到】
: 还没想清楚，先站个坑
: 不过假设你只有4k内寸，可以先捞1~k
: 没有missed，再捞k+1~8K
H*7
16 楼
不是，是10+3年
【在 z*********n 的大作中提到】
: 有的是有期徒刑10年，剥夺政治权利三年，也就是，第四年就可以投票结社了？
【在 z*********n 的大作中提到】
: 有的是有期徒刑10年，剥夺政治权利三年，也就是，第四年就可以投票结社了？
c*n
17 楼
就思路来说，这个办法肯定可以在面试上加分, 基本上就是“combine/hybrid
existing 2 approaches"， 但实际不work , 4B-->4K you have to chop the input
file into 1mil small files and do in-memory search for 1mil times.
【在 h**********c 的大作中提到】
: 还没想清楚，先站个坑
: 不过假设你只有4k内寸，可以先捞1~k
: 没有missed，再捞k+1~8K
existing 2 approaches"， 但实际不work , 4B-->4K you have to chop the input
file into 1mil small files and do in-memory search for 1mil times.
【在 h**********c 的大作中提到】
: 还没想清楚，先站个坑
: 不过假设你只有4k内寸，可以先捞1~k
: 没有missed，再捞k+1~8K
d*f
18 楼
胡说八道。监狱里面是有投票箱的。不过我党从来不点
【在 H******7 的大作中提到】
: 不是，是10+3年
【在 H******7 的大作中提到】
: 不是，是10+3年
c*n
19 楼
常见的。 为严谨起见我逐字抄下来
given a sequential file that contains ____ at most four billion 32-bit
integers -_____ in random order, find a 32-bit integer that isn't in the
file
简单的办法，如果有4G内存， 就做一个bitmap 可以找到。 书里讨论如果只有几百
byte内存， 但可以写文件， 怎么弄。
下面剧透。
书上说，把要找的range 分两半 ， scan 过整个文件，看每一个range 里有多少， 肯
定有一个range 不够满，那就继续找那个range, 这样range 指数变小，最后为size 1,
就是要找的missing number.
我开始理解错，以为是有N numbers,N>2^32, but only 2^32-m of them are
distinct, where 1<=m < 2^32. 这样的话对每个小range 计数就不能认定是否有
missing number. 比如
input is
[0, 1 , 3 ]
(assume input range is 2^2 instead of 2^32 )
最开始range 是0--3
先在 0--1 range 找， 有两个数 （0，1）， 再去2--3 找， 有一个数， range 就变
为2--3
然后找到2 missing.
如果是说条件只是限制unique numbers, 总数不管， 那sample input 变成
[0,1,3,3]
这样两个sub range 都有足够的数，就不行了。
用前面bitmap , 新的条件也可以解， 但binary search 的思路办法似乎就不成了。
given a sequential file that contains ____ at most four billion 32-bit
integers -_____ in random order, find a 32-bit integer that isn't in the
file
简单的办法，如果有4G内存， 就做一个bitmap 可以找到。 书里讨论如果只有几百
byte内存， 但可以写文件， 怎么弄。
下面剧透。
书上说，把要找的range 分两半 ， scan 过整个文件，看每一个range 里有多少， 肯
定有一个range 不够满，那就继续找那个range, 这样range 指数变小，最后为size 1,
就是要找的missing number.
我开始理解错，以为是有N numbers,N>2^32, but only 2^32-m of them are
distinct, where 1<=m < 2^32. 这样的话对每个小range 计数就不能认定是否有
missing number. 比如
input is
[0, 1 , 3 ]
(assume input range is 2^2 instead of 2^32 )
最开始range 是0--3
先在 0--1 range 找， 有两个数 （0，1）， 再去2--3 找， 有一个数， range 就变
为2--3
然后找到2 missing.
如果是说条件只是限制unique numbers, 总数不管， 那sample input 变成
[0,1,3,3]
这样两个sub range 都有足够的数，就不行了。
用前面bitmap , 新的条件也可以解， 但binary search 的思路办法似乎就不成了。
b*e
20 楼
没有吧，万米吃牢饭能投票不？
【在 d********f 的大作中提到】
: 胡说八道。监狱里面是有投票箱的。不过我党从来不点
【在 d********f 的大作中提到】
: 胡说八道。监狱里面是有投票箱的。不过我党从来不点
h*c
21 楼
算连续数的sha1，n^2
H*7
22 楼
if they were convicted on a misdemeanor, then yes, prisoners can vote.
But if they are convicted of a felony...
Maine and Vermont are the only states that allow felons to vote while in
prison.
Most states restore voting rights after the completion of parole. In some
states the voting right restoration is automatic, others require a process.
Thirteen states allow convicted felons to vote while on parole. This fall
Wisconsin is voting to decide whether they become the 14th state.
Alabama, Arizona, Florida, Nevada, and Tennessee allow some freed felons to
vote but not others, depending on the nature of their crime and/or once they
have paid all restitution and fines.
Iowa, Kentucky, Mississippi, and Virginia are the only states that do not
allow any felon to ever vote, even after completing parole.
【在 b*****e 的大作中提到】
: 没有吧，万米吃牢饭能投票不？
But if they are convicted of a felony...
Maine and Vermont are the only states that allow felons to vote while in
prison.
Most states restore voting rights after the completion of parole. In some
states the voting right restoration is automatic, others require a process.
Thirteen states allow convicted felons to vote while on parole. This fall
Wisconsin is voting to decide whether they become the 14th state.
Alabama, Arizona, Florida, Nevada, and Tennessee allow some freed felons to
vote but not others, depending on the nature of their crime and/or once they
have paid all restitution and fines.
Iowa, Kentucky, Mississippi, and Virginia are the only states that do not
allow any felon to ever vote, even after completing parole.
【在 b*****e 的大作中提到】
: 没有吧，万米吃牢饭能投票不？
h*c
23 楼
n! mod \bigpi a_i equal to the missed number.
n! needs nlogn bits
n! needs nlogn bits
d*f
24 楼
Prisoners[edit]
See also: Felony disenfranchisement
Prisoner voting rights are a state issue, so the laws are different from
state to state. Some states allow only individuals on probation. Others
allow individuals on parole and probation. As of 2011, only two states,
Kentucky and Virginia, continue to impose a lifelong denial of the right to
vote to all citizens with a felony record, absent a restoration of rights
granted by the Governor or state legislature.[33] However, in Kentucky, a
felon's rights can now be restored after the completion of a restoration
process to regain civil rights.[33] In 2007, Florida moved to restore voting
rights to convicted felons. In March 2011, however, Governor Rick Scott
reversed the 2007 reforms, making Florida the state with the most punitive
law in terms of disenfranchising citizens with past felony convictions.[34]
In July 2005, Iowa Governor Tom Vilsack issued an executive order restoring
the right to vote for all persons who have completed supervision.[33] On
October 31, 2005, Iowa's Supreme Court upheld mass re-enfranchisement of
convicted felons. Nine other states disenfranchise felons for various
lengths of time following the completion of their probation or parole. Other
than Maine and Vermont, all U.S. states prohibit felons from voting while
they are in prison.[35] In Puerto Rico, felons in prison are allowed to vote
in elections. This is in sharp contrast to European nations, like Norway,
which allow felons to vote after serving sentences and in some cases[36]
allow prisoners to vote. Prisoners have been allowed to vote in Canada since
2002.[37]
The United States has a higher proportion of its population in prison than
any other Western nation,[38] and more than Russia or China.[39] The
dramatic rise in the rate of incarceration in the United States, a 500%
increase from the 1970s to the 1990s[40] due to criminalization of certain
behaviors, strict sentencing guidelines and changes in philosophy[citation
needed], has vastly increased the number of people disfranchised because of
the felon provisions. According to the Sentencing Project, as of 2010 an
estimated 5.9 million Americans are denied the right to vote because of a
felony conviction, a number equivalent to 2.5% of the U.S. voting-age
population and a sharp increase from the 1.2 million people affected by
felony disenfranchisement in 1976.[41] Given the prison populations, the
effects have been most disadvantageous for minority and poor communities.[42]
.
to
they
【在 H******7 的大作中提到】
: if they were convicted on a misdemeanor, then yes, prisoners can vote.
: But if they are convicted of a felony...
: Maine and Vermont are the only states that allow felons to vote while in
: prison.
: Most states restore voting rights after the completion of parole. In some
: states the voting right restoration is automatic, others require a process.
: Thirteen states allow convicted felons to vote while on parole. This fall
: Wisconsin is voting to decide whether they become the 14th state.
: Alabama, Arizona, Florida, Nevada, and Tennessee allow some freed felons to
: vote but not others, depending on the nature of their crime and/or once they
See also: Felony disenfranchisement
Prisoner voting rights are a state issue, so the laws are different from
state to state. Some states allow only individuals on probation. Others
allow individuals on parole and probation. As of 2011, only two states,
Kentucky and Virginia, continue to impose a lifelong denial of the right to
vote to all citizens with a felony record, absent a restoration of rights
granted by the Governor or state legislature.[33] However, in Kentucky, a
felon's rights can now be restored after the completion of a restoration
process to regain civil rights.[33] In 2007, Florida moved to restore voting
rights to convicted felons. In March 2011, however, Governor Rick Scott
reversed the 2007 reforms, making Florida the state with the most punitive
law in terms of disenfranchising citizens with past felony convictions.[34]
In July 2005, Iowa Governor Tom Vilsack issued an executive order restoring
the right to vote for all persons who have completed supervision.[33] On
October 31, 2005, Iowa's Supreme Court upheld mass re-enfranchisement of
convicted felons. Nine other states disenfranchise felons for various
lengths of time following the completion of their probation or parole. Other
than Maine and Vermont, all U.S. states prohibit felons from voting while
they are in prison.[35] In Puerto Rico, felons in prison are allowed to vote
in elections. This is in sharp contrast to European nations, like Norway,
which allow felons to vote after serving sentences and in some cases[36]
allow prisoners to vote. Prisoners have been allowed to vote in Canada since
2002.[37]
The United States has a higher proportion of its population in prison than
any other Western nation,[38] and more than Russia or China.[39] The
dramatic rise in the rate of incarceration in the United States, a 500%
increase from the 1970s to the 1990s[40] due to criminalization of certain
behaviors, strict sentencing guidelines and changes in philosophy[citation
needed], has vastly increased the number of people disfranchised because of
the felon provisions. According to the Sentencing Project, as of 2010 an
estimated 5.9 million Americans are denied the right to vote because of a
felony conviction, a number equivalent to 2.5% of the U.S. voting-age
population and a sharp increase from the 1.2 million people affected by
felony disenfranchisement in 1976.[41] Given the prison populations, the
effects have been most disadvantageous for minority and poor communities.[42]
.
to
they
【在 H******7 的大作中提到】
: if they were convicted on a misdemeanor, then yes, prisoners can vote.
: But if they are convicted of a felony...
: Maine and Vermont are the only states that allow felons to vote while in
: prison.
: Most states restore voting rights after the completion of parole. In some
: states the voting right restoration is automatic, others require a process.
: Thirteen states allow convicted felons to vote while on parole. This fall
: Wisconsin is voting to decide whether they become the 14th state.
: Alabama, Arizona, Florida, Nevada, and Tennessee allow some freed felons to
: vote but not others, depending on the nature of their crime and/or once they
c*n
25 楼
first of all mul and div are too slow
even if u agree to use mul and div, this method is still only as good as the
one given in the book, and can't handle duplicate numbers , which is the
further case I raised
【在 h**********c 的大作中提到】
: n! mod \bigpi a_i equal to the missed number.
: n! needs nlogn bits
even if u agree to use mul and div, this method is still only as good as the
one given in the book, and can't handle duplicate numbers , which is the
further case I raised
【在 h**********c 的大作中提到】
: n! mod \bigpi a_i equal to the missed number.
: n! needs nlogn bits
z*n
26 楼
楼上两位知识真渊博
to
voting
【在 d********f 的大作中提到】
: Prisoners[edit]
: See also: Felony disenfranchisement
: Prisoner voting rights are a state issue, so the laws are different from
: state to state. Some states allow only individuals on probation. Others
: allow individuals on parole and probation. As of 2011, only two states,
: Kentucky and Virginia, continue to impose a lifelong denial of the right to
: vote to all citizens with a felony record, absent a restoration of rights
: granted by the Governor or state legislature.[33] However, in Kentucky, a
: felon's rights can now be restored after the completion of a restoration
: process to regain civil rights.[33] In 2007, Florida moved to restore voting
to
voting
【在 d********f 的大作中提到】
: Prisoners[edit]
: See also: Felony disenfranchisement
: Prisoner voting rights are a state issue, so the laws are different from
: state to state. Some states allow only individuals on probation. Others
: allow individuals on parole and probation. As of 2011, only two states,
: Kentucky and Virginia, continue to impose a lifelong denial of the right to
: vote to all citizens with a felony record, absent a restoration of rights
: granted by the Governor or state legislature.[33] However, in Kentucky, a
: felon's rights can now be restored after the completion of a restoration
: process to regain civil rights.[33] In 2007, Florida moved to restore voting
c*n
27 楼
more details please ?
【在 h**********c 的大作中提到】
: 算连续数的sha1，n^2
【在 h**********c 的大作中提到】
: 算连续数的sha1，n^2
d*f
28 楼
这个当然有，每年在押犯行使民主权利的时候中央台都会播的
【在 b*****e 的大作中提到】
: 没有吧，万米吃牢饭能投票不？
【在 b*****e 的大作中提到】
: 没有吧，万米吃牢饭能投票不？
h*c
29 楼
还没想清楚，先站个坑
不过假设你只有4k内寸，可以先捞1~k
没有missed，再捞k+1~8K
【在 c******n 的大作中提到】
: more details please ?
不过假设你只有4k内寸，可以先捞1~k
没有missed，再捞k+1~8K
【在 c******n 的大作中提到】
: more details please ?
H*7
30 楼
天草的剥夺“政治权利”主要是出书的权利和（万一）当人大代表（候选人）的权利，
其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
c*n
31 楼
【在 h**********c 的大作中提到】
: 还没想清楚，先站个坑
: 不过假设你只有4k内寸，可以先捞1~k
: 没有missed，再捞k+1~8K
z*n
32 楼
宪法规定公民有投票结社示威的自由的
【在 H******7 的大作中提到】
: 天草的剥夺“政治权利”主要是出书的权利和（万一）当人大代表（候选人）的权利，
: 其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
【在 H******7 的大作中提到】
: 天草的剥夺“政治权利”主要是出书的权利和（万一）当人大代表（候选人）的权利，
: 其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
c*n
33 楼
就思路来说，这个办法肯定可以在面试上加分, 基本上就是“combine/hybrid
existing 2 approaches"， 但实际不work , 4B-->4K you have to chop the input
file into 1mil small files and do in-memory search for 1mil times.
【在 h**********c 的大作中提到】
: 还没想清楚，先站个坑
: 不过假设你只有4k内寸，可以先捞1~k
: 没有missed，再捞k+1~8K
existing 2 approaches"， 但实际不work , 4B-->4K you have to chop the input
file into 1mil small files and do in-memory search for 1mil times.
【在 h**********c 的大作中提到】
: 还没想清楚，先站个坑
: 不过假设你只有4k内寸，可以先捞1~k
: 没有missed，再捞k+1~8K
i*g
34 楼
天朝出版社都是共产党开的，屁民出书过不了出版社这一关，没有出版自由
全国人大:以独立候选人参选人大代表无法律依据
屁民也没有参选人大代表的自由
【在 H******7 的大作中提到】
: 天草的剥夺“政治权利”主要是出书的权利和（万一）当人大代表（候选人）的权利，
: 其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
全国人大:以独立候选人参选人大代表无法律依据
屁民也没有参选人大代表的自由
【在 H******7 的大作中提到】
: 天草的剥夺“政治权利”主要是出书的权利和（万一）当人大代表（候选人）的权利，
: 其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
h*c
35 楼
Took some time think over this and I made an assumption, suppose there is no
repeating numbers. So we want to find the single missing number ranging
from 0 to 2^32-1 unsinged integers in a random sequence.
First, need background of unique factorial theorem.
Second, search prime numbers 32 bit in Internet, you will find we have total
about 200,xxx,xxx prime numbers in this scope.
Here is the deal.
suppose we have a_1 ... a_m prime numbers. a_1*...*a_m is the ceiling of 2^
32 -1 with any extra prime number needed. I think the count of a_1 to a_m
will be far less than 200,xxx,xxx. Think over it?
So put a_1 and a_m in a hashmap. The value will be the count of given prime
number.
From 0 to 2^32-1 - 1, the hashmap above will have a unique sequence.
Then we process the input, factor each number in the input data. Count the
presence of each prime number (add to the according value in the hashmap).
We will detect the prime numbers fail to present, compare to an total
sequence of 0 to 2^32-1. Their multiple is the single missed numbers.
If there are multiple missed numbers, we can use a second pass, use the
different combinations of the missed primes, screening the input data again.
So it will be good the OS has a local prime table.
Just for discussion for potential improvement of the situation. Please feel
free to comment. Thank off irrelevants!
MIT License.
1,
【在 c******n 的大作中提到】
: 常见的。 为严谨起见我逐字抄下来
: given a sequential file that contains ____ at most four billion 32-bit
: integers -_____ in random order, find a 32-bit integer that isn't in the
: file
: 简单的办法，如果有4G内存， 就做一个bitmap 可以找到。 书里讨论如果只有几百
: byte内存， 但可以写文件， 怎么弄。
: 下面剧透。
: 书上说，把要找的range 分两半 ， scan 过整个文件，看每一个range 里有多少， 肯
: 定有一个range 不够满，那就继续找那个range, 这样range 指数变小，最后为size 1,
: 就是要找的missing number.
repeating numbers. So we want to find the single missing number ranging
from 0 to 2^32-1 unsinged integers in a random sequence.
First, need background of unique factorial theorem.
Second, search prime numbers 32 bit in Internet, you will find we have total
about 200,xxx,xxx prime numbers in this scope.
Here is the deal.
suppose we have a_1 ... a_m prime numbers. a_1*...*a_m is the ceiling of 2^
32 -1 with any extra prime number needed. I think the count of a_1 to a_m
will be far less than 200,xxx,xxx. Think over it?
So put a_1 and a_m in a hashmap. The value will be the count of given prime
number.
From 0 to 2^32-1 - 1, the hashmap above will have a unique sequence.
Then we process the input, factor each number in the input data. Count the
presence of each prime number (add to the according value in the hashmap).
We will detect the prime numbers fail to present, compare to an total
sequence of 0 to 2^32-1. Their multiple is the single missed numbers.
If there are multiple missed numbers, we can use a second pass, use the
different combinations of the missed primes, screening the input data again.
So it will be good the OS has a local prime table.
Just for discussion for potential improvement of the situation. Please feel
free to comment. Thank off irrelevants!
MIT License.
1,
【在 c******n 的大作中提到】
: 常见的。 为严谨起见我逐字抄下来
: given a sequential file that contains ____ at most four billion 32-bit
: integers -_____ in random order, find a 32-bit integer that isn't in the
: file
: 简单的办法，如果有4G内存， 就做一个bitmap 可以找到。 书里讨论如果只有几百
: byte内存， 但可以写文件， 怎么弄。
: 下面剧透。
: 书上说，把要找的range 分两半 ， scan 过整个文件，看每一个range 里有多少， 肯
: 定有一个range 不够满，那就继续找那个range, 这样range 指数变小，最后为size 1,
: 就是要找的missing number.
t*e
36 楼
宪法 is written on toilet paper.
【在 z*********n 的大作中提到】
: 宪法规定公民有投票结社示威的自由的
【在 z*********n 的大作中提到】
: 宪法规定公民有投票结社示威的自由的
j*3
37 楼
这书现在还有看的意义么？
H*7
38 楼
宪法还用一半篇幅写前言歌颂党的伟大呢
【在 z*********n 的大作中提到】
: 宪法规定公民有投票结社示威的自由的
【在 z*********n 的大作中提到】
: 宪法规定公民有投票结社示威的自由的
C*t
39 楼
Probably we can do in this way.
Build an array rec of length 32 which save the digit sum of all numbers.
for num in nums:
for i in range(32):
rec[i] += num>>i &1
if there is no missing number at all, then rec[i] == 2^31 for all i
if there is some missing numbers, check the first index i such that rec[i] <
2^31, then the missing number if of the form
XXXXXXXXXXXX 1 00000000
where digit 1 is located at the i-th place from the right.
We may repeat this process for 32 times.
Build an array rec of length 32 which save the digit sum of all numbers.
for num in nums:
for i in range(32):
rec[i] += num>>i &1
if there is no missing number at all, then rec[i] == 2^31 for all i
if there is some missing numbers, check the first index i such that rec[i] <
2^31, then the missing number if of the form
XXXXXXXXXXXX 1 00000000
where digit 1 is located at the i-th place from the right.
We may repeat this process for 32 times.
z*n
40 楼
写在宪法里，就很神圣
【在 H******7 的大作中提到】
: 宪法还用一半篇幅写前言歌颂党的伟大呢
【在 H******7 的大作中提到】
: 宪法还用一半篇幅写前言歌颂党的伟大呢
d*f
41 楼
你不要歪，现在说的是你胡乱释法的问题。有法不依是我国的政治传统，但是你不能因
此就胡乱解释。
【在 H******7 的大作中提到】
: 天草的剥夺“政治权利”主要是出书的权利和（万一）当人大代表（候选人）的权利，
: 其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
此就胡乱解释。
【在 H******7 的大作中提到】
: 天草的剥夺“政治权利”主要是出书的权利和（万一）当人大代表（候选人）的权利，
: 其他投票结社，示威啥的本来也没有，你无法剥夺人家没有的东西
r*9
42 楼
13年吧
【在 d********f 的大作中提到】
: 理论上是，实践我不知道
【在 d********f 的大作中提到】
: 理论上是，实践我不知道
r*9
43 楼
13年吧
【在 d********f 的大作中提到】
: 理论上是，实践我不知道
【在 d********f 的大作中提到】
: 理论上是，实践我不知道
v*s
44 楼
买得起书号，转法轮都能出。
独立候选人当选人大代表的现在一抓一大把吧，不过还没有能选到市一级的。
【在 i*********g 的大作中提到】
: 天朝出版社都是共产党开的，屁民出书过不了出版社这一关，没有出版自由
: 全国人大:以独立候选人参选人大代表无法律依据
: 屁民也没有参选人大代表的自由
独立候选人当选人大代表的现在一抓一大把吧，不过还没有能选到市一级的。
【在 i*********g 的大作中提到】
: 天朝出版社都是共产党开的，屁民出书过不了出版社这一关，没有出版自由
: 全国人大:以独立候选人参选人大代表无法律依据
: 屁民也没有参选人大代表的自由
相关阅读
在外发生小争执 我妈上来就喊我女儿是北大的 (转载)伤心：老公看起来太年轻 (转载)我设想的防浪半潜船 (转载)健康版笑话76---zz印去年逾萬人死於鐵路 (转载)汤唯谈跨国婚姻：我嫁给外国人还挺勇敢的 (转载)好能吃的mm连处女怀孕的耶稣都有人信，信王林又有啥好奇怪？ (转载)男人没用了，女GAY可以直接生孩子了人造精子技术问世 (转载)你们都被王林骗了，明明是强生好不好 (转载)郭沫若全集第一卷，一些笑话Re: 丹佛干净个屁，全美重污染地区，colo springs一鬼城 (转载)北软为优化指明了一条新的道路 (转载)ps一下对照算造假吗？ (转载)俺家乡省重点高中学费5万了出差回来 (转载)IPHONE上的一件很可怕的怪事 (转载)女大学生到河南义务支教 刚下火车被骗6500元印度泼猴抢劫游客十几万卢比 撒向空中遭哄抢