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.
I can totally relate. When a Google recruiter approached me and told me that they were looking for Python and also Java developers I was potentially interested in the python position (being a Ruby dev). But then I learned that my interview would be conducted in Java and they would generously give me 1 week to brush up my Java skills, I laughed and declined. Definitely got other things to do with my evenings than brushing up my Java skills so I can work a Python job...
Really? The general policy, as I've been told, is to let the interviewee use whatever language they're comfortable with as long as the interviewer is comfortable with it too. I even give the option of using sufficiently detailed pseudo-code.
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.