Couldn't disagree more with the author. How many developers need to implement their own binary-tree? This is why code-bases become convoluted with six different implementations of standard data structures.
So this article leads off with @mxcl's tweet about google not offering him a job because he wasn't able to reverse a binary tree on a whiteboard.
I don't think that being able to describe an algorithm you haven't had to implement in more than decade (at least, that would be the case for me, college is starting to be a long time ago for me).
Honestly right now, without looking up the answer, I probably can't reverse a binary tree on a whiteboard. I could, however, do it by test driving a solution with a real computer (I haven't flexed those muscles in a long time, but test driving would help me dig into the recesses of my brain).
Which skill set is more useful for production quality software? I can say for sure that it's not white boarding.
Deriving trivially provable algorithms in a test-driven way, by trial and error, hoping that no edge cases are missed? Sounds really, really depressing. The future of software engineering is very bleak if this approach is a new norm.
My point was that I would start by test driving to "dust off the cobwebs", as it were.
Personally, I don't actually believe in truly "mindless", trial and error TDD, as oftentimes it will miss the forest for the trees.
Amusingly now, three days later, I'm certain I could do this nonsense on a whiteboard now, as thinking about it three days ago seems to have primed my subconscious to dig it up.
Reversing a binary search tree is a binary (pun intended) answer: you either know how to do it because you learned it in college/read Cracking the Coding Interview, or you don't.
What? You do not need to know anything at all. The very wording of this problem is already a solution. No thinking required. No prior knowledge required.
They also teach things like this in boot camps now. The graduates are trained to game these tests because placement rates are so important to boot camps.
Assuming someone is a good programmer because of trivial examples like reversing a binary tree or, worse, writing a bubble sort is like asking someone you to use a wrench to prove that you're an architect.
But surely an example question with only 2 right answers doesn't give you a good cross-section of the person's understanding. What if they understand the reverse relationship but choose the more concise option for many other reasons. The desire to understand a developer's thinking is good. This question does not well accomplish that goal.
That's a really big obstacle, but it's not insurmountable. My companies often ask if the candidate is willing to be a contractor for a couple of weeks. If they're not currently working, it gives them some income to continue the job search, and it allows us to see what it's like working with them.
I can usually tell that someone is unacceptably bad within a few days of working with them, so it makes sense to do those few days before hiring (if possible).
Imagine you have one position, and 15 people were screened for an interview. What would you do with 15 contractors? Even if you run a Microsoft department it would not make much sense.
Trivial problems are a good filter, as long as you manage to maintain a non-stressful interview environment. Whiteboard coding is a good thing, because it shows that one really understands things, not just memorised keystrokes.
Doing about 80% of my work on a piece of paper, I cannot really comprehend all the moaning about whiteboard being "detached" from anything practical.
Even if a developer did need to implement a binary tree, she wouldn't be doing it in a high-pressure, interview setting, nor would she be doing it using a marker on a white board.
Furthermore, the business value of a programmer is rarely how she writes code in isolation. It's how she writes code on a team. I'd take a B-level programmer who is excellent at writing clean, readable, simple code over someone who is a savant at white-board problems.
"To use a library effectively, you have to be able to write it."
That's a blanket statement. If we find one exception to this rule, then we can say that it's 100% false (since its truthfulness is binary -- it's either true or false).
To find one exception, we only need to find a single "good" piece of software whose author can't write 100% of the dependencies, including: (probably) C/C++ compilers, FS drivers, low-level network libraries, and the widely-used monster that is SSH.
You're not 100% wrong but you chose the wrong examples.
Compilers & drivers aren't libraries. Low-level network libraries, using libuv as an example, have concurrency gotchas that require awareness on the part of the app developer. Using TCP as an example, think of the pain people go through over nagling.
Security software is the best example of something we use without understanding but it has gotchas; you need a nontrivial understanding of the internals to guard against sidechannel attacks.
Trees are the single most important data structure in computer science. Just
about everything you do in your programming career will be related to trees.
Trees are a horrid data structure for any modern processor. Pointer chasing thrashes caches. The actual most important data structure is a hashmap. The same speed in theory, much faster in practice.
This depends a lot on data size & shape. There've been some applications where I benchmarked a std::map (a tree, in practice) against Google's highly-tuned hashmap for a small (~25-50 item) container and the tree came out ahead. For such a small data structure, everything fit in L1 cache, and comparisons to follow pointers could usually be resolved by looking at the first word of the key.
One thing often forgotten with hashmaps is that they aren't actually O(1); they're O(k), where k is the length of the key, and often need to examine the entire key to derive a hashcode. This oftentimes makes them significantly slower than a binary search tree when the size of the key is large compared to the size of the container.
I believe continuation-passing style is an alternative to the direct style you mention. Return-oriented programming and threaded programming may be specific counter-examples.
Depending on your problem domain, you might be able to flatten it by just combining keys together (subject to keys being combinable like with string concatenation, using separators to ensure uniqueness of combined keys, etc.)
E.g., turn {"foo": {"bar": "moop"}} into {"foo-bar": "moop"}. This also requires writing accessor fns, but it might be worth it, depending.
Right, that works fine so long as you only ever go up the hierarchy, but going down the hierarchy would require a prefix search, which is the one place where trees actually do win over hashes.
The author says that the candidate's thought process behind arriving at the solution provides insight into the candidate's skill.
There's no reason to implement your own binary tree, but knowing how to devise algorithms to accomplish a given task is a necessary competency.