Quick Overview

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 a Cache Snapshot Printer

Company: Hebbia

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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: ```text A: 2 B: 2 ``` the compressed snapshot can be represented as: ```text 2 [A, B] ``` Clarify and implement how ordering should be preserved in the compressed output, especially when multiple values appear in the cache.

Quick Answer: 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.

Simulate an LRU cache with snapshot and compressed_snapshot operations. Return outputs for get and snapshot operations.

Constraints

  • Snapshots list entries from most recent to least recent.
  • Compressed snapshots group equal values in first-seen snapshot order.

Examples

Input: (3, [["put","A",2],["put","B",2],["put","C",3],["snapshot"],["compressed_snapshot"]])

Expected Output: [[['C', 3], ['B', 2], ['A', 2]], [[3, ['C']], [2, ['B', 'A']]]]

Explanation: Snapshot is most-recent to least-recent and compressed groups preserve that order.

Input: (2, [["put","A",1],["put","B",2],["get","A"],["put","C",3],["snapshot"]])

Expected Output: [1, [['C', 3], ['A', 1]]]

Explanation: Get refreshes recency before eviction.

Hints

  1. Clarify edge cases before coding.
  2. Keep the return value deterministic.

Loading coding console...