Algorithm dossier

  • Category: Hashing
  • Worst-case complexity: O(1)
  • Approach: Iterative
  • Data structure: Hash table
  • First formalised: 1960s

Why this snippet is LRU Cache

Why LRU cache. Two operations — get(k) and put(k, v) — both O(1) amortised. The trick is the *insertion-ordered* container: every access bumps the key to the most-recently-used end, and overflow evicts from the least-recently-used end. Implementation. Classic interview version is a hash map + doubly linked list; this Python form leans on OrderedDict, which is exactly that combination under the hood. Memcached, Redis maxmemory-policy=allkeys-lru, every CPU L1, every browser tab cache — all LRU at the core.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.