Some examples. They’re vague because they were work for employers:
-
A heap to get the top N results in a Google-style search. (Starting from candidates in an index, go through them all linearly, sifting them through a min-heap of max size N.) This was for an image-search prototype.
-
Bloom filters cut the size of certain data about what millions of users had seen down to an amount that’d fit in existing servers (it all had to be in RAM for speed); the original design would have needed many new servers just for that database.
-
A triangular array representation halved the size of a dense symmetrical array for a recommendation engine (RAM again for the same reason).
-
Users had to be grouped according to certain associations; union-find made this easy, quick, and exact instead of slow, hacky, and approximate.
-
An app for choosing retail sites according to drive time for people in the neighborhood used Dijkstra shortest-path with priority queues. Other GIS work took advantage of quadtrees and Morton indexes.
Knowing what’s out there in data-structures-land comes in handy — “weeks in the lab can save you hours in the library”. The bloom-filter case was only worthwhile because of the scale: if the problem had come up at a startup instead of Yahoo, I’d have used a plain old hashtable. The other examples I think are reasonable anywhere (though nowadays you’re less likely to code them yourself).