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 Uber.

What role is this question designed for?

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

Design and Implement an LRU Cache | Uber Coding Question

Quick Overview

This question evaluates a candidate's ability to design and implement an LRU cache data structure with O(1) time complexity for both reads and writes. It tests practical knowledge of combining hash maps with doubly linked lists, a core data structures and algorithms topic frequently used to assess low-level design and implementation skills in software engineering interviews.

Design and Implement an LRU Cache

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Design and Implement an LRU Cache Design a data structure that implements a **Least Recently Used (LRU) cache** with a fixed positive capacity. The cache stores integer keys mapped to integer values and must support both operations in **average O(1) time**. Implement a class `LRUCache` with the following interface: - `LRUCache(capacity)` — Initialize the cache with a positive integer `capacity` (the maximum number of key/value pairs it can hold). - `get(key)` — Return the value associated with `key` if it is present in the cache; otherwise return `-1`. A successful `get` counts as a use of that key (it becomes the most recently used). - `put(key, value)` — Insert or update the value for `key`. This counts as a use of that key (it becomes the most recently used). If inserting a new key would exceed `capacity`, **evict the least recently used key** before inserting the new one. "Use" of a key means: any successful `get`, and any `put` (whether it inserts a new key or updates an existing one). The least recently used key is the one that has gone the longest without being used. ### Example ``` LRUCache cache = new LRUCache(2); // capacity = 2 cache.put(1, 1); // cache: {1=1} cache.put(2, 2); // cache: {1=1, 2=2} cache.get(1); // returns 1; key 1 is now most recently used -> cache order: {2=2, 1=1} cache.put(3, 3); // capacity exceeded -> evict key 2 (least recently used); cache: {1=1, 3=3} cache.get(2); // returns -1 (key 2 was evicted) cache.put(4, 4); // capacity exceeded -> evict key 1; cache: {3=3, 4=4} cache.get(1); // returns -1 (evicted) cache.get(3); // returns 3 cache.get(4); // returns 4 ``` ### Constraints - `1 <= capacity <= 3000` - `0 <= key <= 10^4` - `0 <= value <= 10^5` - At most `2 * 10^5` total calls will be made to `get` and `put`. - Both `get` and `put` must run in average O(1) time per call. ### Required interface ``` class LRUCache: def __init__(self, capacity: int): ... def get(self, key: int) -> int: ... def put(self, key: int, value: int) -> None: ... ```

Quick Answer: This question evaluates a candidate's ability to design and implement an LRU cache data structure with O(1) time complexity for both reads and writes. It tests practical knowledge of combining hash maps with doubly linked lists, a core data structures and algorithms topic frequently used to assess low-level design and implementation skills in software engineering interviews.

Design a data structure that implements a **Least Recently Used (LRU) cache** with a fixed positive capacity. The cache stores integer keys mapped to integer values and must support both operations in **average O(1) time**. Implement a class `LRUCache` with the following interface: - `LRUCache(capacity)` — Initialize the cache with a positive integer `capacity` (the maximum number of key/value pairs it can hold). - `get(key)` — Return the value associated with `key` if it is present in the cache; otherwise return `-1`. A successful `get` counts as a use of that key (it becomes the most recently used). - `put(key, value)` — Insert or update the value for `key`. This counts as a use of that key (it becomes the most recently used). If inserting a new key would exceed `capacity`, **evict the least recently used key** before inserting the new one. "Use" of a key means: any successful `get`, and any `put` (whether it inserts a new key or updates an existing one). The least recently used key is the one that has gone the longest without being used. ### Driver harness (how your code is invoked) To make this runnable, you implement a single function `solution(operations, inputs)` that simulates a sequence of method calls: - `operations` is a list of strings, each one of `"LRUCache"`, `"get"`, or `"put"`. - `inputs` is a list of argument lists, parallel to `operations`. - `"LRUCache"` → `[capacity]` (this is always the first operation). - `"get"` → `[key]`. - `"put"` → `[key, value]`. Return a list of the same length as `operations`. For each call append: `None` for the `"LRUCache"` constructor and for every `"put"`, and the returned integer (the value or `-1`) for every `"get"`. ### Example ``` operations = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] inputs = [[2], [1,1], [2,2], [1], [3,3], [2], [4,4], [1], [3], [4]] returns [None, None, None, 1, None, -1, None, -1, 3, 4] ``` Walkthrough: `put(1,1)` → {1=1}; `put(2,2)` → {1=1,2=2}; `get(1)` → 1, key 1 becomes most-recently-used; `put(3,3)` exceeds capacity → evict key 2 (LRU) → {1=1,3=3}; `get(2)` → -1; `put(4,4)` → evict key 1 → {3=3,4=4}; `get(1)` → -1; `get(3)` → 3; `get(4)` → 4.

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 total get and put calls.
Both get and put must run in average O(1) time per call.

Examples

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

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

Explanation: The worked example. capacity=2. get(1) makes 1 MRU; put(3,3) evicts 2; put(4,4) evicts 1; remaining {3,4}.

Input: (["LRUCache", "put", "get", "put", "get", "get"], [[1], [2, 1], [2], [3, 2], [2], [3]])

Expected Output: [None, None, 1, None, -1, 2]

Explanation: Capacity 1. put(2,1) then get(2)->1. put(3,2) evicts key 2, so get(2)->-1 and get(3)->2.

Input: (["LRUCache", "get"], [[1], [0]])

Expected Output: [None, -1]

Explanation: Edge case: get on an empty cache returns -1.

Input: (["LRUCache", "put", "put", "get", "get"], [[2], [1, 10], [1, 20], [1], [2]])

Expected Output: [None, None, None, 20, -1]

Explanation: Updating an existing key (put(1,20)) overwrites the value without inserting a new entry, so no eviction; get(1)->20, get(2)->-1.

Input: (["LRUCache", "put", "put", "put", "get", "get", "get"], [[2], [1, 1], [2, 2], [3, 3], [1], [2], [3]])

Expected Output: [None, None, None, None, -1, 2, 3]

Explanation: Three inserts into capacity 2: put(3,3) evicts the LRU key 1, so get(1)->-1, get(2)->2, get(3)->3.

Hints

A hash map alone gives O(1) lookup but no notion of recency order; pair it with something that tracks usage order.
Combine a hash map with a doubly linked list (or Python's OrderedDict): the map gives O(1) access, the list gives O(1) reordering and O(1) eviction of the least recently used end.
On every get and every put, move the touched key to the most-recently-used end. When size exceeds capacity after a put, remove the key at the least-recently-used end.

Quick Overview