## Google Interview Question

Software Engineer / Developers**Team:**Google New York City

**Country:**United States

**Interview Type:**Phone Interview

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.

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?

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.

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

@sam

you get a number

but would it be random?

you'll always get the same answer for a given list, min and max

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

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.

Thanks for your approach.

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 ] )

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 )

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?

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 .

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

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

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.

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

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

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.

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

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)

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.

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.

```
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) {
fwrite(STDOUT,"No answer after 100 iterations".PHP_EOL);
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();
```

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.

```
#!/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()
```

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

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.

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.

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.

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

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

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

- Tushar January 07, 2013We 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.

So the answer is 53.

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