As an engineer who works on security software, here's what I've empirically used on the job:

1. Tree/graph traversal (certificate validation and a couple other random places)

2. Using, not implementing, hash tables

3. Generators/iterators/streams: minimizing the number of unnecessary list traversals or allocations made when you have to shovel data around

4. Circular buffers: specifically in low latency, high throughput applications

5. Some exotic string search algorithms in a very specific, highly performance sensitive inner loop

6. Database query performance tuning

7. Every now and then something vaguely reminiscent of dynamic programming comes up, but it's never an actual dynamic programming problem, it's just a "cache results of expensive operations" problem.

For my job you need something exotic once in a blue moon, and when that happens you Google for someone else's research. You're not making up algorithms on your own. If you want to test that someone can handle algorithm-heavy situations like case #5, you should be testing their paper reading and ability to implement that paper, not their ability to solve an algorithms puzzle.

Also relevant to my job: if you find yourself implementing cryptographic algorithms, you're almost certainly doing it wrong. You shouldn't be implementing cryptographic algorithms. When I need them, my job is to vet and correctly use an expert implementation.