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

- Miguel Oliveira November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Justin November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"(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

- Miguel Oliveira November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Justin November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Miguel Oliveira November 02, 2013 | Flag
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..

- codewarrior November 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- A Non November 03, 2013 | Flag
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

- Miguel Oliveira November 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Guest November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira November 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

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

- Hen December 21, 2013 | Flag
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;
}

- karaamaati November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

best solution

- Vincent November 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Anonymous November 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Alex M. May 04, 2016 | Flag
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[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;
}

- Tim November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Tim November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- meow January 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can some one please explain the logic?

- sjsu January 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous February 28, 2014 | Flag
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...

- S O U N D W A V E November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- S O U N D W A V E November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- S O U N D W A V E November 01, 2013 | Flag
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

- Miguel Oliveira November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- S O U N D W A V E November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- S O U N D W A V E November 02, 2013 | Flag
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

- Miguel Oliveira November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira November 01, 2013 | Flag
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

- Miguel Oliveira November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Miguel Oliveira November 01, 2013 | Flag
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;
   }
}

- Jason November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the signature is

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

- Anonymous November 02, 2013 | Flag
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;
}

- mindless monk November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous November 05, 2013 | Flag
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.

- Anonymous November 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good one too

- Vincent November 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SS November 04, 2013 | Flag
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;
}

- sambatyon November 03, 2013 | Flag Reply
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[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;
}

- thiago November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I forgot the necessary index decreasing:

2.4		index++

- Anonymous November 04, 2013 | Flag
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

- Anonymous November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I forgot the necessary index decreasing:

2.4		index++

- Anonymous November 04, 2013 | Flag
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;
	}

- santhanamss November 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- santhanamss November 04, 2013 | Flag
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;

- May November 04, 2013 | Flag Reply
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;

- May A. November 04, 2013 | Flag Reply
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[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;
}

- YF November 07, 2013 | Flag Reply
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;
}

- ShiguangWang November 07, 2013 | Flag Reply
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);
    }

- James Tsay November 09, 2013 | Flag Reply
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[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;
}

- HoneyBall November 09, 2013 | Flag Reply
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;
	}

}

- Gaurav November 11, 2013 | Flag Reply
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;
}

- Prowindy November 14, 2013 | Flag Reply
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

- caniggia November 25, 2013 | Flag Reply
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[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?

- den November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- S O U N D W A V E November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

N==K.length*

- S O U N D W A V E November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira November 02, 2013 | Flag
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;

- Anonymous November 02, 2013 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More