Design an LRU Cache
Difficulty: Hard · Pattern: Design · Concept: General Coding (DSA) — Core Patterns to Drill
Design a Min Stack needed one derived value kept in lockstep with a single structure. An LRU (Least Recently Used) Cache is harder in a different way: it has a fixed capacity, and needs two operations — get(key) and put(key, value) — where every access reorders things. A cache hit moves that key to "most recently used"; when a put would exceed capacity, whichever key is currently least recently used gets evicted to make room.
Your task: implement a LRUCache class with __init__(self, capacity), get(self, key) (return the value, or -1 if not present — and count as a "use," moving that key to most-recently-used), and put(self, key, value) (insert or update; if this would exceed capacity, evict the least-recently-used key first).