4

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.

Marko Topolnik
  • 195,646
  • 29
  • 319
  • 436
TheGraduateGuy
  • 1,450
  • 1
  • 13
  • 35
  • 1
    If you only want 10 values you could just keep a collection of already chosen values and check the random values aren't in it. This becomes increasingly horrible for more values but 10 will be fine – Richard Tingle Sep 25 '13 at 12:30
  • possible duplicate of [Generating random numbers in a range with Java](http://stackoverflow.com/questions/363681/generating-random-numbers-in-a-range-with-java) – sp00m Sep 25 '13 at 12:31
  • Arraylist would of course do for such a collection but some kind of set (like a hashset) is likely to be far more efficient – Richard Tingle Sep 25 '13 at 12:32
  • 1
    @sp00n that question does not concern itself with uniqueness – Richard Tingle Sep 25 '13 at 12:33
  • @sp00m i saw that post but my question is here related with wastage of memory with that approach – TheGraduateGuy Sep 25 '13 at 12:40
  • Lucky that it was accepted, since it is wrong! You create a new instance of `RandomNumberGen` in each loop cycle instead of reusing that instance. And before your next interview you should read about generics. – Gyro Gearless Sep 25 '13 at 12:40
  • @Richard. I don't need just 10 number .I just used the example to show the memory wastage.I might call the method more number of times. – TheGraduateGuy Sep 25 '13 at 12:41

5 Answers5

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

Random number generator

Piotr Müller
  • 5,323
  • 5
  • 55
  • 82
7

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();
    }
}
Peter Walser
  • 15,208
  • 4
  • 51
  • 78
  • 1
    This should be the correct answer. In my VM (Oracle 1.7 64 Bits on Linux) a profiler shows less than 50K memory consumption for the `BitSet`. Plus, while both the `HashSet` and `BitSet` provides amortized constant lookup / insertion time. `BitSet` `get` / `set` operations runs circles around `HashSet` `get` / `add`. If I was the interviewer I would be very pleased to see a programmer using a `BitSet` to solve this kind of problem. – Anthony Accioly Sep 25 '13 at 13:33
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)

Piotr Müller
  • 5,323
  • 5
  • 55
  • 82
  • I need int/integer number only .And this method can be called many times until all the 5 digit numbers are over.I just showed an example by calling it 10 times to show ememry wastage. – TheGraduateGuy Sep 25 '13 at 12:34
  • So i would pick a factor of possible results population. After exceding about 50% of numbers I would create a collection of remaining numbers to pick, same as yours (and you can garbage existing set). – Piotr Müller Sep 25 '13 at 12:36
  • Edited answer with casting to integer – Piotr Müller Sep 25 '13 at 12:38
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.

r0t0xd
  • 206
  • 1
  • 6
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
Community
  • 1
  • 1
Richard Tingle
  • 16,906
  • 5
  • 52
  • 77
  • Its returning 4 digit and 3 digit number as well. – TheGraduateGuy Sep 25 '13 at 12:45
  • @AnujKumarJha Have adjusted such that only 5 digit unique numbers are returned – Richard Tingle Sep 25 '13 at 12:50
  • Method will infinitely loop if you have used all the random numbers, you could check `alreadyChosen.size()` if there is a chance to find a new one though. – zapl Sep 25 '13 at 12:55
  • My suggestion is to at least include a warning in JavaDoc that this method will slow after much calls. Eventualy check .size() and throw a `RuntimeException/IllegalStateException` if called when 89999 numbers were already picked. – Piotr Müller Sep 25 '13 at 12:56
  • 1
    Or even better: once `alreadyChosen` contains 50% of all numbers switch to shuffeled list of not yet chosen numbers and pop a number each time until list is empty. Faster and memory consumption is halved. – zapl Sep 25 '13 at 12:58
  • 2
    @killer_PL If I was writing this for real I would write it so that it changed its method after (say) 10000 calls, but all that is too complicated for an SO answer. I have made those points more explicit however – Richard Tingle Sep 25 '13 at 13:00