## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

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

Some people have suggested making an array of the numbers we do not have in the given list. This array can be too big.

We can have this algoirthm:
1. Sort the given list. It takes time O(nlogn)
2. Instead of creating an array we can just get the size of the array, i.e., number of elements which are not present in the given list. It will be
size = (max-min+1) - (number of distinct numbers in the list)

3. Now we can get a random number k in the range [1,size]

4. Now we just need to find the kth number among the numbers which are not present in the given list. We have not created the array of missing numbers. So we will find the kth number among the missing numbers using the given list as follows:
a) take curr = min
b) take num = curr + k - 1 (taking k to bestarting from 1)
c) do binary search to find element in the list which is the rightmost element less than or equal to num. Label it as lower_element
If no such element exists, then num is less than first element in the list, so num is the answer.
Otherwise,
(i) count the number of elements from lower_element in this traversal to the lower_element in previous traversal (if first traversal, count number of elements from starting)
(ii) k = (count in step (i))
(iii) num = num + k

Example:

List is {10, 20, 40, 60, 80} //taking sorted list for convenience.
Range is 1-100

Step 2.
size = (100-1+1) - 5
= 95

Step 3.
Random number generated = 50

Step 4.

a) curr = 1
b) num = 1+50-1 = 50
c)
First traversal:
search for 50 in the given array.
lower_element = 40
i) count = 3
ii) k = 3
iii) num = 50+3 = 53

Second traversal:
search for 53 in the given array after 40.
There is no lower_element now.

Basic Assumption: We have a function that generates a pure random number from 1 to n.

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

This is an elegant solution. With nlogn preprocessing time and logn per query, which can be improved if used a hash table to get a constant time per query.

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

What are you planning to store in the hash table?

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

Tushar, I like how your solution focuses on just the elements not in the list but I don't think its quite correct.
Consider a dense array, lets say from [1-100] where only two elements are missing: 50 and 60. (So existing elements are 1-49, 51-59 and 61-100)
Step 2:
size = (100 - 1 + 1) - 98 = 2
Step 3:
Random number will be generated in set [1,2], lets say we got 2
Step 4:
a) curr = 1
b) num = 1 + 2 - 1 = 2
c)
First binary search for 2 will return 2 since it exists in the array
lower_element = 2
i) count = 2
ii) k = 2
iii) num = 2 + 2 = 4

Second traversal:
Search for 4 in the given array after 2, so the rest of the array starting at 3

Search for 4 will result in finding 4. Would you return that?

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

Thank you for pointing this out
I forgot to write the basic point that we will go through a loop till the num is less than the smallest element in the subarray being considered at a particular point.
So in the example you have given, we will not stop at 4. We will again traverse with k=2 and go on like that. After reaching 50, k=1. Then we will move ahead and reach 60.
In my example there were 2 traversals as it required that only.

Also I have not covered the case where all numbers in the range are in the list. I have also assumed that numbers are distinct in the list.
When we are implementing this, we will need to take care of such edge cases. There are some other cases like min<=max and others which will be taken care of while implementing.

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

Actually you do NOT need to do the binary search step.
So you know that your array contains integers ranging between min and max.
Algorithm is as follows:
1) Sort array
2) Check min of array and max of array (first and last element), if different from min and max given, you found yourself a solution
3) Otherwise, you just do a linear pass on the sorted array:
Compare consecutive elements, if the A[i+1]-A[i] > 1, then you simply return A[i]+1 as your solution.

4) If you passed steps 2 and 3 without a solution, your array contains all the integers between min and max

Cheers

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

@sam
you get a number
but would it be random?
you'll always get the same answer for a given list, min and max

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

@Tushar
I had completely missed the "random" requirement of the question, thanks for pointing that out.
In that case I would slightly modify the algorithm as follows:
3) Throughout the linear pass, if A[i+1]-A[i] > 1, keep track in an array B (or linkedlisted B) the pair (A[i], A[i+1]-A[i]-1) , where A[i+1]-A[i]-1 is the range of missing integers.
Keep track of a variable Tot_Range = Tot_Range+ A[i+1]-A[i]-1, which is the number of missing integers

4) When done, generate a number X uniformly at random between (1 and Tot_Range),
5) Find =0;
Do a linear pass on array B, where you keep track of Find = Find + B[i].range, and whenever Find > X, you found your offset and return: X = B[i].offset + (X- (Find-B[i].range))

The complexity of the solution remains the same. We created a compact description of the missing values which is O(missing ranges), which might be the disadvantage. Of course there's a tradeoff...

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

