# Design an LRU Cache with a Constant-Time Average Design an in-memory cache with fixed positive capacity. Keys are unique strings and values are signed numbers. Support: - `get(key)`: return the value and mark the key most recently used, or report a miss. - `put(key, value)`: insert or update the key and mark it most recently used; if over capacity, evict the least recently used key. - `get_average()`: return the arithmetic mean of values currently in the cache, or a documented empty result. All three operations should take expected `O(1)` time. Explain invariants, numeric choices, and edge cases rather than relying on an ordered-map library as a black box. ### Constraints & Assumptions - Capacity never changes after construction. - Updating an existing key replaces its value and changes recency. - The average covers current entries, not historical requests. - Thread safety is not required for the initial design. ### Clarifying Questions to Ask - Are values integers or floating point, and what precision is expected? - Does a miss change recency or affect the average? - What should `get_average` return for an empty cache? - Are overflow and concurrent calls in scope? ### What a Strong Answer Covers - A hash map paired with a doubly linked recency list - A running sum updated on insert, replacement, and eviction - Correct movement, unlinking, and eviction invariants - Expected-time, space, precision, and overflow analysis - Tests that check both recency and aggregate correctness ### Follow-up Questions - How would you add TTL expiration without scanning the cache? - How would a dynamic capacity change work? - How would you make operations thread-safe and linearizable? - What changes if values are vectors rather than scalars?