I've heard from one senior engineer at Google that he likes to ask candidates to sketch out the implementation for a red/black tree on the spot.
I guess I could go dig up my old data structures and algorithms book that I haven't touched in 15 years to refresh my memory, but I don't want to work at Google badly enough to bother with that.