Implement a Cache Snapshot Printer
Problem Description
Implement an LRU-style cache with a fixed capacity that stores key-value pairs.
Cache Operations
The cache must support the following operations:
- Insert/Update: Add a new key-value pair or update an existing key's value. This operation should mark the key as most recently used.
- Read: Retrieve the value associated with a given key. This operation should also mark the key as most recently used.
- Eviction: When the cache capacity is exceeded upon insertion, the least recently used entry must be evicted.
Snapshot Feature
Add a function, snapshot(cache), that returns a printable representation of the current cache contents. The entries in the snapshot should be ordered by recency, from most recently used to least recently used.
Compressed Snapshot Feature
Extend the snapshot logic to support compressed output. Given a mechanism or utility for compression, group entries that share the same value.
For example, if the cache contains A: 2 and B: 2, the compressed snapshot should represent this as 2 [A, B].
Crucially, clarify and implement how the recency ordering should be preserved in the compressed output, especially when multiple distinct values appear in the cache.
AI interview prep
Core dilemma
Balancing the O(1) efficiency requirements of a standard LRU cache with the need to efficiently generate ordered snapshots (both uncompressed and compressed), which may require iterating or maintaining auxiliary data structures, potentially impacting performance or memory footprint.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Implement a Cache Snapshot Printer
Problem Description
Implement an LRU-style cache with a fixed capacity that stores key-value pairs.
Cache Operations
The cache must support the following operations:
- Insert/Update: Add a new key-value pair or update an existing key's value. This operation should mark the key as most recently used.
- Read: Retrieve the value associated with a given key. This operation should also mark the key as most recently used.
- Eviction: When the cache capacity is exceeded upon insertion, the least recently used entry must be evicted.
Snapshot Feature
Add a function, snapshot(cache), that returns a printable representation of the current cache contents. The entries in the snapshot should be ordered by recency, from most recently used to least recently used.
Compressed Snapshot Feature
Extend the snapshot logic to support compressed output. Given a mechanism or utility for compression, group entries that share the same value.
For example, if the cache contains A: 2 and B: 2, the compressed snapshot should represent this as 2 [A, B].
Crucially, clarify and implement how the recency ordering should be preserved in the compressed output, especially when multiple distinct values appear in the cache.