techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

One in, One out

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
Enguerrand Send private email
Tuesday, July 08, 2008
 
 
If I'm not mistaken, this is also known as a 'de Bruijn sequence'. You can also restrict to those that are cycles. You can also achieve the same in any base (not just in binary). There are quite a few properties of these sequence (try Google if you want to know more :) ).

R.
R. Send private email
Thursday, July 10, 2008
 
 
I don't think DeBruijn. Gray Code seems more like it.
LLRB
Thursday, July 10, 2008
 
 
Right, read too fast!

R.
R. Send private email
Thursday, July 10, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz