## Sunday, May 29, 2005

### A Paltry Plethora of Permutation Puzzles

I remember a few years ago whenever I would hear a new puzzle it would often be prefaced by the explanation that this was a puzzle asked at interviews for Microsoft. Examples were the classic "how to test if a linked list has a loop in it in linear time and constant space", and the by now hoary "U2 Puzzle". I always maintain the answer to "what should U2 do in this situation?" is "Sack their tour manager", but sadly no one seems to think that this is reasonable. International supergroups have never previously shown such strong regard for punctuality and I believe that their fans could tolerate the extra three minutes delay. Certainly, some of Microsoft's software releases have been in excess of three minutes later than their original shipping date. But I digress.

Anyway, these days many new puzzles I hear are prefaced by by an explanation that they were asked at interviews for Google. I wonder when this shift happened and Google took the crown for being the tech company with a reputation for hiring the best at answering funny little puzzles. I also wonder if they really were asked in interviews, or whether this is just a shorthand for "This is a moderately tricky problem, but you should be able to work out an answer within a reasonable period of time. At the very least you should be able to find some solution quite quickly even if it is not the optimal one". With this in mind, here are three puzzles relating to permutations which I think are of "popular tech company interview level". They might puzzle you for a while, but the solutions are fairly simple.

1. You are given a permutation of 1...n and you want to cyclically shift it by k. That is, the item at position 1 should go to k+1 mod n, at position 2 should go to k+2 mod n and so on. Usual restrictions apply: do this in linear time and with constant space [that is, you have a constant number of variables which can each hold an item or a pointer].

2. You are given a string of length n, consisting of words separated by spaces. Permute it so that the order of the words is reversed, but the words themselves still read left to write. For example, the transform applied to the first sentence of this puzzle would be "spaces. by separated words of consisting n, length of string a given are You"

3. Take a permutation of 0..2n-1 and subtract i from the i'th entry, modulo 2n.
For example, 2 3 1 0 becomes 2 2 3 1. Show that for any n this operation can never result in a new permutation. [Note that the permutation is of even length; for odd length one can easily find a permuation of length 3 for which this is not the case].

In terms of origins, one of these was apparently asked in a Google interview. One was a puzzle created by a CS researcher (not sure whom or how), and two of then came up in the context of a research problem to prove a lemma. Yes, that's four: one puzzle came up in two contexts.

Many thanks to Amit and Muthu for telling me some of these problems.