[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...