Cache Trade-offs and a Constant-Time Least-Recently-Used Cache

Problem Statement

In latency-sensitive financial systems, caches are frequently placed in front of slow data stores (such as relational databases or external market data feeds) to optimize read latency. However, introducing a cache comes with trade-offs regarding data freshness, consistency, eviction overhead, and memory consumption.

Implement an in-memory Least Recently Used (LRU) Cache with a fixed capacity that satisfies the following interface:

class LRUCache:
    def __init__(self, capacity: int):
        """Initialize the cache with a positive capacity."""
        pass

    def get(self, key: int) -> int:
        """Return the value of key if it exists, otherwise return -1.
        Accessing an existing key marks it as most recently used.
        """
        pass

    def put(self, key: int, value: int) -> None:
        """Update key with value if it exists. Otherwise, insert key-value pair.
        If number of keys exceeds capacity, evict the least recently used key.
        Both insertions and updates mark the key as most recently used.
        """
        pass

Both get and put operations must run in O(1) average time complexity.

Input & Output Format

• The constructor receives a single integer capacity.
• get(key) returns an integer value or -1.
• put(key, value) returns None.

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 total calls will be made to get and put.

Example

cache = LRUCache(2)
cache.put(1, 10)  # cache is {1: 10}
cache.put(2, 20)  # cache is {1: 10, 2: 20}
cache.get(1)       # returns 10, key 1 becomes most recently used
cache.put(3, 30)  # capacity exceeded; evicts key 2; cache is {1: 10, 3: 30}
cache.get(2)       # returns -1 (not found)
cache.put(4, 40)  # capacity exceeded; evicts key 1; cache is {3: 30, 4: 40}
cache.get(1)       # returns -1 (not found)
cache.get(3)       # returns 30
cache.get(4)       # returns 40

Edge Cases to Consider

• Capacity of 1: Every insertion of a new key must evict the previous key immediately.
• Updating an existing key should update its value and refresh its recency without changing the total count of keys.