Implement a Cache Snapshot Printer
Company: Hebbia
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
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
- Clarify edge cases before coding.
- Keep the return value deterministic.