## Google Interview Question

SDE1s**Country:**United States

**Interview Type:**Phone Interview

I'm not sure this solution works:

Take N=6, so that we have [1,2,3,4,5,6] as our range of valid numbers.

Take K=[1,2,3], so that K.length = 3

Suppose when drawing x uniformly from [1, N-K.length] (e.g., [1,3]) we draw a 1, so that x = 1.

First iteration: i=0, K[i]=1, x=1, last=0

(K[i]-last > x) = true, so we return x + last = 1

The return value 1 is in K. How can this be correct? Please let me know what I missed...

"(K[i]-last > x) = true"

No. x = 1, K[0] - last = 1 - 0 = 1 which is not > x. So the cycle will ignore all values in K and return 1 + K[2] = 1 + 3 = 4

What would happen if elements in K are larger than N? Then wouldn't the probability you're looking for be greater than N - k.length? Since some of the elements in k are not applicable.

"uniform()" is just a pseudo-code used by the author of the question. i just reused it. as the comment says, it generates a random number uniformly between 1 and X

The question is not entirely clear, but it doesn't make much sense if the elements in K would be greater than N. i think "probability of generated number should be 1/(N-K.length)" would be impossible

K is a sorted array that contains numbers from 0 to N. It seems to me (from Justin's example) that you are assuming K contains the first k numbers. That's wrong.

you misread my approach. that was just an example.

K should just contain numbers between 0 and N

My approach is as follow:

-Transform K such that K[i] = number of integers 0.. K[i] missing before K[i] in K[]

-Generate a random number x = uniform(0... N-K.length-1)

-Find y = number of numbers equal to or less than x in K[], using binary search.

-return x+y

Time = O(K.length) Space = O(1)

Working C code below

```
#include<stdio.h>
#include<stdlib.h>
int getIndexEqualOrLess(int K[], int kLen, int x);
int random(int N, int K[], int kLen)
{
//Generating x = uniform(0.. N-kLen-1)
srand(time(NULL));
int x = rand()%(N-kLen);
// transforming K such that K[i] = number of integers before K[i] in K
int i;
for(i=0; i<kLen; i++)
K[i] = K[i]-i;
//get numbers less than or equal to x in transfromed K
int y = getIndexEqualOrLess(K, kLen, x) + 1;
return x+y;
}
int getIndexEqualOrLess(int K[], int kLen, int x){
int start = 0, end = kLen, mid, ans = -1;
while(start<=end)
{
mid = (start + end)/2;
if(K[mid] == x){
while(mid+1 < kLen && K[mid+1] == x)
mid++;
return mid;
}
if(K[mid] > x)
end = mid-1;
else{
ans = mid;
start = mid+1;
}
}
return ans;
}
int main(){
int N = 10, K[] = {2, 3, 5, 8}, kLen=4;
printf("%d\n", random(N, K, kLen));
return 0;
}
```

You can make time complexity O(log(K.length)) if you skip the following loop:

```
// transforming K such that K[i] = number of integers before K[i] in K
int i;
for(i=0; i<kLen; i++)
K[i] = K[i]-i;
```

and replace all the array accesses in getIndexEqualOrLess (K[idx]) with (K[idx] - idx)

```
// time O(lg K.size()) & space O(1)
int getRandom(int N, vector<int> K) {
int pos = unique_random(0, N-K.size()) + 1; // [1, N-K.size() + 1)
if (pos < K[0]) {
return pos;
}
int l = 0, r = K.size();
while (l < r) {
int mid = (l + r) / 2;
if (K[mid] - mid < pos) {
l = mid + 1;
} else {
r = mid;
}
}
return pos + l - 1;
}
```

Sorry for indentation (I use GNU style, which mixedly use tab and space); and it should be vector<int> & instead of vector<int>

you might try binary search to identify if the randint(1,N) you flipped was in K[ ], and if it is... you...

TBH I don't really understand the question. To me it's underspecified.

I thought it meant probability is

1 / ( N - k ) where k is the number of elements of K[ ] in the range 1 ... N

But it says k=K.length.

even we assume the numbers in K[ ] are a subset of {1,...,N}

and then use uniform prob 1/(N-k) we should be fine.

But the questions has weird cases. Division by zero. K.length > N. And I don't even know what prob 1/(N-K.length) means in most cases.

from the example given in the question, what we want is to select one number in the interval [0, N) except the numbers in array K. Hence, there are N - K.length valid numbers.

Example: N = 10 and K = [2,3, 5, 8]. We should give a random number of the set [0, 1, 4, 6, 7, 10] with 1/6 probability

:) Your code is great and upvoted, but I have a problem with the question (and questioner).

It is not at clear what is to be returned.

It is not at clear what happens if N=2 and K=[6, 4.5, 2]

Or N=3, K=[1,2,3]

Or what "k is less than N" in the comments of his code mean.

Based on his question we can even get negative probabilities.

I'm assuming numbers between 1 and N.

Generate a random number X in the range 1..N-K.length. Then, process the K array while we haven't seen X numbers.

