## techInterview Discussion |
||

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor |
The problem:
You have an empty room, and a group of people waiting outside the room. At each step, you may either get one person into the room, or get one out. Can you make subsequent steps, so that every possible combination of people is achieved exactly once? Solution: Yes, given that the group size is >= 1 Proof: (We'll represent each person as a binary digit) Note that there is a solution for group size = 1 0 (single person outside room) 1 (single person inside room) Note that for n people, solution S will have 2^n - 1 steps Note also that S can be represented as a sequence of natural numbers which correspond to the binary digits. Observe that for n=2, 00 01 11 10 is a solution so S(2) = { 0 1 3 2 } Note that each natural number < 2^n is represented exactly once in S(n) Now, assume there is a solution S(n): Then S(n) has 2^n - 1 steps Let S(n+1) = S(n) + { 2^n + x for x in rev S(n) } where rev S(n) is the reversal of sequence S(n) for example: S(3) = S(2) + { 4 + x for x in rev S(2) } S(3) = { 0 1 3 2 } + { 4 + x for x in { 2 3 1 0 } } S(3) = ( 0 1 3 2 } + { 6 7 5 4 } S(3) = { 0 1 3 2 6 7 5 4 } S(3) = 000 001 011 010 110 111 101 100 Note that reversing S does not change its property of a single change per step Note that the addition of 2^n to rev S(n) does not change its property of a single change per step Note that the addition of 2^n to rev S(n) insures that each element of {2^n + x for x in s(n)} > each element of S(n) Note that the length of S(n+1) = 2 (2^n - 1) = 2^(n+1) - 1 Note that because of the reversal and addition, the last element of S(n) differs in one binary place from the first element of { 2^n + x for x in rev S(n) } Therefore: if S(n) is valid, so is S(n+1) Thus, by the principal of mathematical induction, there is a valid for all n >= 1 |

Powered by FogBugz