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 didnt 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 cant 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.
0 komentar:
Posting Komentar