3 ms·
Permutations are much harder than reversing a linked list. Actually I'm interested in what solution you had in mind. I can only think of these three: 1) Do it
by jules 16y ago
Permutations are much harder than reversing a linked list. Actually I'm interested in what solution you had in mind. I can only think of these three:
1) Do it recursively like permutations(xs) = [[x] + p for p in permutations(xs - [x]) for x in xs].
2) Systematically generate all combinations of letters, only print the ones that are permutations of the original.
3) Systematically generate the permutations in lexicographical order.
All three would require pretty significant effort to get correct on a whiteboard in a language like C (without high level list comprehensions & operations).
- waterhouse 16y agoRegarding your last sentence, he did say: > write code, in any real language (i.e., not pseudocode,) to print out the permutations of a string
- dkarl 16y ago1) is what I was expecting. The solutions I saw were either attempts at 1) or attempts to do 3) using nested loops. There was also one guy who spent an hour trying to solve it with increasingly intricate methods of swapping the letters around in the string, I think because the first algorithmy thing that came to his mind was balancing binary trees. (He kept sketching the string as a tree rooted at the first letter.) Choosing C would be a pretty big fail, though honestly, people didn't struggle much with language issues. I told them it was fine if they didn't remember exact APIs, and nobody got to the point where they were worried about whether the code would parse. One guy did it in C++ using the string class, and I don't think he was at a big disadvantage. It's (evidently) harder to figure out the details of the algorithm than to write out a solution in C++.
- jules 16y agoHaving just spent half an hour to figure out (3) by swapping letters around, I think (1) may still be easier even in C because the method is straightforward. Are you using functional languages where you work? Interviewees who use a language with list comprehensions would have a significantly easier time with this question (the solution being two lines of code instead of 10+ lines of intricate letter swapping). Did any of the candidates use Python or ML or Haskell? What is the reason they didn't get it right? It may be harder to figure out idea of the algorithm than the implementation details, but in my experience you often won't even think about the high level algorithm if you are in a C++ mindset, you'll only think about swapping letters around.
- dkarl 16y agoNobody chose Python, ML, or Haskell. Some chose Perl, which I took as a promising sign, but they didn't do any better than the ones who chose C++ or Java. Actually conceiving of the solution was the roadblock for most, but the ones who got past that struggled to figure out the recursion -- what should be the signature of the recursive function?
- jules 16y agoThey couldn't even figure out the type of a function that takes a string and returns a list of permutations? That is...unexpected. One wonders how so much working software gets written.
- ericbb 16y agoWhat's so bad about C? It's not very pretty but the following was easy enough to write and worked first try. http://pastebin.com/QBAgzWWJ http://pastebin.com/QBAgzWWJ Pipe the result through "sort -u" if you don't want dups.