A friend of mine interviewed for MS around the same time, albeit for a senior-ish position, and his question required knowing Fibonacci trees.

It wasn't an abstract CS flex on interviewer's part either, because apparently the fib trees were actually used in some part of the FrontPage.