Katkat
Back

Implement a Cache Snapshot Printer

HebbiaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of LRU cache semantics, data structures for maintaining recency and eviction, and techniques for serializing or compressing state by grouping identical values while preserving ordering.

Implement an LRU-style cache and a snapshot-printing feature.

The cache stores key-value pairs and has a fixed capacity. It should support normal cache operations such as inserting/updating a key and reading a key. When the capacity is exceeded, the least recently used entry should be evicted.

Add a function snapshot(cache) that returns a printable representation of the current cache contents in recency order.

Then extend the snapshot logic to support compressed output. Given a compression utility, group entries that have the same value. For example, if the cache snapshot contains:

A: 2
B: 2

the compressed snapshot can be represented as:

2 [A, B]

Clarify and implement how ordering should be preserved in the compressed output, especially when multiple values appear in the cache.