How to generate random numbers in [1...7] from random numbers in [1...5]

Well known as a Google/Microsoft interview question, the following problem is actually really complicated to solve correctly, although it looks easy:

Given a function which produces a random integer in the range 1 to 5, write another function which uses it and produces a random integer in the range 1 to 7.

I'm going to modify this a little and make it generic:
Given a function which produces a random integer in the range 1 to 5(M), write another function which uses it and produces a random integer in the range 0 to 7(N).

Of course it's easy to do it without generating a uniform distribution so I'm not going to spend time on that.
What needs to be done is generate a uniform distribution. But consider this example:
If we add random(5) + random(5), assuming random(5) generates numbers from 0 to 4, we have:

   1:  0+0

   2:  0+1, 1+0

   3:  0+2, 2+0, 1+1

   4:  0+3, 3+0, 1+2, 2+1

   5:  0+4, 4+0, 1+3, 3+1, 2+2

   6:  1+4, 4+1, 2+3, 3+2

   7:  2+3, 3+2, 3+3

   8:  3+4, 4+3

   9:  4+4

This obviously is not a uniform distribution because we have more chances of generating the number 4 than the number 8. So whatever algorithm is needed, it cannot simply use operations involving random(5). Or, actually it can, with some complicated math behind. Read about Box–Muller transformations and Rejection sampling.

What I think is a simpler algorithm is the following: since every number can be represented in X bits, generate X numbers from 1 to 5, and depending on the generated number, set bit X to 1 or 0. Number from 0 to 7 can be represented with 3 bits. Let me know what you think.

   1:  int genRandom1to5() {

   2:      return (rand() % 5) + 1;

   3:  }

   4:   

   5:  int genRandom1to7() {

   6:      int rand17 = 0;

   7:      for (int i = 0; i < 3; i++) {

   8:          int rand15 = 3;

   9:          while (rand15 == 3) {

  10:              rand15 = genRandom1to5();

  11:          }

  12:          if (rand15 < 3)

  13:              rand17 |= (1 << i);

  14:      }

  15:      return rand17;

  16:  }

How to find the missing number from an array

This is what I've been asked at an interview at Microsoft (over the phone): An array of length N (for example N = 6) is given, containing all the elements from 1 to N, except one which is duplicated. So instead of having:

   1:             1, 2, 3, 4, 5, 6

we have an array which has one number duplicated:

   1:             1, 2, 3, 4, 4, 6

(notice a duplicated "4"). One additional detail: the array is not ordered. This is an final example of such an array:

   1:             3, 4, 1, 6, 4, 2

The question is: how do you find the number which is missing?

There are multiple solutions:

1. We could order the array as the first step. This would have complexity O(n*log₂n) in the best case considering merge sort, or quick sort in the average case. Next step would be to iterate through the array once, and check which number is the same as the previous one. We have the answer.

2. Previous solution was O(n*log₂n) in time complexity and took no additional space to solve (depending on the sorting algorithm). A second solution would be to keep an extra array of boolean values, initialized with false. We can iterate through the array once, and switch the corresponding boolean value from false to true as we go. Once we find a value which is already true, we have the duplicated number. At the end, one of the values in the extra array will remain false. This is the answer. This solution is O(n) in time complexity (much better), but also has O(n) space complexity.

3. The last solution is the best but is a trick actually. Considering there are N numbers in the array, from 1 to N, it means their sum is (N*(N+1))/2. So if we do the sum in the array, it will be X, different than (N*(N+1))/2. Calculating the difference between the values gives us the answer to the questions in O(1) time complexity and O(1) space complexity.