CareerCup

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.

So the answer is 53.

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

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

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 .

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

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

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

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

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

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.

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.

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