Deshaw Inc Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
@alex , u misunderstand the Q ... like me, i will tell u complete Q
write a function to generate random value for array index with satisfying given conditions.
condition:
1)Every index should be select "C" times
"C" is the value that is filled in array in all indexes.
Given
1) array with size "n" , having filled with constant value "c" in each index.
2) randomGenFromMToN() will give random number from m to n;
Do you require uniform distribution at the start?
After every deletion ?
Also,
rand(b)%a+rand(b-a) <=== off by one error?
Also, the above might not be very uniform (it is close to uniform if and only if the length of the sequence given by rand() is "long" relative to the b-a ... assuming the C type rand() ).
The question as stated is not clear. After all numbers are are deleted , then what do your function return?
If I understand the problem, the array exists for tracking the resource count. When a slot in the array drops to zero, that index can't be used again.
So performance becomes the issue as more as more slots drop to zero. Finding an entry in the array that contains a count > 0 gets hard and harder.
So searching for that last entry in the array with the value 1 could turn into a linear search...unless you come up with a better solution.
If the range is a to b, then generate a random no as
- alex October 20, 2013r=rand(b)%a+rand(b-a)
maintain a hash table to check that the no of times the value has been returned is less than n. Maintain the no as key and count as value.
So, if(count(r)<=arr[r]){
count(r)++;
return r;
}