```
public int randomNumber(int N, int[] K) { // K is sorted
int x = uniform(N - K.length); // 1 .. N - K.length
int last = 0 , i;
for (i = 0; i < K.length; i++) {
if (K[i] - last >= x)
return x + last;
x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers
last = K[i];
}
return x + K[ K.length-1 ];
}
```

runtime O(K), O(1) space

I'm assuming numbers between 1 and N.

Generate a random number X in the range 1..N-K.length. Then, process the K array while we haven't seen X numbers.

public int randomNumber(int N, int[] K) { // K is sorted

int x = uniform(N - K.length); // 1 .. N - K.length

int last = 0 , i;

for (i = 0; i < K.length; i++) {

if (K[i] - last > x)

return x + last;

x -= (K[i] - last - 1); // we've seen K[i] - last - 1 valid numbers

last = K[i];

}

return x + K[ K.length-1 ];

}

runtime O(K), O(1) space

This problem is an extension of standard reservoir sampling

```
//assme 0<= A[i] <= N-1, -1 means all integers in [0,n-1] are in A.
int randomNum(int n, vector<int> A)
{
int retVal = -1;
int sampleSize = 0;
A.insert(A.begin(), 0);
for(int i=1; i<A.size(); i++)
{
if(A[i] >A[i-1]+1)
{
int interval = A[i] - A[i-1]-1;
sampleSize += interval;
int temp = 1+ rand()%sampleSize; // temp in [1, sampleSize]
if(temp <= interval) // pick a number in the interval [A[i-1]+1, A[i]-1] with prob. interval/sampleSize;
retVal = A[i-1] + temp;
}
return retVal;
}
}
```

I think the trick is to get random number in range [0, N - K.length()] and if the random number is present in K, then you add random number's position in K to N - K.length().

```
int GetRandom(int *K, int kLen, int N)
{
int rnd = rand() % (N - kLen);
int pos = Find(K, kLen, rnd); // Perform binary search and return index
return pos == -1? rnd: N - kLen + pos;
}
```

I think there exists cases where the above code produces invalid value:

Let N= 1, 2, 3, 4

and

K=1, 3, 4

Now, let assume that the randomly generated number is 1. Hence:

rnd=1%(4-3)=1

such that pos=0

This results in a return value to be 4-3+0=1. However, 1 is an element of K.

Please correct me if I am misinterpreting this solution.

```
public static int randomNumber(int N, int[] K) {
int length = K.length - 1;
while(K[length] > N){ //find actual length of K that matters to us (elements <= N)
length--;
}
int x = Random.nextInt(length) + 1; //get the xth number between 0 and N that's not in k
int place = 0;
int count = 0;
for (int i = 0; i < N; i++) {
if(i == K[place]){
place++;
} else {
count++;
}
if(count == x){
return i;
}
}
return x + K[ K.length-1 ];
}
```

This solution doesn't take into account the possibility of duplicates in K. We can handle that in the beginning like how I handled the case where there's elements greater than N.

This seems to have an error. Here is another solution, along similar lines.

public static int getRandom(int n, int[] k) {

int length = k.length;

while (length > 0 && k[length - 1] > n) {

length--;

}

if (length >= n) {

throw new IllegalArgumentException("Sample space of size 0");

}

int draw = new Random().nextInt(n - length);

System.out.println("draw=" + draw);

int current = -1;

int j = 0;

for (int i = 0; i <= draw; i++) {

current++;

while (j < length && k[j] < current) {

j++;

}

while (j < length && k[j] == current) {

current++;

j++;

}

}

return current;

}

I assume that each number in k is at most once, that size of k < n. The idea is to return the i-th allowed number where i is a random number in the interval 0, n - k.size().

```
int RandomNumber(const int &n, const std::vector<int> &k) {
int res = rand(n - k.size());
int index = 0;
while (index < k.size() && res >= k[index]) {
++res;
++index;
}
return res;
}
```

```
int getRandom( int n, int K[], int sz) {
int L = n - sz;
int c = rand() % L;
if (c < K[0])
return c;
for (int i = 0; i < sz; i++) {
int d = K[i] - K[i - 1];
if (d > 0 && c < d)
return K[i-1] + c + 1;
c -= d;
}
return K[sz - 1] + c + 1;
}
```

consider the following (in pseudo code):

```
1. index = 0;
2. Iterate over all the numbers [0,N) which are not in K:
2.1 probability = 1 / (N - K.size - index)
2.2 x = rand(0, 1)
2.3 if (x > probability) return current number
```

space: O(1) - no arrays

time: O(N) - because K is sorted, we can get all the numbers which are not in K by iterating on it, and find the missing numbers

Why does this works:

* Assume that N=10, K=[0,1,2,5,7,8] , N-K.size = 4

* We iterate over the numbers: 3,4,6,9

* Let's calculate the probability for returning the number 3 (the first one):

1/(N-K+index) = 1/4

* Let's calculate the prob for returning the number 4 (the second one):

We haven't returned 3 in the first round - the probability for that is: 3/4