There are always trade offs involved
In the example in third comment on this answer, your method would be faster and extra space taken would not be much, whereas if there are missing numbers which are distributed into many different ranges, it might lead to too much extra space.
An answer similar to yours has been posted by notbad on Jan 6.
It is quite difficult to have one best anwer.

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

Use a hash[] array to keep track of generated numbers ( or use hash-map )

``````hash[] --> order of size of given list, set all false
count = 0 --> no of different values generated

do{
r = min + rand()%( max-min+1 );
index = hash_func(r)
if( !hash[index] ) {
hash[index] = true
count++
}
} while( r is in list and count < list size );

if( count < list size ) return r;
else : no random no. possible``````

Complexity : O(n* [ complexity of random() ] * [ complexity of hash_func() ]*[ complexity of list search ] )

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

i think if all numbers are defined in the rangeļ¼ you will have an infinite loop

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

In that case no random number is possible, we can add a check for number of different values generated to avoid the infinite loop ( done )

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

if list does not have all numbers in range and only thse n numbers are generated by random, will thi return random no. not possible?

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

Its given that list has all numbers within the range.

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

We can use intervals to store all the numbers possible. For examples, min=0, max=10 and the forbidden list is {1,5,8}, then we get an array of interval {[0,0],[2,4],[6,7],[9,10]}.We need sort the list to create the array of interval. Rand a number in [0,max-min-|forbidden list|],Next we only need to find the k-th in the array of interval. We can use binary search to do this. The complexity if O(ln(max) + |list|ln(|list|)) in time, and O(|forbidden list|) in space .

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

Why are you finding kth number ?
I think it would be better to use two random numbers r1 , r2.

r1 - > get a random interval
r2 -> get a random number in that interval

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

@Cerberuz The intervals may have different sizes. They can't be selected with the same possibility.

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

They can be but i think you mean to say the values overall can't be selected with same probability :). We can use some weight function which depends on size of interval to avoid it.

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

How are you generating those intervals? It isn't a given that the list is sorted in the initial question.

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

@brodude yeah,we should sort the list first, and then create the array of intervals.

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

This is my solution, although be aware you need to check for if insertion is possible. Please tell me if you break it!

``````public void numInRange(int[] intList,int min,int max){
Arrays.sort(intList); //Must sort for BinSearch
int range = (max-min+1);
int kVal = (int) rand.nextInt(range) + min; //Instantiate outside
while(Arrays.binarySearch(intList, kVal) >= 0){
if(Arrays.binarySearch(intList, kVal) < 0){
break;
}
else{
kVal = (int) rand.nextInt(range) + min;
}
}
System.out.println(kVal);
}``````

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

I think this will generate an infinite loop if no possible random number is found

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

Your while loop condition checks that return value of function is non negative and then inside the loop, you check that the value is negative. I think the condition inside the loop is redundant.

I agree with Hugo that this will be stuck indefinitely till you are able to generate a number not in the list. It might be in 1 step or it might even take a long time to get that value. It is not deterministic. Though we need a random value, we need an algo that will come to an end within a limited time.

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

pick and count numbers in range (min, max)
missing = max-min-num
n = random()%missing - This is actualy not 100% safe radnom generator.
sort picked numbers
Pick n-th numer not in list using counting.

Complexity n*log(n).

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

Sorting numbers in range (min, max) is not nlog(n) as in this case N refers to order of size of given array. Example : max = 10^18, min = 0, size of given array = 100

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

The data structure contains two lists, one list(InList) contains the numbers it have, the other(OutList) contains numbers that has not been included yet. Use random on the OutList to get the number

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

If you are not allowed to change the data structure, you can do it like this:
int length = list.length();
int total = max - min;
int range = total - length;
int index = min + rand()%range
r = index
while(r in list) {
r++;
}

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

I believe the answer above is not correct, try this:
r = min + rand()%(max-min+1)
while( r in list) {
r ++;
}

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

With r = min + rand()%(max -min + 1) there is a chance of getting max and min which are part of the list. So I think it would be better to ignore those numbers..

the solution i can think of is
do {
r = (min + 1) + rand()%(max-min - 2); }
while( r is in the list)

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

Usually we include end points in the range ( though inclusive word has not been explicitly used ).

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

In O(n) Complexity and O(n) Space Complexity.

Store the elements in a hash map which are in the range min and max both inclusive or both exclusive

Generate a new array of numbers from min to max not putting the number in the new array if it is already in the hash map.

Get the size of the new array

Generate a random number in the range 0 to size and return the number at the index of random number.

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

Again, O(max-min) will not be considered as linear complexity in this case. as it is possible that (max-min) >> size of given array

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

