Walking trees on a whiteboard is a poor test of this ability. I'd much rather hear how somebody would decompose a real world problem into workable abstractions. A knack for designing clean architectures counts much more than algorithmic cleverness in 9 out of 10 actual programming jobs.
They're probably nervous because you've asked them to solve a weird problem they've never had to solve in the real world. Have you actually written, in shipping code, a single-linked list or an elementary algorithm to operate on one?
Unless you want them to implement a compiler or something, I think you'll learn a lot more about somebody's programming abilities by asking them to turn a list of use cases into a class diagram or write out a few SQL queries given for a given set of tables.
"A compiler or something" huh? Let's see. Would you hire someone who couldn't reverse a linked list, if you wanted to develop...
Google Chrome?
Adobe Photoshop?
Crysis 2?
An IPad?
A self-driving car?
Not all programming is boring business stuff with SQL and class diagrams. And even "boring" apps may be more tricky than they look: Microsoft Excel had its own bytecode interpreter, which definitely qualifies as "a compiler or something" :-)
>Have you actually written, in shipping code, a single-linked list or an elementary algorithm to operate on one?
Yes, I have. Admittedly, I had to do it much more often when STL was a toy.
But this is not the reason for this question, this is simple coding exercise, if a candidate can't do it without bugs in 10 minutes, there is nothing to talk about. Of course jobs not requiring writing C++, Java, C#, or Python code need different set of questions.
