Generate unique random number on each call

Question

In a interview I was asked to wrtie a method which will generate unique 5 digit random number everytime when it is called.For ex: if I call the method and get 22222 then in next call i should not get 22222.

I wrote a code as below:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class RandomNumberGen {


    private static ArrayList arr=new ArrayList();
    private static int k=-1;
    public RandomNumberGen(){
        for (int i=10000;i<99999;i++){
            arr.add(i);
        }
        Collections.shuffle(arr);
    }
    public static void main(String[] args) {
        for(int m=0;m<10;m++){
            try {
                System.out.println(new RandomNumberGen().randomNumbermethod());
            } catch (Exception e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }


    }
    public Integer randomNumbermethod() throws Exception{
        k++;
        if(k>=arr.size()){
            throw new Exception("No more number available");
        }else return (Integer) arr.get(k);
    }

}

Answer got accepted but I was asked to avoid memory wastage now. My question is here as you can see I am using only 10 numbers.So rest of the space occupied by arraylist is a memory-wastage.Is there a way I can achieve same thing without using extra memory. What I mean is there someway using which unique number can be generated on each call so that this much memory do not get wasted.

Answer 1

Implications:

• In order to not to return the same value twice, you need to track which numbers you've already generated. This can be very memory consuming.
• You eventually run out of numbers. Instead of keeping on searching for an unused random number, you can track how many numbers you've returned (or how many are still available) and recognize if you ran out of numbers.

The generated numbers could be tracked in a collection (Set). This means having an overhead of 32bit per number (when tracking available or generated numbers) plus the collection overhead. Another possibility is to use a boolean-array and mark which slots have been used. Again, this is an overhead, as booleans usually are stored as 32bit value.
But there's a cheaper way to store booleans: as packed bits in an integer. That's what java.util.BitSet does, so each boolean will occupy one bit.

Solution with BitSet and tracking how many numbers are available:

public class RandomNumbers {

    private final Random random = new Random();
    private final BitSet used = new BitSet();
    private final int min = 10000;
    private final int max = 99999;
    private final int numbersAvailable = max - min + 1;

    public static void main (String[] args) {

        RandomNumbers randomNumbers = new RandomNumbers();
        for (int i = 0; i < 100; i++) {
            System.out.println(randomNumbers.nextRandom());
        }
    }

    public int nextRandom () throws NoSuchElementException {

        while (numbersAvailable > 0) {
            int rnd = min + random.nextInt(max - min + 1);
            if (!used.get(rnd)) {
                used.set(rnd);
                numbersAvailable--;
                return rnd;
            }
        }
        throw new NoSuchElementException();
    }
}

Answer 2

Your method would indeed be ideal to create a large number of unique values, however if you are only creating a small number of unique values it can be more efficient to simply keep track of the used values to garantee uniqueness

import java.util.Collection;
import java.util.HashSet;
import java.util.Random;

public class UniqueRandom {

    static Random rnd=new Random();
    
    public static void main(String args[]){
        Collection<Integer> alreadyChosen = new HashSet<Integer>();
        for(int i=0;i<10;i++){
            System.out.println(getNextUniqueRandom (alreadyChosen));
        }
    }
    
    
    public static int getNextUniqueRandom(Collection<Integer> alreadyChosen){
        if (alreadyChosen.size()==90000){ //hardcoded 5 figure numbers, consider making a variable
             throw new RuntimeException("All 5 figure IDs used");
        }


        boolean unique=false;
        int value=0;
        while(unique==false){
            value=rnd.nextInt(90000)+10000;
            unique=!alreadyChosen.contains(value);
        }
        alreadyChosen.add(value);
        return value;
    }
    
}

This method is highly efficient when only a small proportion of the available range is required but becomes slower and slower as collisions become more common. The exact implementation you should choose is highly dependant upon how many values you need to get.

Notes to consider

• As already stated this will get very very slow as more values are chosen, should be made clear to end user, or even better; change algorithm after so many calls

Answer 3

private static int number = 10000;
public int getNextUniqueRandomNumber() {
   return number++;
}

Answer 4

Seems pretty straightforward. A much simpler solution with less memory usage is to just create a set that will hold all the numbers you want like this:

Random random = new Random();
Set<Integer> randomNumbers = new HashSet<Integer>(10);
while(randomNumbers.size() < 10)
    randomNumbers.add( new Integer(random.nextInt(89999) + 10000) );

And to view them all:

for(Integer randomNumber : randomNumbers){
    System.out.println(randomNumber);
}

This will guarantee uniqueness to the properties of a set and greatly improve your memory usage.

Answer 5

Just

(int)(Math.random()*89999)+10000

After edit: (just not understood before edit) - you can put generated number in HashSet and after random just check if set contains new number (it will go very slow if you use it many times, but I think this is a good solution if you don't need a lot of numbers.

From my comment: After exceding about 50% of numbers I would create a collection of remaining numbers to pick, same as yours, but you should document in class, that it can freeze for a moment after 50% results usage and give ability to set this factor to client.

Maybe ther is a better way, depending of "how much randomness" must be in generated numbers (for example mathematical approach to sequence generator)