In O(n) Complexity and O(n) Space Complexity.

Store the elements in a hash map which are in the range min and max both inclusive or both exclusive

Generate a new array of numbers from min to max not putting the number in the new array if it is already in the hash map.

Get the size of the new array

Generate a random number in the range 0 to size and return the number at the index of random number.

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

``````class Solution {
private \$pin;

public function __construct() {
\$this->pin = array(44,49,12,39,21,15,23,25,33,1,21,17,23,6,30,15,36,8,7,35);
}

public function run() {
\$minPos = 0;
\$min = \$this->pin[\$minPos];
\$maxPos = 0;
\$max = \$this->pin[\$maxPos];
\$checked = array();

/**
* Find min and max
*/
for(\$i=1; \$i<count(\$this->pin); \$i++) {
if(\$this->pin[\$i]<\$min) {
\$min = \$this->pin[\$i];
\$minPos = \$i;
}

if(\$this->pin[\$i]>\$max) {
\$max = \$this->pin[\$i];
\$maxPos = \$i;
}
}

\$counter = 0;
do {
\$counter++;
if(\$counter>=100) {
break;
}
/**
* generate random number
*/
\$isChecked = false;

\$iterator = 0;
do {
\$iterator++;
if(\$iterator>=100) {
fwrite(STDOUT,"No unchecked number found after 100 iterations".PHP_EOL);
break;
}
\$rand = rand(\$min, \$max);
for(\$i=0; \$i<count(\$checked); \$i++) {
if(\$checked[\$i]==\$rand) {
\$isChecked = true;
}
}
} while(\$isChecked);

\$exists = false;
/**
* Check if exists
*/
\$low = min(array(\$minPos,\$maxPos));
\$high = max(array(\$minPos,\$maxPos));

for(\$i=\$low; \$i<\$high; \$i++) {
if(\$this->pin[\$i]==\$rand) {
\$exists = true;
\$checked[] = \$rand;
}
}
} while(\$exists);

if(\$counter<100) fwrite(STDOUT,"Random number: ".\$rand.PHP_EOL);
}
}

\$obj = new Solution();
\$obj->run();``````

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

Insert all the numbers into a hashtable as keys.
Initialize a counter to the minimum value that is not used (that is, there is no key of that value), and then iterate on the hashtable keys.
For each key, do the following:
- if the key is smaller than the counter, then skip this iteration
- set the value associated with the current key to be the value of the counter.
- Increase the counter until it points to an empty slot.

The counter's value has been increased by the number of unique values, so the length of range between the counter and max equals the number of values not present in the input list.

The values in the range between counter and max have been mapped to unused values between min and counter.

So we choose a random number between counter and max, and return it if it's not in the hashtable, otherwise return the value stored for it in the hashtable.

Subsequent random values can be produced in O(1) time worst-case.

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

``````#!/usr/bin/python

import random

class C:
def __init__(self, l):
self.min_val=min(l)
self.max_val=max(l)

self.d=dict()
unique_keys=0
for k in l:
if not self.d.has_key(k):
unique_keys+=1
self.d[k]=None

free_pos=self.min_val
self.min_val+=unique_keys

for k in self.d:
if k<self.min_val:
continue
if self.d.has_key(k):
while(self.d.has_key(free_pos)):
free_pos+=1
self.d[k]=free_pos
free_pos+=1

def rand_unused(self):
r=random.randint(self.min_val, self.max_val)
if self.d.has_key(r):
r=self.d[r]
return r

def main():
l=[1,8,6,10]
print "hello"
print l
c=C(l)
res=dict()
for i in range(1,1000):
r=c.rand_unused()
print r
res[r]=res.setdefault(r, 0)+1
print res

if __name__ == "__main__":
main()``````

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

``````import random

class C:
def __init__(self, l):
self.min_val=min(l)
self.max_val=max(l)

self.d=dict()
unique_keys=0
for k in l:
if not self.d.has_key(k):
unique_keys+=1
self.d[k]=None

free_pos=self.min_val
self.min_val+=unique_keys

for k in self.d:
if k<self.min_val:
continue
if self.d.has_key(k):
while(self.d.has_key(free_pos)):
free_pos+=1
self.d[k]=free_pos
free_pos+=1

def rand_unused(self):
r=random.randint(self.min_val, self.max_val)
if self.d.has_key(r):
r=self.d[r]
return r``````

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

We can attempt this problem the following way:

