Implement and Analyze an LRU Query Cache

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem Implement a fixed-capacity least-recently-used cache for database query results. A successful `get` and every `put` make the key most recently used. When insertion exceeds capacity, evict the least recently used key. ### Function Contract Implement `runLRU(capacity, operations)`: - `["get", key]`: return the stored integer value, or `null` if absent. - `["put", key, value]`: insert or update and return `null`. ### Constraints & Assumptions - `1 <= capacity <= 100,000`. - At most `500,000` operations are supplied. - Keys and values are signed 32-bit integers. - Updating an existing key does not increase cache size. - Each operation should be `O(1)` expected time. ### Clarifying Questions to Ask - Does a cache hit refresh recency? Yes. - Does updating an existing key refresh recency? Yes. - What is returned on a miss? `null`. - Is concurrent access part of the implementation? No, discuss it as a follow-up. ```hint Pair lookup with order A hash map provides key lookup, while a doubly linked list supports constant-time removal and movement at both recency ends. ``` ### Example ```text capacity = 2 operations = [["put",1,10], ["put",2,20], ["get",1], ["put",3,30], ["get",2], ["get",3]] output = [null, null, 10, null, null, 30] ``` Key `2` is evicted because the hit on key `1` refreshed it. ### Evaluation Focus - Keeps map and linked-list state consistent on every path. - Moves hits and updates to the most-recent end. - Evicts exactly one least-recent entry when necessary. - Delivers expected `O(1)` get and put. ### Extensions to Discuss 1. How would a sequential scan of unique user IDs affect the hit rate? 2. Which locking or sharding strategies support concurrency? 3. How would rising traffic change capacity, admission, and cache topology?

Overview: Implement a fixed-capacity least-recently-used cache for integer query results with expected constant-time get and put operations. Refresh recency on hits and updates, evict the correct key on overflow, and handle misses and duplicate puts precisely.

Problem

Implement a fixed-capacity least-recently-used cache for database query results. A successful get and every put make the key most recently used. When insertion exceeds capacity, evict the least recently used key.

Function Contract

Implement runLRU(capacity, operations):

["get", key] : return the stored integer value, or null if absent.
["put", key, value] : insert or update and return null .

Constraints & Assumptions

1 <= capacity <= 100,000 .
At most 500,000 operations are supplied.
Keys and values are signed 32-bit integers.
Updating an existing key does not increase cache size.
Each operation should be O(1) expected time.

Clarifying Questions to Ask Guidance

Does a cache hit refresh recency? Yes.
Does updating an existing key refresh recency? Yes.
What is returned on a miss? null .
Is concurrent access part of the implementation? No, discuss it as a follow-up.

Example

capacity = 2
operations = [["put",1,10], ["put",2,20], ["get",1],
              ["put",3,30], ["get",2], ["get",3]]
output = [null, null, 10, null, null, 30]

Key 2 is evicted because the hit on key 1 refreshed it.

Evaluation Focus

Keeps map and linked-list state consistent on every path.
Moves hits and updates to the most-recent end.
Evicts exactly one least-recent entry when necessary.
Delivers expected O(1) get and put.

Extensions to Discuss

How would a sequential scan of unique user IDs affect the hit rate?
Which locking or sharding strategies support concurrency?
How would rising traffic change capacity, admission, and cache topology?