undefined | Better HN

0 pointstzs14y ago0 comments

Interesting. I'd find the permutations one trickier, and yes I've encountered permutations in math and have been a programmer a long time). Here's why I'd find it tricky.

There is an obvious recursive algorithm, but I'd be worried that if I gave that the interviewer would quibble about stack usage (although it is going to be linear in the number of items being permuted which should be OK most of the time).

Thinking a bit more, I can see that it should be possible to do an iterative algorithm that needs little or no state other than the last permutation generated and that given a sorted input string would generate the permutations in lexicographic order. The basic idea is that if you partition the string into two parts, AB, such that no permutation of B exists that is lexicographically after B, then the next permutation of AB is formed by replacing B with the lexicographically first permutation of B, and then exchanging the last character of A with the first character of the new B. (I think that will generate them all, in order--but I've not seriously analyzed it--I'm just riffing off the top of my head as I type here, like I'd be doing in an interview).

OK, now I'd worry about that step of replacing B with the lexicographically first permutation of B. That can be done by sorting B, but then the interviewer might complain about all that sorting. Aha! The lexicographically last permutation of B and the first permutation or reverses of each other, and reversal can be done in O(n). (And maybe it can be done even faster with some kind of doubly linked list to store strings as list of elements, where a string is represented by a pointer into the list, a length, and a direction flag...something to think about).

Anyway, the permutation question is fraught with potential pitfalls. I'd be smart enough, I hope, to do all the above musings out loud to give the interview a chance to jump in and tell me "It's OK...I just want to see if you can write code, so go ahead with the recursive solution".

That second problem is straightforward. It's just binary search. The rotated array doesn't change anything fundamental about it--it just slightly complicates the check to see which half the target element must lie in. There will always be at least one "normal" half--that is, a half where all the elements are sorted. You can recognize a normal half be the left endpoint being less than the right endpoint. You check for the target in a normal half the usual way. If the target is not in the normal half you check, it must be in the other half (or not in the array at all).

0 comments

aplusbi14y ago

Interestingly enough no one I've interviewed has every suggested lexicographical ordering although I have implemented it that way myself to see how hard it would be (answer: it's kind of hard).

That said, C++'s standard library has a next_permutation function that returns the lexicographical next permutation of a pair of iterators (actually it does it in-place and returns a bool). If a candidate used that I'd allow it (as long as there was some discussion as to how it worked).

I've since stopped asking that question and now stick primarily with the split array question as I think it's less tricky. There's more than one way to solve it and most of the solutions build up on simpler solutions which makes for good discussion. I also don't ask for actual code for that problem unless I get the feeling the candidate will understand the problem better by expressing it in code.

eropple14y ago

Given that I've been back in C++ mode for the last week, this is exactly what I was considering (using next_permutation). ;)