Monthly Archive for November, 2013

Breadth-First Traversal with Alternating Directions at Each Level

Yesterday I discussed the interview coding problem I blew: Code, in Java, a breadth-first traversal of a binary tree, alternating directions at each level.

TestTree

The key observation is obvious: At each level you process nodes in the reverse order of the previous level.  (Duh! That’s the problem statement.)  To turn it around: At each level you must preserve for later processing the child nodes in reverse order of the nodes you’re processing at this level.  A data structure which let’s you pull off nodes in reverse order in which you saved them is a stack, one of the simplest data structures of all. Continue reading ‘Breadth-First Traversal with Alternating Directions at Each Level’

Two coding interview questions done badly, for different reasons

In my recent job search I was asked very few coding questions.  Not sure why not—I was interviewing for individual contributor roles as per usual.  Anyway, two coding questions stand out for basic errors I made. One was at the whiteboard, one was a “homework” problem.

The whiteboard problem had a very simple statement: Code, in Java, a breadth-first search, but switch the traversal direction at each level.  A nice twist on a typical problem!  I did it by inserting a sentinel into the standard queue of pending nodes.  Using a Java Queue<Object> I inserted an (arbitrary) Integer as the flag, but it would have been just as reasonable to use a Queue<Node> and insert the tree root as sentinel.  Remember to check for termination: if you’ve just dequeued the sentinel then if the queue size is zero, you’re done.  Very short and sweet—but wrong! It hit me like a ton of bricks as soon as I drove off!  It doesn’t traverse alternate levels in different directions, but only the nodes of alternate levels in different directions.  Bungled!  The error, my fault, was that I didn’t fully work things out, with an example, before I started coding.  Had I, I would immediately have caught my error.  In my defense, the interviewer and I were under very tight time constraints-it was a screening interview, it started late (scheduling mishap at their end), and we did a bunch of design questions first.  On the other hand, he seemed very happy with the solution: he complimented it and said I would be invited back for a full loop (though I bailed on that for unrelated reasons).  (Anyway, the correct solution. which immediately followed my shocking realization, is here.)

Now, what is it that you should never do with an interview homework problem? Continue reading ‘Two coding interview questions done badly, for different reasons’