Google Interview Question Software Engineer in Tests
Don't think this is correct at all. Let's consider this example:
K = [2, 3, 6, 9, 12, 17, 20, 21]
N = 30
r = rand (22) = 16
as there are 5 values in K < 16, r = 21
however, r is forbidden as it's K[7]
The ideia is to move 16 to the 16th slot on available numbers:
Available: [1, 4, 5, 7, 8, 10, 11, 13, 14, 15, 16, 18, 19, 22, 23, 24, 24, 26, 27, 28, 29, 30]
So r = 24 in this case.
It is important that k be in increasing order for this method to work. If you take a second look at the method, you will see that it isn't just incrementing r for each below it in k, it is incrementing based on its previous incrementend value.
So for the above situation, the iterations will be:
k[0] -> 16 > 2, so r = 17
k[1] -> 17 > 3, so r = 18
k[3] -> 18 > 6, so r = 19
k[4] -> 19 > 9, so r = 20
k[5] -> 20 > 12, so r = 21
k[6] -> 21 > 17, so r = 22
k[7] -> 22 > 20, so r = 23
k[8] -> 23 > 21, so r = 24
And just for the records i ran several tests on the code, generating milions of n, and milions of k, all of then random. Not even once the program selected a number in k, and it also distributed choosen values evenly among the valid results.
Thanks. I was hasty while looking at the procedure. Now, I think your proposed method can be used to reduce the time to O(log k) by using O(k) additional space. O(k) preprocessing would fill up the additional array count[], where count[i] stores number of forbidden values less than or equal to i-th forbidden value. Then binary search is used to get the proper mapping.
Thats a pretty good idea. I just implement and tested it:
I didnt used another array to store the count. Only preprocessed k doing:
1. for each k in i position, do k = k-1.
By doing that, each element with value greater or equal this new k, will be offset by the position of k (equals to the number of elements lower or equal r in k vector).
Space was O(k) and time O(logk) as you suggested.
import java.util.Random;
class KDistinct2 {
private int[] k;
private Random rand = new Random();
public KDistinct2(int[] k) {
this.k = k.clone();
for (int i=1; i<k.length; ++i) {
this.k[i] -= i;
}
}
public int rand(int n) {
int r = this.rand.nextInt(n-k.length);
return r + countLowerOrEqualThan(r);
}
private int countLowerOrEqualThan(int val) {
int l = 0, r = k.length-1;
while (l <= r) {
int m = (l+r)/2;
if (k[m] <= val && (m == (k.length-1) || k[m+1] > val))
return (m+1);
if (k[m] > val)
r = m-1;
else
l = m+1;
}
return 0;
}
}
@lucas.eustaquio
probability of generating random number can't be proven by running ur program 100 times.
in this case. if there are k distinct number already occupied.
then random number need to be generated using n-k numbers with each number probability as 1/(n-k)..
by compiling above program it looks like number are not getting generated with same probability.
e.g
if k number are 1,2,3,4,7,8;
and i need to generate number between 1 to 10.
using rand() of 10-6 = 4 numbers I generate suppose 1,2,3,4 any of these.
using ur program i will get 5 as answer each time. which is not random!!
but theoretically answer for these 4 should be
1=5
2=6
3=9
4=10
now question remains same how to generate these number without using extra space in <= O(log(k))
Take an array of size (N - k) and fill it with the numbers not in the subset. Then just pick arr[rand() % (N - k)].
Seems a little expensive on the memory side for large N. You can rand(N-k),a dn then find where that belongs in log(k) time.
why not anyone think of using set? put the known list in the set, random generate a number, test if it is in the list, if not output; otherwise try it again. It is the second solution to generate k random numbers in the book Programming Pearl second edition chapter 12. The other three solutions are Knuth, Floyd, Swap
The approach will vary based on whether the function would be called once or multiple times.
If it is called multiple times, then below approach may be good as amortized time complexity is reduced.
Here s one approach. Make a look up table[using bit vector] of the numbers present in the set.
Apply divide & conquer technique. generate a random number & look in the bit vector whether its already present. If not,return.
else, call recursively for 0 to k-1 & k+1 to N.
Let me know if there is any better approach.
class RandomPickWithBlacklist:
def __init__(self, N, blacklist):
self.map = {}
self.wLen = N - len(blacklist)
whiteList = set()
# Create a list of all whitelist numbers in [N − len(B), N)
for i in range(self.wLen, N):
whiteList.add(i)
# Iterate over the blacklist and remove the values
# from the whitelist
for i in blacklist:
if i in whiteList:
whiteList.remove(i)
# Now, iterate through all numbers in X, assigning M[X[i]] = W[i]
wi = iter(whiteList)
for i in blacklist:
if i < self.wLen:
self.map[i] = next(wi)
def pick(self):
randIdx = random.randrange(0, self.wLen)
return self.map.get(randIdx, randIdx)
1. Generate a number between [0, N-K]
2. For each k(sorted), checks if the generated number if >= k. If so, increment.
Doing this is the same as simulating holes where k numbers should be.
Time: O(k) (For a constant time solution use artakbegnazaryan advice.
- lucas.eustaquio August 02, 2011public class KDistinct { private int[] k; private Random rand = new Random(); public KDistinct(int[] k) { this.k = k; } public int rand1(int n) { int r = rand.nextInt(n-k.length); for (int f : k) { if (r >= f) ++r; else break; } return r; } }