Designing data structures

Design problems ask you to support a set of operations, each within a cost. Write the list of operations and costs first. An LRU cache needs: look up a key, mark it as most recently used, insert, and evict the least recently used entry. A hash map finds entries. A doubly linked list keeps the order and lets you remove or insert an entry in O(1) once you've found it.

What must stay true covers both structures at once. Every key in the map has exactly one node in the list, every node has exactly one map entry, and the list order matches how recently each key was used. Updating one structure without the other is a bug, even if each looks fine on its own.

A randomized set combines a list, so you can pick a random index, with a hash map from each value to its index. To delete, move the last value into the deleted spot, update the moved value's index, and pop the end. The map and list must always agree on every value's index. Forgetting to update the moved value's index breaks later deletions.

A min stack can store, with each value, the minimum of everything at or below it. That keeps repeated minimum values correct after one is popped. A queue built from two stacks takes O(1) time per operation on average, because each element moves between the stacks at most once.

In Rust, storing nodes in a vector and linking them by index is often simpler than shared mutable pointers. If you reuse slots, you may need a version number so that old handles are caught. Pick a representation that supports the operations and their costs; code that's easy to write doesn't replace the cost argument.

Practice: LC 146 LRU Cache, LC 380 Insert Delete GetRandom O1, LC 155 Min Stack, LC 232 Implement Queue using Stacks, LC 981 Time Based Key Value Store.

Check your understanding: What ties the structures together? What happens when you insert a key that already exists? What happens when the structure is empty, or its capacity is zero? Is each cost worst-case, average, or averaged over many operations?