> Did you have to prepare for that?

Yes, I found it valuable/important to study basic data structures and algorithms before my interviews. Specifically, I read Wikipedia articles and worked through problems in Programming Interviews Exposed, although there are probably many better resources available these days.

Algorithmic questions, while often not very representative of the work that you'll do as a dev, are really common interview questions at many companies. I think this is in part because they're usually well encapsulated and don't require extra context/specialized knowledge. They're also usually not very programming language-dependent.