[sanderjd]

I'm not the biggest fan of the algorithm-theory centric hiring regime, but "implement a red black tree" is a straw man. Even the most CSy interviews are at the level of contiguous vs. linked data structures, binary trees, and recursion, not at the level of very specific algorithms with intricate details like red black trees.

[mavelikara]

> I'm not the biggest fan of the algorithm-theory centric hiring regime, but "implement a red black tree" is a straw man.

I think it comes from the "Get that job at Google" blog post[1] by Steve Yegge. It is not clear what Steve means here, but he wrote:

  You should be familiar with at least one flavor of balanced 
  binary tree, whether it's a red/black tree, a splay tree or 
  an AVL tree. You should actually know how it's implemented.

I understand the gist of a R-B tree, I can probably write the immutable one on a whiteboard, but I don't think I will ever be able to implement the mutable insert/delete methods on a whiteboard. I have never been asked it in an interview yet, though.

[1]: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-goog...