2

A question that was asked during a job interview (which I pretty much failed) and sadly, something I still cannot figure out.

Let's assume that you're given some positive integer, n. Assume that you construct a sequence consisting of only 1 and 0, and you want to construct a sequence of length 2^n + n-1 such that every sequence of length n consisting of adjacent numbers is unique.

for instance

00110 (00, 01, 11, 10) for n=2

How would one construct such a sequence?

I think one should start with 0000..0 (n zeroes) and do something about it.

If there is a constructive way of doing it, maybe I could extend that method to constructing a sequence consisting of only 0, 1, ..., k-1, and having length k^n + n-1 such that every sequence of length n consisting of adjacent numbers is unique (or maybe not..)

(sorry, my sequence for n=3 is wrong, so I deleted it. also, i've never heard of De Bruijin's sequence. I know it now! thanks for all the answers and comments).

Improve this question
4
  • 3
    Your sequence for n=3 does not contain 100, and it contains 010 twice. Perhaps this is impossible except for n=2? Or I've misunderstood the question. Commented Nov 14, 2013 at 9:59
  • 5
    So, like a De Bruijn sequence? (otherwise, what's the difference?) Commented Nov 14, 2013 at 10:01
  • 2
    De Bruijn sequences includes cycles, where the end of the sequence can wrap around to the start, and are therefore shorter, just 2^n. But this question involves length 2^n+n-1. So the question here is slightly different. But the answer is the same! Just take a De Bruijn sequence, copy a few characters from the beginning and paste them onto the end. (I never heard of De Bruijn sequences before today, thanks @harold) Commented Nov 14, 2013 at 10:26
  • @user98235, you should probably delete the 0 from the end of your n=3 sequence, and put a 1 at the front. That would give you 100, and remove your duplicate 010. Commented Nov 14, 2013 at 10:28

1 Answer 1

Reset to default
1

This strikes me as a very ambitious interview question; if you don't know the answer, you're unlikely to get it in a few minutes.

As mentioned in comments, this is really just the derivation of a de Bruijn sequence, only unwrapped. You can read the Wikipedia article linked above for more information, but the algorithms it proposes, while efficient, are not exactly easy to derive. There is a much simpler (but rather more storage-intensive) algorithm which I think is folkloric; at least, I don't know of a name attached to it. It's at least simple to describe:

  • Start with n 0s

  • As long as possible:

    • If you can add a 1 without repeating a previously-seen n-sequence, do so.
    • If not but you can add a 0 without repeating a previously-seen n-sequence, do so.
    • Otherwise, done.

This requires you to either search the entire string on each iteration, requiring exponential time, or maintain a boolean array of all seen sequences (coded as binary numbers, presumably), requiring exponential space. The "concatenate all Lyndon words in lexicographical order" solution is much more efficient, but leaves open the question of generating all Lyndon words in lexicographical order.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.