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.
Solution for Problem 1. I think that this satisfies your constraints.
ReplyDeleteint shifter(valarray int & vec, int k)
{
if (vec.size() == 0 || k < 0)
return -1;
if (k % vec.size() == 0)
return 0;
int tmp;
for (int s = 0; s < k; s++) {
tmp = vec[1];
vec[1] = vec[0];
for (int index = 2; index < vec.size(); index ++) {
tmp ^= vec[index];
vec[index] ^= tmp;
tmp ^= vec[index];
}
vec[0] = tmp;
}
return 0;
}
Posted by Anonymous
I was actually asked #2 at an interview. Part A was reverse the elements in an string. part B) was to perform the reversal as stated above. Luckily, I happened upon the trick for (B).
ReplyDelete*********************
solution to b:
reverse entire string so "abc def" -> "fed cba"
then reverse each word so "fed cba -> "def abc"
Posted by marc
The third one is nice, but has a simple solution: in any permutation of {0, ..., 2n-1}, the sum of the elements must always be the same (mod 2n). To possibly yield a permutation, this implies that the sum of the shifts must be 0 mod 2n. But:
ReplyDelete0 + (-1) + (-2) + ... + (-2n+1) = - (2n+1)/2 * 2n
= - n (2n+1)
which is non-zero modulo 2n.
On the other hand, taking permutations on an odd number of elements we see that the sum of the shifts is:
0 + (-1) + ... + (-2n+2) = - (n-1)(2n-1)
which is zero modulo 2n-1. At least in principle, then, it is possible to obtain another permutation when dealing with an odd number of elements.
Posted by Anonymous
Nice comments so far.
ReplyDeleteAnon1. The bit fiddling operations are a little hard to read, but it looks like you are using them to do a cyclic shift of 1, then doing this k times over. Overall this has a cost of O(kn) not O(n) as desired. But I think your approach could be modified to run in a single pass. There are solutions with the same cost that don't do any bit operations (just copying/replacing entries) which might be a bit easier to read. These also require a nice little fact about the cyclic permutation being performed.
Marc. That's correct. For full credit, you'd need to specify how to do the reversals in linear time (not difficult, but a necessary step).
Anon2: Right argument, but I think your arithmetic is a bit off: the values subtracted are {0,1,2,..2n-1} which is a permutation, so summing the differences yields 0 mod 2n-1. Full credit for method, but less than full credit for working.
cheers
Graham
Posted by Graham Cormode
I will leave the linear reversal algorithm as an "exercise for the
ReplyDeletereader" ... ;-)
If you dont notice that trick though, it is a pretty annoying
little problem
Posted by Marc
Since you linked to it, I have to ask: Was Sariel's post about the google job question a joke? I admit that after reading the question, my first instinct was to resort to parametric search. And I remember thinking, "What kind of sadist asks a question like this for a job-interview question?" Then, after letting it soak in, I figured that a simple merge of the two arrays A and B in sorted order (with a notation added to each element so that we can recognize whether an element is from A or B), followed by a check to see when a "switch" occurs, (e.g., we have a transition from set A to set B) in the merged ordering should do the job. What was Sariel thinking?
ReplyDeletePosted by Anonymous
Anon3:
ReplyDeleteI don't follow your comment on Sariel's post.
Suppose
A: 10 9 5 4
B: 3 2 0 0
Then your alg would pick all of A and none of B (I think). How does this then generate large sums a+b? Note that the optimal solution to this instance is to pick 10,9 from A and 3,2 from B, and generate
13, 12, 12, 11
Graham
Posted by Graham Cormode
Re: Sariel's post. My bad. I revert to parametric search. Thanks.
ReplyDeletePosted by Anonymous