Case 1: If the range [min, max] >> the number of elements N in the list, we can generate a random number "min + rand(max-min+1)". Sort the list which is done once, O(nlgn) preprocessing cost. Binary search the number in the list, if found, generate another number, else return the number. We have high probability of hitting a random number not in the list because range of min,max is very large. O(lg N) time, O(1) space to generate one random number.
Case 2: If the range [min,max] = O(n) and there are few elements not in the list. We can generate another list of missing elements (which will be far fewer than N) and generate a random number out of this missing elements list. If there is just one missing element, that will be outputted every time. O(1) time, O(1) space because there are few elements in the new array.
Case 3: If the range[min,max] = O(n) and there are nearly as many missing as the numbers in the list within some constant multiple. We can use case 1 with the disadvantage of unbound time to get a random (in case if keeps on hitting the element in the list but with the advantage of no additional space. We can use case2 with the disadvantage of using O(n) additional space but random number generation is O(1) worst case.

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

init time is o(n)
random value generation's time complexity is o(1) and space complexity is o(1)

1. create function for prime generation. f(min) is 2, f(min+1) is 3, f(min+2) is 5 ... f(max)
2. go through the whole array. get one big data t = f(array[0]) * f(array[1]) *... f(array[n])
3. generate one random value x . if t mod x != 0, it didn't appear in this array.

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

Hash table can be used in this case. What we can do is insert all elements of the array in an hash table, without any duplication. Then generate a number between min and max, check whether the number exist in hash table if it does then generate again or else show that number. One draw back of this approach is that we can stuck in loops while generating random numbers as they are always present in hash table.
Another approach is that we store all number which are not present in the array and then randomly show all numbers with equal probability. Generate random number between 0 and size of new array, use this number to print element on that index.

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

Implement a custom quick sort with random partition where in each iteration get the nearest min and max to pivot. If there any space between nearest min or max to the pivot then return the random number, else continue with custom quick sort recursively.

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

``````import java.util.Arrays;
import java.util.Random;

public class ExclusionRandom {

public ExclusionRandom(int seed, int arr[], int min, int max){
if(arr.length > 0){
if(min > arr[0] || max < arr[arr.length-1]) throw new IllegalArgumentException("Bound error");

for(int i = 1; i < arr.length; i++){
if(arr[i-1] == arr[i]) throw new IllegalArgumentException("Repeated numbers in input");
}
}

arr_ = arr;
min_ = min;
max_ = max;
rand_ = new Random(seed);
}

public int random(){
int ret = min_ + rand_.nextInt(max_-min_+1-arr_.length);

for(int i = 0; i < arr_.length && ret >= arr_[i]; i++) ret++;

return ret;

}

// same as random, but the first index to search from is obtain using search
public int fastRandom(){
int ret = min_ + rand_.nextInt(max_-min_+1-arr_.length);

int firstIdx = Arrays.binarySearch(arr_, ret);
if(firstIdx < 0) firstIdx = -(firstIdx+1);
else firstIdx ++;

ret+= firstIdx;

for(int i = firstIdx; i < arr_.length && ret >= arr_[i]; i++) ret++;

return ret;

}

private Random rand_;
private int arr_[];
private int max_;
private int min_;

public static void main(String[] args) {
int [] forbidden = {-4, 2 ,5,6};
int min = -10, max = 10;
ExclusionRandom er = new ExclusionRandom(1, forbidden, min, max);

int [] results = new int[max- min+1];

for (int i = 0; i < 100000; i++) {
results[er.fastRandom()-min]++;
}

printResults(results, min);
}

private static void printResults(int[] results, int min) {
for (int i = 0; i < results.length; i++) {
System.out.println((i+min)+": " + results[i]);
}

}

}``````

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

We can use partition algorithm from quick sort to reduce the time complexity. Hashing is okay, but we can do this in O(1) space with a decent time complexity.
> Partition the array using max. Now all the elements to the left of this array is smaller than this. Now partition using min. So we have min and max at its sorted position. All the numbers between min and max are also in between position of max and min in the array.
//O(n)
Eg: {3, 4, 2, 6, 8, 9}, max = 8, min = 4
-> {3, 2, 4, 6, 8, 9}
> Sort only between max and min. So here time complexity is O(klogk) where k is number of elements between max and min. Also we know that k is strictly < n else there would be no answer.
> From now on, our array means only the element between min and max.
> randRange = (max - min +1) - size(array)
> random = Math.rand( )%randRange;
> So now you have a number between 0 and number of missing elements.
You can just run binary search and return the missing number depending on the position.
Suppose random returned 2 in above array, we just find the number which has 2 numbers lesser in its position using binary search and print that. //O(logk)
So overall time complexity would be O(klogk) where k is the number of elements between max and min array elements. It does not depend upon range of max and min.
Space complexity O(1).

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.