I just did a ‘Technical Interview’ for a San Francisco start up. This type of interview seems to be common in the US when looking for programmers. Despite being a complete flop at it myself, and this is the second time in my life I’ve been put through such – flopped that one too, I very much appreciate the concept. To make myself feel better I like to think there are very few guys I’ve worked with (in Sydney) who would be able to get this on the spot. If I could learn how to get through these tests then perhaps I’d actually get to work with some people who know what they’re doing.
Anyway, after a five minute preamble, the guy (I won’t name names as he may be very well known in some circles) poses a puzzle. Important lesson to remember when getting this puzzle is: you have to solve it. You might be super bright and solve it in five minutes, or you might not be thinking clearly and need an hour. The interviewer is not going to move on until you actually solve it. That was unexpected. I knew the guy knew a few solutions so I was just kinda phaffing about waiting for him to get bored of waiting for me so then he could jump in and show me the answer. Any other kind of situation I know this doesn’t take long because people are always keen to show off how smart they are 
If/when I get into this situation again I’ll have to resign myself to doing the groundwork to solving the puzzle. But in this case, by the time I worked out that he wasn’t going to jump in and give me the answer I was all ready for the earth to open up and swallow me, but I digress…
The puzzle is perhaps a classic, at least it sure smells like a tried and true trick for sorting sheep and goats.
A tree of nodes. Each node has a label (eg "A") and some children. Write an iterator "next" such that it returns A, B, E, H, O, F, G, H, C, I, J, K, P, Q, D, L, M. You'll want to create a constructor for the iterator. Each node knows who its parent is.
Sounds easy, and probably is. I couldn’t do it. Still haven’t solved it!
I mean I think I can walk the tree to get the right result easily enough like this:
walk (node) {
print node;
foreach child of node
walk (child);
}
But the ‘next’ node is still out of grasp; perhaps this is where the initializer comes in; to keep state in the walk you’re on? I was instructed that the tree might be dynamic which ruled out walking the tree in the initializer then stepping through that list with each call to next(). The real trick seems to lie in finding the next() of Q; ie D via the arbitrarily deep ancestor A. I went to google and found some uni lecture notes which place a stack in the iterator which must be the solution which I never came close to finding.
How about FIFO queue?
1) Start of by putting the parent node into the FIFO queue
2) Pop the first element (at this point parent node) from the FIFO queue, print the content ‘A’,
and place its children (‘B’, ‘C’, ‘D’) into the FIFO queue.
3) Pop another element off the queue (now, ‘B’) print content and add its children to the FIFO queue (the queue now holds ‘C’, ‘D’, ‘E’, ‘F’, ‘G’, ‘H’), continue until no more nodes left.
THere’s clearly a recursive function above…
I would at this point point out to the interviewer that that’s a pretty crappy way of building a tree and whoever programmed the code to construct the tree should be shot.
I too hate those sort of programming interviews but such is life.
Btw, the above took me about 5 minutes, but hey, it’s a Saturday and I don’t have someone staring at me
Submitted too early. What I was trying to say, it’s something you need to have time and be in the right frame of mind, to solve.
To do the same under interview conditions, is just insane. Employers may be missing out on some very good programmers…
Umm, the order it prints out is the basic depth first search of that tree. This should be a simple tree traversal loop you learn in first year comp-sci… I prefer the puzzle tests that are actualy puzzles and can be solved with some inginuity. This however, is hardly a puzzle. The interviewer is simply checking if you know how to do a depth first search. Something many AI coders, among others, do for various reasons regularly.
Also, it would help if you stated the problem correctly in your post.
You have: A, B, E, H, O, F, G, H, C, I, J, K, P, Q, D, L, M
You ment this: A, B, E, N, O, F, G, H, C, I, J, K, P, Q, D, L, M