[manfredo]

It's almost always a combinations of:

* Searching algorithms

* Sorting algorithms

* Dynamic Programming (memoization)

* Graph operations (traversal, best path, minimum spanning set)

* Maps & Hashing.

* Heaps or trees. E.g. finding a median or top-k elements.

Every once in a while you'll get a more exotic problem that requires something like a bloom filter or a trie.

But that's just enough to get the solution. A good interviewer will also see if you can build this solution in a way that has effective abstractions. They'll also probe real-world concerns like data locality. For instance, one solution might be better in terms of big-O notation performance but might have worse access data pattern than other solutions.