[glaak]

It depends on how you look at it.

Google wants people who have a strong understand of CS fundamentals (which includes knowing core data structures). Google also wants people who are good coders (which includes being able to translate an idea into code).

A good coder who knows CS fundamentals should be able to do that. Thus, not knowing how to implement a binary search tree is revealing.

And, really, the question is rarely "implement a binary search tree." It may, however, be to implement a binary search tree which support a getMedian() operation.

[Evbn]

Of course, not knowing how to write a library quality Java w/generics implementation of a a search API on a non-search tree, on the whiteboard, as one of my interviewers once demanded, is something a bit else.