Search this Java developer blog:

Can you write a program in Java? for beginner to intermediate level coding




Q. Can you write code to generate a 4 digit number, where the same number cannot be repeted? For example, 1234 is valid, but 1124 or 1214 are invalid because the value 1 is repeated.
A. Firstly, write some pseudo code

1. Have an array or list of numbers - 0,1,2,3,4,5,6,7,8,9
2. Shuffle these numbers randomly in a list or array.
3. Pick the first 4 number from the list or array
4. concatenate these 4 randomly selected numbers and return them as a 4 digit result.

Now, you can write the code as shown below:


import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class GenerateRandomNumber2 {
 
 private static final int GENERATION_COUNT = 10; 
 private static final int NUMBER_OF_DIGITS = 4;

 public static void main(String[] args) {
  for (int i = 1; i <= GENERATION_COUNT; i++) {             //e.g. generate 10, 4-digit numbers 
   System.out.println(generateNumber(NUMBER_OF_DIGITS)); //e.g. generate a 4 digit number
  }
 }

 public static String generateNumber(int size) {
  //input validation -- i.e. precondition check
  if(size <= 0 || size > 10) {
   throw new IllegalArgumentException("Invalid size: " + size);
  }
  
  //power of varargs to create a list of 10 numbers from 0 to 9
  List<Integer> listOfNumbers = Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
  
  //shuffle the numbers using the Collections utility class
  Collections.shuffle(listOfNumbers);
  
     StringBuilder sb = new StringBuilder(4);
     
     //get the size - for e.g first 4 shuffled numbers
     for (int i = 0; i<size; i++ ) {          //e.g. loops 4 times
   sb.append(listOfNumbers.get(i));     //string builder is used for mutation
  }
     
  return sb.toString();                   //convert to string object
 } 
}



Q. What if you didn't have the shuffle method in the Collections class?
A. Here is the pseudo code

1. Have an array  - 0,1,2,3,4,5,6,7,8,9
2. Loop through these numbers 4 times and randomly pick an index.
3. Once a number from an index is used, set the number on that index to say -1 so that the same number cannot be picked again.
4. If the same index was randomly picked, try again.
5. concatenate these 4 randomly selected numbers and return them as a 4 digit result.

public class GenerateRandomNumber {
 
 private static final int GENERATION_COUNT = 10; 
 private static final int NUMBER_OF_DIGITS = 4;

 public static void main(String[] args) {
  for (int i = 1; i <= GENERATION_COUNT; i++) {             //e.g. generate 10, 4-digit numbers 
   System.out.println(generateNumber(NUMBER_OF_DIGITS)); //e.g. generate a 4 digit number
  }
 }

 public static String generateNumber(int size) {
  // input validation -- i.e. precondition check
  if (size <= 0 || size > 10) {
   throw new IllegalArgumentException("Invalid size: " + size);
  }
  
  int[] myNumbers = new int[10];
  
  //store numbers 0 to 9 in an array
  for (int i = 0; i < myNumbers.length; i++) {
   myNumbers[i] = i;
  }
  
  StringBuilder sb = new StringBuilder(4);
  int index;
  
  for (int i = 0; i < size; i++) {
   index = (int) Math.floor(Math.random() * 10); // pick a random index
   if (myNumbers[index] >= 0) {
    sb.append(myNumbers[index]);
    myNumbers[index] = -1;  // mark it as used with -1
   } else {
    i--;   //try again if this index was already used i.e. value is -1
   }
  }
  return sb.toString();
 }
}


Some follow up questions:

Q. Was the above method thread-safe?
A. Yes, as it uses local variables and there is no shared data.

Q. How will you extend the above code so that each number generation happens on its own thread?
A. Spawn new threads as shown below


public static void main(String[] args) {
  for (int i = 1; i <= GENERATION_COUNT; i++) {    //e.g. generate 10, 4-digit numbers 
   Runnable r = new Runnable() {                   //e.g. generate a 4 digit number in its own thread 
    @Override
    public void run() {
     System.out.println(generateNumber(NUMBER_OF_DIGITS));
    }
   };
   
   Thread t= new Thread(r, "thread-" + i);
   t.start();  //executes the run( ) method
  }
 }

Q. How will you extend the code to retry when there is a duplicate 4 digit number?
A. Here is the added code to return only unique 4 digit numbers


    private static final int GENERATION_COUNT = 10; 
 private static final int NUMBER_OF_DIGITS = 4;
 
 private static final Set<String> setOfGeneratedNumbers = Collections.synchronizedSet(new HashSet<String>(10));

 public static void main(String[] args) {
  for (int i = 1; i <= GENERATION_COUNT; i++) {    //e.g. generate 10, 4-digit numbers 
   Runnable r = new Runnable() {                   //e.g. generate a 4 digit number in its own thread 
    @Override
    public void run() {
     System.out.println(getUniquelyGeneratedNumbers(NUMBER_OF_DIGITS));
    }
   };
   
   Thread t= new Thread(r, "thread-" + i);
   t.start();  //executes the run( ) method
  }
 }
 
 public static String getUniquelyGeneratedNumbers(int size) {
  // input validation -- i.e. precondition check
  if (size <= 0 || size > 10) {
   throw new IllegalArgumentException("Invalid size: " + size);
  }
  
  //generate a number first
  String genNumber = generateNumber(size);
  
  //check if the generated number was already generated, if yes -- generate another number
  while(setOfGeneratedNumbers.contains(genNumber)) {
   genNumber = generateNumber(size);
  }
  
  //store the generated number in the set
  synchronized(setOfGeneratedNumbers) {
     setOfGeneratedNumbers.add(genNumber);
  }
  
  return genNumber; 
 }
 


Q. Can you see any flaw(s) in the above code?
A. Mathematically you can only generate  5040 numbers. This was calculated as described below:

1. There are 10 numbers from 0 to 9.
2. You can't repeat the same number, so first digit can be chosen from 10 possible numbers, the second digit from 9 possible numbers, the third digit from 8 possible numbers, and the final and fourth digit from 7 possible numbers.
3. Hence, the number of 4 digit number combinations you can have is -- 10 * 9 * 8 * 7 = 540.

Flaw 1:

So, if the GENERATION_COUNT  is set to 5041, the while loop in the getUniquelyGeneratedNumbers(int size) method will never return false, and you will end up with an endless loop.


Flaw 2: 

The above code generate a new thread for each execution. This can potentially create 5040 new threads, which can be expensive new real production code and also can adversely impact performance as the CPU spends more time in context switching. It is best to use the Java 5 executor framework that lets create a pool of thread and reuse them.

No comments:

Post a Comment

5 recent Java developer posts