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