Him53
BAN USER- 0of 0 votes
AnswersGiven a list, L, of size k. L contains elements between 1 and n. Also given a function RND() such that this function returns a number between 1 and INT_MAX.
- Him53 in India
Now generate number between 1 and n, using RND(), such that the element should not be there in the list L. All elements should have a uniform probability.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
O(N) solution:
Map this problem to the following one
An array of size (= length of circular track) exists with all values 0 except the indices where fuel pits are there. The indices where fuel pits exist have values = amount of fuel that can be refilled from there.
Circular track => You can move across the array and after the final index return back to 0th index.
1. find the first fuel pit in the array. Assign this value to a variable say amountOfFuel.
2. As you move across the array (in a circular fashion), keep decrementing the value of amountOfFuel and if you encounter another fuel pit(another index with non-zero value), add the value to the variable. If you reach back at the starting point after a circular trip, voila!!
3. if you run out of fuel, then the fuel pits, that you have encountered till now, won't be the starting points obviously. So you again move forward until you find the next fuel pit and restart from point 1.
In case you have crossed one circle and still don't find a starting point.
Do the above again in the opposite direction.
Hope that helps
I think you mean, set k such that (n-k) divides INT_MAX into equal partitions.
Under this condition, the problem is trivial, ofcourse.
So the problem boils down to -
we have an RND() function that gives a random number from 1 to n and we have to find a random number from 1 to k using this function, such that all numbers from 1 to k have equal probability.
There is no relation between n and k
Even I thought of this first.
But will RND()%(n-k) + 1 really generate a random number from 1 to (n-k).
For the sake of discussion, suppose INT_MAX = 50 and n-k = 30.
then C = RND(50) % 30 + 1.
if RND(50) gives numbers 1 to 30, then it will remain same but if it gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20, which means probability of getting numbers 1 to 20 is more than the probability for 21 to 30. Hence it doesn't generate a random no. from 1 to 30.
Also somehow, if we create a function to give a random no. from 1 to n-k, can you please elaborate on your logic in 3rd step.
Seems wrong to me!
Suppose, your S is numbers 1 to 5. So f() gives a random number between 1 to 5. If you want a random number from 1 to 7, according to your logic, you will multiply 1.4 to f() to generate a random number from 1 to 7. Suppose you are using a floor function to map the decimal values to integers, then following will happen
- Him53 January 26, 20121.4 -> 1 -> p = 1/5
2.8 -> 2 -> p = 1/5
4.2 -> 4 -> p = 1/5
5.6 -> 5 -> p = 1/5
7.0 -> 7 -> p = 1/5
So out of the numbers 1 to 7, numbers 1, 2, 4, 5, 7 will be generated with probability 1/5 each and numbers 3, 6 won't be generated at all.
I hope this explanation suffices.