How does an LRU cache work internally?

Question presented to candidate: "Design a cache with a fixed capacity that throws away the least recently used item when it is full. Both get and put should be O(1). How does it work inside, and how does Python's own functools.lru_cache do it?"

What a strong answer should cover:

• The policy: every get hit or put marks a key as most recently used; when the cache is full, the least recently used key is evicted.
• The data structures: a hash map from key to node for O(1) lookup, plus a doubly linked list ordered by recency for O(1) move-to-front and evict-from-back; sentinel nodes remove edge cases.
• Why both are needed: a dict alone cannot cheaply find the oldest key after reorderings (unless you use its insertion order), a list alone cannot find a key in O(1).
• Python shortcuts: OrderedDict.move_to_end() and popitem(last=False), or a plain dict with pop and re-insert, since dicts keep insertion order.
• How functools.lru_cache does it in CPython: a C type with a dict plus a circular doubly linked list around a root sentinel; arguments become the key (must be hashable); cache_info() reports hits and misses; maxsize=None skips the list entirely.

Clarifying questions expected:

• What is the capacity, and what should get return on a miss?
• Does put on an existing key count as a use? Is thread safety required?

Code / implementation expected: Yes — an O(1) LRU class, usually with a dict plus a hand-written doubly linked list, or with OrderedDict if allowed.