We return the 4 in the second round: 1/(N-K-index) = 1/(10-6-1) = 1/3

Multiply the probs: 3/4 * 1/3 = 1/4 - same probability as the number 3

* You can continue with this method, and find out that all the numbers get the same probability

```
public static int getRandom(int n, int[] k) {
int length = k.length;
while (length > 0 && k[length - 1] > n) {
length--;
}
if (length >= n) {
throw new IllegalArgumentException("Sample space of size 0");
}
int draw = new Random().nextInt(n - length);
System.out.println("draw=" + draw);
int current = -1;
int j = 0;
for (int i = 0; i <= draw; i++) {
current++;
while (j < length && k[j] < current) {
j++;
}
while (j < length && k[j] == current) {
current++;
j++;
}
}
return current;
}
```

The main idea is to find the Xth number that not appear in the k array:

int getrandom(int N, int k[], int length)

{

int x = uniform(N - length), count = k[0] - 1;

for(int i = 0; i < length - 1; i++)

{

if(i == 0 && x <= count)

{

return x;

}

count += (k[i + 1] - k[i] - 1);

if(x <= count)

{

return k[i + 1] - (count - x + 1);

}

}

return k[length - 1] + x - count;

}

#include <iostream>

#include <fstream>

#include <vector>

#include <stdlib.h>

#include <time.h>

using namespace std;

int getRandom(int N, vector <int> K){

int L = N-K.size();

cout << L << endl;

int random_num = rand()%L;

cout << random_num << endl;

K.push_back(N);

int prv = 0 , i = 0 , sum = 0;

if ( random_num < K[0] ) return random_num;

while ( (i < K.size()) && (sum < random_num) ) {

sum += K[i]-prv-1;

prv = K[i];

i++;

}

i--;

return (K[i]-sum+random_num-1);

}

int main()

{

int N;

cin >> N;

vector <int> K;

int M;

cin >> M;

for ( int i = 0 ; i < M ; i++ ) {

int tmp;

cin >> tmp;

K.push_back(tmp);

}

cout << getRandom(N, K) << endl;

return 0;

}

Here is the simple java solution using binary search:

```
import java.util.Random;
public class Random {
public static void main(String[] args) {
int sortedArray[] = {2, 3, 5, 6, 7, 8, 9};
int random = getRandom(10, sortedArray);
System.out.println(random);
}
public static int getRandom(int key, int[] sortedArray){
int length = sortedArray.length;
int randomNumber = new Random().nextInt(sortedArray[length-1]);
System.out.println("randomNumber: "+randomNumber);
if(binarySearch(randomNumber, sortedArray) != -1){
randomNumber = getRandom(key, sortedArray);
}
return randomNumber;
}
public static int binarySearch(int key, int[] sortedArray){
int lo = 0;
int hi = sortedArray.length - 1;
while (lo <= hi) {
// Key is in sortedArray[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < sortedArray[mid]) hi = mid - 1;
else if (key > sortedArray[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
}
```

O(logK) time, O(1) space.

```
int getRandom(int N, int K[]){
int M = sizeof(K);
int ret = randon()%(N-M);
//to find the ret-th valid number
int L = 0, R = M-1, mid , pos = M;
while(L<=R){
mid = (L + R)/2;
if (K[mid]-mid >= ret){
pos = mid;
R = mid-1;
}else L = mid+1;
}
int back;
if (pos == M)
back = N-pos;
else back = K[pos]-pos;
back -= ret;
if (pos == M)
ret = N-1-back;
else ret = K[pos]-1-back;
return ret;
}
```

Solution:

Generate rnum = uniform(N) and then keep doing binary search till rnum does not belong in K. (python code)

```
def get_random(n, k)
rnum = random.randint(0, n)
def binsearch(l, target):
if not l:
return 0
mid = len(l)/2
if target == l[mid]:
return 1
if target > mid:
return binsearch(l[mid+1:], target)
else:
return binsearch(l[:mid], target)
while binsearch(k, rnum):
rnum = random.randint(0, n)
return rnum
```

We should return K[i]. Pr{K[i]} - probability return K[i].

Pr{K[0]} = Pr{K[1]} = ... = Pr{K[K.length - 1]} (from constraints).

But Pr{K[0]} + Pr{K[1]} + ... + Pr{K[K.length - 1]} = 1 (from probability theory)

So Pr{K[i]} = 1/N for i = 0..K.lenght - 1.

So the only valid N = 2*K.length.

Am I right? Or didn't understand the question?

No idea.

The way question is stated you can even make the computer cry by calling function with K[ ] which has length == K.length

from the example given in the question, what we want is to select one number in the interval [0, N) except the numbers in array K. Hence, there are N - K.length valid numbers.

Example: N = 10 and K = [2,3, 5, 8]. We should give a random number of the set [0, 1, 4, 6, 7, 10] with 1/6 probability

I'm assuming numbers between 1 and N.

Generate a random number X in the range 1..N-K.length. Then, process the K array while we haven't seen X numbers.

runtime O(K), O(1) space

- Miguel Oliveira November 01, 2013