Was this part of the interview challenging? Seems to me like a surprise data structure coming up in an interview could be a bad thing (in terms of doing well).

Edit: What have your other interview experiences been like? Similar to Google, or would different/more preparation be required?

Also, what level are you at/interviewing for at these companies?