## Google Interview Question for SDE1s

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 12 vote

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

Comment hidden because of low score. Click to expand.
0

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...

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

Ahh... some how I still had the >= bug in my mind. Thank you.

Comment hidden because of low score. Click to expand.
1
of 1 vote

yeah, it sucks that the edit/remove feature is gone :s

Comment hidden because of low score. Click to expand.
1
of 1 vote

What does the uniform() method do? Never seen it before in Java..

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

"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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

you misread my approach. that was just an example.
K should just contain numbers between 0 and N

Comment hidden because of low score. Click to expand.
3

Sorry , but isn't it much more simple way coding your approach ?

int RandNum( int N , vector<int> k)
{
int jumps = 0 ;
int i = 0;
int num = uniform(N - k.size());
while ( i < k.size() && jumps + num >= k[i])
{
++jumps;
++i;
}
return jumps + num ;
}

Comment hidden because of low score. Click to expand.
4
of 6 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

best solution

Comment hidden because of low score. Click to expand.
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)

Comment hidden because of low score. Click to expand.
0

Good solution. But, truly speaking, if K array is not modifiable, it uses O(K) additional memory.

Comment hidden because of low score. Click to expand.
3
of 3 vote

``````// 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) {
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;
}``````

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

+1. this is very clean and easy to understand.

Comment hidden because of low score. Click to expand.
0

Can some one please explain the logic?

Comment hidden because of low score. Click to expand.
0

K [0, 2, 3, 4], N = 5;
In this case, pos is 0/1+1, consider pos = 1+1 =2;
run through while loop.
in the end, l = 3.
return value 2+3-1 = 4; but it's there in the K.
Correct me if I am wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

:) 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.

Comment hidden because of low score. Click to expand.
0

And I don't see any examples from him.

Just function signature, and constraints (not "objective" just constraints).

And some code with some comments that don't match the previous signature and constraints.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

can't edit or remove the post. there's a little bug >= should be >. fixed below

Comment hidden because of low score. Click to expand.
0
of 4 vote

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

Comment hidden because of low score. Click to expand.
0

can't edit or delete. please ignore. correct post below

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0

the signature is

``int randomNum(int n, vector<int> A)``

Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

Comment hidden because of low score. Click to expand.
0

good one too

Comment hidden because of low score. Click to expand.
0

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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int getRandom( int n, int K[], int sz) {
int L = n - sz;
int c = rand() % L;

if (c < K)
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;
}``````

Comment hidden because of low score. Click to expand.
0

I forgot the necessary index decreasing:

``2.4		index++``

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

I forgot the necessary index decreasing:

``2.4		index++``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

Memory O(1) run-time O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int num = 20;
int k[] = {2, 3, 6, 7, 8};

//	long int x = random() % 15;
long int x = 3;

cout << x << endl;

for (int i = 0; i < sizeof(k)/4 - 1; i++) {
if (x < k[i])
break;
else
x++;
}

cout << x << endl;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int num = 20;
int k[] = {2, 3, 6, 7, 8};

//	long int x = random() % 15;
long int x = 3;

cout << x << endl;

for (int i = 0; i < sizeof(k)/4 - 1; i++) {
if (x < k[i])
break;
else
x++;
}
cout << x << endl;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 - 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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int rand(int N, int[] K){
int R = N - K.length;
Random rand = new Random();
int p = rand.nextInt(R);
int j = 0;
int ret = 0;
for(;j<K.length; j++){
if(ret == K[j])
ret ++;
else
break;
}
for(int i = 0; i<p; i++){
if(j < K.length && ret == K[j]){
j++;
ret ++;
}
ret ++;
}
return ret;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int transform(int x, int k[], int kLen) {
int nExcluded = 0;
for(int i=0; i<kLen; i++)
{
if(x >= (k[i] - i))
nExcluded++;
else
break;
}
return x + nExcluded;
}

int getRandom(int N, int k[], int kLen)
{
int x = rand()%(N-kLen);

return transform(x, k, kLen);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#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 ) 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;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

We should return K[i]. Pr{K[i]} - probability return K[i].
Pr{K} = Pr{K} = ... = Pr{K[K.length - 1]} (from constraints).
But Pr{K} + Pr{K} + ... + 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?

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

N==K.length*

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

int RandomNum(int N, int K[])
{
int num = N-K_length;
srand (time(NULL));
int ret = rand() % num;
for(int i=0; i<K_length && K[i]<=ret; ++i,++ret);
return ret;

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.