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?