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.

Could you provide some examples of questions you were asked?

I majored in entrepreneurship so my idea of "CS fundamentals" may be different from yours, but I took Harvard's CS50 class and felt that it provided a very good introduction to CS.