The setup is straightforward: cache query results in memory to avoid redundant database hits. But the implementation gets tricky fast.

Most people start with a Vec for storage. Works fine, passes correctness tests, but doesn't scale. Then they add a HashMap for O(1) lookups, which helps. But now you need eviction when the cache fills up.

This is where it gets interesting. LRU eviction means tracking access order. You could shuffle a VecDeque around, but that's still O(n). The real solution needs two structures working together: HashMap for lookups and a doubly linked structure for LRU updates, both at O(1).

Building that in safe Rust with no external crates becomes the actual challenge. You're fighting the borrow checker because you need bidirectional references. Some people use indices instead of pointers. Others build intrusive lists with generational indices. A few discover std::collections::LinkedList and then realize it doesn't quite fit.

Contest link if you want to try it (90 to 120 min, standard library only): https://cratery.rustu.dev/contest