Generate random numbers from 1-100 from the generator 1-50

Question

in a recent interview I was asked the following question:

Print random numbers from 1 to 100 using the specified getrnd50() method, which generates random numbers from 1 to 50. Each random number should be printed only once and in random order. Using another random number generator is allowed, and I was not allowed to change the definition of getrnd50() .

I came up with the following code that gives the correct output.

 import java.util.Random; public class Test { public static void main(String[] args) { int[] rs = new int[100]; int count = 0; int k; while (count != 100) { // I decided to simply multiply the result of `getrnd50()` by 2. // But since that would generate only even numbers, k = getrnd50() * 2; // I decided to randomly subtract 1 from the numbers. // Which i accomlished as follows. if (getrnd50() <= 25) // 25 is to half the possibilities. k--; // Every number is to be stored in its own unique location // in the array `rs`, the location is `(number-1)`. // Every time a number is generated it is checked whether it has // already been generated. If not, it is saved in its position, printed and // `count` is incremented. if (rs[k-1] == 0) { rs[k-1] = k; count++; System.out.print(k + " "); } } } // This is the method and i am not supposed to touch it. static int getrnd50() { Random rand = new Random(); return (1 + rand.nextInt(50)); } } 

While this was accepted in this round, in the next round, the interviewer tells me that getrnd50() is an expensive method, and even in the best case, I should call it twice for each number generated. those. 200 times for 1-100. In the worst case, it will be infinity and tens of thousands in the average case. He asks me to optimize the code to significantly improve the average case.

He gave me a hint when I expressed my inability to do this, he said:

Consider the number of numbers generated when generating a new number. E.g. if count becomes 99, I don’t need to call getrnd50() I can just find the remaining number and print it.

As long as I understood his drift, I had no idea how this would help me, so obviously I was rejected. Now I am interested to know the answer. Help me! Thanx in advance!

Note: if someone is lazy to write a long code, just specify the part of generating the number, the rest is easy. Also, we are not required to follow the prompt.

Answer 1

The key is not to check if you generated the number before, which becomes very expensive when looking for only one remaining number, but to create the numbers 1-100 in order and then shuffle.

In your code, when you created 99 out of 100 numbers, you will go around generating random numbers until you find 1 remaining number. This is why the average case in your version is so bad.

If instead you just shuffle the array, you need to have as many random numbers as you do shuffle operations, and only as many shuffle operations as you need.

(For complete shuffle information, find Fisher-Yates , including the smallest bend option that the shuffled array can generate in place)

To generate random numbers, you need a variable generator, not a fixed 1-50. You can approach this in different ways, but be careful with skewing the results if you really want the result to have a good distribution over the possible states.

For example, I would recommend using an integer number of bits with a shift rather than trying to use a module. This is due to a certain number of cycles, if the values ​​are outside the desired range, but without the ability to change the initial generation of random numbers, your hands are somewhat tied.

 static int bits = 0; static int r100 = 0; static int randomInt(int range) { int ret; int bitsneeded = 32 - Integer.numberOfLeadingZeros(range - 1); do { while(bits < bitsneeded) { int r = (getrnd50()-1) * 50 + getrnd50()-1; if(r < 2048) { r100 <<= 11; r100 |= r; bits += 11; } } ret = r100 & ((1 << bitsneeded) - 1); bits -= bitsneeded; r100 >>= bitsneeded; } while(ret >= range); return ret + 1; } 

This implementation will use something in an area of ​​150 random numbers for your 100 modified array of values. This is worse than the modulo version, but better than the 2x input range, which was the best version of the original version. There is if the random generation was really random, yet the worst case scenario of infinity, but random generation usually doesn't work like that. If that were the case, I'm not sure if the results without a search were realistic given the limitations.

To illustrate, since the results are subtle, here is a graph of my proposed random routine compared to the modular version:

So, I think that although your random generation is a little inefficient and can be improved, the really big victory that the interviewer was looking for does not first need a lot of random numbers, making a shuffle rather than repeating the search with less chance.

Answer 2

Since 100/50 is an integer, it's pretty simple. Since 50 / (100/50) is an integer, this is even simpler.

If you do not quite understand this, here is a sample code:

 int rnd1 = getrnd50(); int rnd2 = getrnd50(); if (rnd1 % 2 == 0) { rnd2 += 50; } return rnd2; 

Here is the diagram:

• Two numbers randomly selected between 1 and 50 are called a and b .
• If a is equal, add 50 to b .
• Return b .

You can do this in one layer if you want:

 return getrnd50() + getrnd50() % 2 * 50; 

It's too confusing though.

Edit: I see that the question was really asking for a shuffled list, not a sequence of random integers.

This can be done by creating a list from 1 to 100 and performing 100 random swaps, for example, Shuffle Fisher-Yates. I assume that with a Fisher-Yate shuffle, the absolute minimum number of calls is 93 (given with the formula ceil(log50(100!)) ), But with a much simpler algorithm, you can use 200.

A simple algorithm involves replacing each of the 100 elements with a random element of 100. The number to be selected will be generated from 1-100 using the aforementioned generator.

For instance:

 for (int i = 0; i < 100; i++) { swap(i, getrnd100() - 1); // - 1 for zero base! } 

Here is the complete code:

 int[] result = new int[100]; for (int i = 0; i < 100; i++) { result[i] = i + 1; } for (int i = 0; i < 100; i++) { int j = (getrnd50() + getrnd50() % 2 * 50) - 1; int tmp = result[i]; result[i] = result[j]; result[j] = tmp; } return result; 

(Disclaimer: I do not know Java, and I have not tested it.)

The best case is 200, the worst case is 200, the average case is 200.

Answer 3

Here is how you could answer it. He uses the fact that

• Assuming you use a shuffle to get an O (n) replacement for the “cards,” the module decreases with the shuffle. that is, start with int[] all values ​​and shuffle it like Collections.shuffle ().
• you have more randomness than you need if you call getrnd50 () twice, for example, when you have less than 50 values ​​left to exchange.

EDIT: for those who are not familiar with how shuffling works, I added code for shuffling

 import java.util.*; import java.lang.*; class Main { public static void main(String... args) { int samples = 100; // all the numbers [1, 100] int[] nums = new int[samples]; for (int i = 0; i < samples; i++) nums[i] = i + 1; for (int i = samples - 1; i > 0; i--) { int swapWith = nextInt(i + 1); // swap nums[i] and nums[swapWith] if (swapWith == i) continue; int tmp = nums[swapWith]; nums[swapWith] = nums[i]; nums[i] = tmp; } System.out.println("calls/sample " + (double) calls / samples); System.out.println(Arrays.toString(nums)); int[] count49 = new int[49]; for (int i = 0; i < 49 * 10000; i++) count49[nextInt(49) - 1]++; int[] count54 = new int[54]; for (int i = 0; i < 54 * 10000; i++) count54[nextInt(54) - 1]++; System.out.println("Histogram check (49): " + Arrays.toString(count49)); System.out.println("Histogram check (54): " + Arrays.toString(count54)); } // keep track of the range of values. static int maxRandom = 1; // some random value [0, maxRandom) static int rand100 = 0; static int nextInt(int n) { while (maxRandom < 10 * n * n) { maxRandom *= 50; rand100 = rand100 * 50 + getrnd50() - 1; } int ret = rand100 % n; maxRandom = (maxRandom + n - 1) / n; rand100 /= n; return ret + 1; } static final Random rand = new Random(); static int calls = 0; static int getrnd50() { calls++; return (1 + rand.nextInt(50)); } } 

prints

calls / sample 0.94

[1, 37, 4, 98, 76, 53, 26, 55, 9, 78, 57, 58, 47, 12, 44, 25, 82, 2, 42, 30, 88, 81, 64, 99, 16 , 28, 34, 29, 51, 36, 13, 94, 80, 66, 19, 38, 20, 8, 40, 89, 72, 56, 75, 96, 35, 100, 95, 74, 69, 11 , 31, 86, 92, 6, 27, 22, 70, 63, 32, 93, 84, 71, 15, 23, 5, 14, 62, 49, 43, 87, 65, 83, 33, 45, 52 , 39, 91, 60, 73, 68, 24, 97, 46, 50, 18, 79, 48, 77, 67, 59, 10, 7, 54, 90, 85, 21, 61, 41, 3]

Histogram check (49): [10117, 10158, 10059, 10188, 10338, 9959, 10313, 10278, 10166, 9828, 10105, 10159, 10250, 10152, 9949, 9855, 10026, 10040, 9982, 10112, 10021, 10082 , 10029, 10052, 9996, 10057, 9849, 9990, 9914, 9835, 10029, 9738, 9953, 9828, 9896, 9931, 9995, 10034, 10067, 9745, 9873, 9903, 9913, 9841, 9823, 9859, 9941 , 10007, 9765]

Histogram check (54): [10124, 10251, 10071, 10020, 10196, 10170, 10123, 10096, 9966, 10225, 10262, 10036, 10029, 9862, 9994, 9960, 10070, 10127, 10021, 10166, 10077, 9983 , 10118, 10163, 9986, 9988, 10008, 9965, 9967, 9950, 9965, 9870, 10172, 9952, 9972, 9828, 9754, 10152, 9943, 9996, 9779, 10014, 9937, 9708, 9978, 9894, 9803 , 9904, 9915, 9927, 10000, 9838]

In this case, 100 numbers need less than 100 getrnd50 calls

If you have 1000 shuffle values

 calls/sample 1.509 

Answer 4

Slow performance of your code on this line

 if (getrnd50() <= 25) 

You need to find a way to get more information from this single random number generated, otherwise you are wasting these expensive generated resources. Here is my suggestion for this:

First, imagine that we will have a random number generator for numbers 0-15. Each number can be represented as a path in a binary tree, where sheets represent numbers. Therefore, we can say that we evaluate that if the condition is true every time we go to the left in the tree, starting from the root.

The problem is that the random number generator generates numbers in an interval that does not end with a power of two. Therefore, we need to expand this tree. This is done like this:
If the random number is in the range 0-31, we can do a great job with the tree for these numbers. If it is in the range 32-47, we use a tree from 0 to 15 for those, and in the case of 48-49 we use a tree for numbers 0-1.

So, in the worst case, we do not use much more information from this random number, but in most cases we do it. Thus, this should significantly improve the average case.

Answer 5

So, are you allowed to print the last missing number of annus sets of n numbers without generating a random number generator?

If so, you can use recursion and reduce the size of the set on each call, until you only have n = 2, and then call getrnd50 () once. when you return recursively, just print the missing number on each set.

Answer 6

  List<Integer> lint ; public void init(){ random = new Random(); lint = new LinkedList<>(); for(int i = 1 ; i < 101; ++i) { lint.add(i); // for truly random results, this needs to be randomized. } } Random random ; public int getRnd50() { return random.nextInt(50) + 1; } public int getRnd100(){ int value = 0; if (lint.size() > 1) { int index = getRnd50()%lint.size(); value = lint.remove(index); } else if (lint.size() == 1 ) { value = lint.remove(0); } return value; } 

Call getRnd50 () exactly 99 times. It is not truly random, since the numbers stored in a list of 100 integers are in sequence.

Answer 7

(1) Create an array A initialized with {1, ..., 100}. Save the variable 'length' of this array.

(2) Create a random method to randomly generate a number from 1 to length. Each call to this method will call getrnd50 () no more than 2. Call the return value as an "index".

(3) Output A [index], swap A [length] to A [index] and length -.

(4) Repeat (1) - (3) until the array becomes empty.