How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at MongoDB.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MongoDB during technical interviews.

Implement a thread-safe high-concurrency LRU cache

Quick Overview

This question evaluates understanding of concurrent data structures, synchronization strategies, and LRU cache semantics within the Coding & Algorithms domain, testing the ability to design an in-memory cache with O(1) average operations and explicit thread-safety guarantees.

Company: MongoDB

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem Design and implement an in-memory **LRU (Least Recently Used) cache** that supports concurrent access. ### Basic requirements Implement a cache with fixed `capacity` supporting: - `get(key) -> value | -1`: Return the value if present; otherwise return `-1`. A successful `get` marks the entry as **most recently used**. - `put(key, value)`: Insert/update the key. If the cache exceeds `capacity`, evict the **least recently used** entry. All operations should be **O(1) average time**. ### Concurrency requirements Now extend the cache so it can be safely used by **multiple threads** calling `get/put` concurrently. You should: - Define the thread-safety guarantees (e.g., linearizable operations). - Aim to **minimize lock contention** under high read/write concurrency. - Clarify how you handle races between `get` and `put` on the same key. ### Constraints (assume) - `1 <= capacity <= 10^6` - Up to `10^7` operations - Keys are hashable (e.g., integers or strings) ### Deliverables - Data structures you would use. - API and behavior under concurrency (including any acceptable trade-offs).

Quick Answer: This question evaluates understanding of concurrent data structures, synchronization strategies, and LRU cache semantics within the Coding & Algorithms domain, testing the ability to design an in-memory cache with O(1) average operations and explicit thread-safety guarantees.

Part 1: Basic O(1) LRU Cache Simulator

Implement a fixed-capacity LRU (Least Recently Used) cache. You are given the full list of operations up front and must return the results of every `get` in order. A successful `get` makes that key the most recently used. A `put` inserts or updates a key and also makes it most recently used. If inserting a new key would exceed the capacity, evict the least recently used key. Your implementation should achieve O(1) average time per operation.

Constraints

1 <= capacity <= 10^5
0 <= key, value <= 10^9
0 <= len(operations) <= 2 * 10^5
Each operation is either `('put', key, value)` or `('get', key)`

Examples

Input: (2, [('put', 1, 1), ('put', 2, 2), ('get', 1), ('put', 3, 3), ('get', 2), ('put', 4, 4), ('get', 1), ('get', 3), ('get', 4)])

Expected Output: [1, -1, -1, 3, 4]

Explanation: After get(1), key 1 becomes most recently used. Putting 3 evicts 2. Putting 4 later evicts 1. The get results are 1, -1, -1, 3, 4.

Input: (2, [('put', 2, 1), ('put', 2, 2), ('get', 2), ('put', 1, 1), ('put', 4, 1), ('get', 2)])

Expected Output: [2, -1]

Explanation: The second put updates key 2 to value 2. After inserting 1 and then 4, key 2 becomes the least recently used and is evicted. So the get results are 2 and then -1.

Input: (0, [('put', 1, 10), ('get', 1), ('put', 2, 20), ('get', 2)])

Expected Output: [-1, -1]

Explanation: A cache with capacity 0 cannot store anything, so every get returns -1.

Input: (1, [('put', -1, 5), ('get', -1), ('put', -1, 7), ('get', -1), ('put', 2, 9), ('get', -1), ('get', 2)])

Expected Output: [5, 7, -1, 9]

Explanation: Updating an existing key changes its value without increasing size. When key 2 is inserted into a capacity-1 cache, key -1 is evicted.

Hints

A hash map gives O(1) access to a key, but you also need O(1) updates to recency order.
A doubly linked list with dummy head/tail nodes makes it easy to move a node to the most-recently-used position and remove the least-recently-used node.

Part 2: High-Concurrency Sharded LRU Cache Simulator

A common way to make an LRU cache safer under high concurrency is lock striping: split the cache into independent shards, each with its own LRU list and lock. In this problem, you will implement the deterministic behavior of that design. The judge gives a linearized operation order representing one valid concurrent execution. Key `k` belongs to shard `k % shard_count`. The total capacity is split as evenly as possible across shards: shard `i` gets `capacity // shard_count + 1` entries if `i < capacity % shard_count`, otherwise `capacity // shard_count`. Each shard runs its own LRU policy, so eviction is per shard, not global. Process all operations and return the result of every `get`. If `get` and `put` target the same key, apply them in the given input order.

Constraints

1 <= capacity <= 10^5
1 <= shard_count <= capacity
0 <= key, value <= 10^9
0 <= len(operations) <= 2 * 10^5
Each operation is either `('put', key, value)` or `('get', key)`

Examples

Input: (4, 2, [('put', 1, 1), ('get', 1), ('put', 3, 3), ('put', 5, 5), ('get', 1), ('put', 1, 1), ('get', 1), ('get', 5)])

Expected Output: [1, -1, 1, 5]

Explanation: All keys map to shard 1, whose capacity is 2. Key 1 is evicted when key 5 is inserted, then reinserted later.

Input: (4, 3, [('put', 1, 20), ('put', 4, 40), ('get', 1), ('get', 4), ('put', 0, 10), ('put', 3, 30), ('get', 0), ('put', 6, 60), ('get', 6)])

Expected Output: [-1, 40, 10, 60]

Explanation: Shard capacities are [2, 1, 1]. Key 1 is evicted from shard 1 by key 4. In shard 0, getting key 0 makes it recent, so key 3 is evicted when key 6 is inserted.

Input: (2, 4, [('put', 2, 20), ('put', 1, 10), ('get', 2), ('get', 1), ('put', 5, 50), ('get', 1), ('get', 5)])

Expected Output: [-1, 10, -1, 50]

Explanation: Shard capacities are [1, 1, 0, 0]. Key 2 maps to a zero-capacity shard, so it is never stored. Keys 1 and 5 share shard 1, so 5 evicts 1.

Input: (0, 3, [('put', 0, 100), ('put', 1, 200), ('get', 0), ('get', 1)])

Expected Output: [-1, -1]

Explanation: Every shard has capacity 0, so all puts are ignored.

Input: (3, 1, [('put', 1, 1), ('put', 2, 2), ('put', 1, 10), ('put', 3, 3), ('put', 4, 4), ('get', 2), ('get', 1), ('get', 4)])

Expected Output: [-1, 10, 4]

Explanation: Updating key 1 changes its value and makes it most recently used. Later, key 2 becomes the least recently used and is evicted.

Input: (5, 2, [])

Expected Output: []

Explanation: No operations means no get results.

Hints

Reuse the LRU data structure from Part 1, but create one independent instance per shard.
Precompute each shard's capacity. The first `capacity % shard_count` shards get one extra slot.

Quick Overview