liangzhongliang
BAN USER
Comments (4)
Reputation 130
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
But seems that it said no excessive space can be used, and no hash. Using a map violated both requirements...
- liangzhongliang March 01, 2012Comment hidden because of low score. Click to expand.
0
of 0 vote
But seems that it said no excessive space can be used, and no hash. Using a map violated both requirements...
- liangzhongliang March 01, 2012Comment hidden because of low score. Click to expand.
0
of 0 vote
since RND() generate uniform distribution from 1 to INT_MAX, and we want uniform distribution from 1 to n, just normalize it:
int x = floor( (double) RND() / (double )INT_MAX * (double) n ); // floor is find largest int smaller than argument
now search through the list if x is in list, regenerate another number till it's not in the list, return x.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
I think the key point here is that the stream is of *infinite* length.
- liangzhongliang March 26, 2012Any solution that keeps track of all bits or their summation or in any other form would cause overflow problems.
The solution needs some number theory to prevent keeping info of all incoming bits. The right way to do this is to only keep the REMAINDER.
Notice the truth that X%3 and X have the same remainder, when divided by 3. So having X%3 is enough to decide whether X is divisible by 3.
When new bit comes, multiply the remainder by 2 (if bit is 0) or *2+1 (if bit is 1). Then repeat the procedures of keeping remainders.