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 easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at xAI.

What role is this question designed for?

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

Design a Fixed-Capacity Least-Recently-Used Cache

Quick Overview

This question evaluates a candidate's understanding of data structure design and algorithmic complexity, specifically implementing a fixed-capacity least-recently-used (LRU) cache that maintains recency ordering and supports O(1) average-time get and put operations in the Coding & Algorithms category.

Company: xAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

# Design a Fixed-Capacity Least-Recently-Used Cache Design and implement a cache with a fixed maximum capacity that evicts the **least recently used** entry when it is full. Your implementation must support the following operations, each in **O(1) average time**: - `LRUCache(capacity)` — initialize the cache with a positive integer capacity. - `get(key)` — return the value associated with `key` if it is present in the cache; otherwise return `-1`. A successful `get` marks the key as the **most recently used** entry. - `put(key, value)` — insert `key` with `value`. If `key` already exists, update its value and mark it as the most recently used entry. If `key` does not exist and the cache is at capacity, evict the least recently used entry first, then insert the new key as the most recently used entry. "Recency" is defined by the order of successful `get` calls and all `put` calls: every `get` hit and every `put` (insert or update) makes that key the most recently used; the entry that has gone the longest without being touched by either operation is the least recently used. Do **not** use a built-in ordered-map structure that already provides LRU behavior (such as Python's `OrderedDict` / `functools.lru_cache` or Java's access-ordered `LinkedHashMap`) as the core of your solution — build the recency-ordering structure yourself. **Example** ``` LRUCache cache = new LRUCache(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.put(3, 3) // capacity exceeded: evicts key 2; cache: {1=1, 3=3} cache.get(2) // returns -1 (evicted) cache.put(4, 4) // evicts 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 <= 10^4` - `0 <= key, value <= 10^9` - Up to `10^5` total calls to `get` and `put` - `get` and `put` must each run in O(1) average time Your implementation should behave correctly in all edge cases, including: capacity 1; updating the value of an existing key (which must refresh its recency but must not evict anything); repeatedly touching the entry that is currently least recently used; and evicting when the touched or evicted entry is at either end of your recency ordering.

Quick Answer: This question evaluates a candidate's understanding of data structure design and algorithmic complexity, specifically implementing a fixed-capacity least-recently-used (LRU) cache that maintains recency ordering and supports O(1) average-time get and put operations in the Coding & Algorithms category.

Design and implement a cache with a fixed maximum capacity that evicts the **least recently used** entry when it is full. Each operation must run in **O(1) average time**. Implement a class `LRUCache` with: - `LRUCache(capacity)` — initialize with a positive integer capacity. - `get(key)` — return the value associated with `key` if present, otherwise `-1`. A successful `get` marks the key as the **most recently used** entry. - `put(key, value)` — insert `key` with `value`. If `key` already exists, update its value and mark it most recently used. If `key` is new and the cache is at capacity, evict the least recently used entry first, then insert the new key as most recently used. "Recency" is defined by the order of successful `get` calls and all `put` calls: every `get` hit and every `put` (insert or update) makes that key the most recently used; the entry that has gone the longest without being touched by either operation is the least recently used. Do **not** use a built-in ordered-map that already provides LRU behavior (Python `OrderedDict` / `functools.lru_cache`, Java access-ordered `LinkedHashMap`) as the core — build the recency-ordering structure yourself (the intended solution is a hash map plus a doubly linked list). **How this console drives your class.** The harness calls a driver `solution(operations, args)`. `operations` is a list of strings (`"LRUCache"`, `"put"`, `"get"`) and `args[i]` holds the arguments for `operations[i]` (`[capacity]`, `[key, value]`, or `[key]`). The driver constructs your `LRUCache`, replays the calls in order, and returns **the list of values produced by the `get` calls** (constructor and `put` produce no output). Implement the `LRUCache` class; the driver is provided for you. **Example** ``` operations = ["LRUCache","put","put","get","put","get","put","get","get","get"] args = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]] put(1,1) // cache: {1=1} put(2,2) // cache: {1=1, 2=2} get(1) // -> 1; key 1 now most recently used put(3,3) // at capacity: evict key 2; cache: {1=1, 3=3} get(2) // -> -1 (evicted) put(4,4) // evict key 1; cache: {3=3, 4=4} get(1) // -> -1 (evicted) get(3) // -> 3 get(4) // -> 4 returns (get results only): [1, -1, -1, 3, 4] ```

Constraints

1 <= capacity <= 10^4
0 <= key, value <= 10^9
Up to 10^5 total calls to get and put
get and put must each run in O(1) average time
Do not use a built-in access-ordered map (OrderedDict / lru_cache / access-ordered LinkedHashMap) as the core structure

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: [1, -1, -1, 3, 4]

Explanation: The spec example (capacity 2). get(1) hits (1), then put(3,3) evicts key 2 so get(2)=-1; put(4,4) evicts key 1 so get(1)=-1; get(3)=3 and get(4)=4 remain.

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

Expected Output: [1, -1, 2]

Explanation: Capacity 1 edge case. put(1,1) then get(1)=1; put(2,2) evicts key 1 (the only entry), so get(1)=-1 and get(2)=2.

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

Expected Output: [10, 2]

Explanation: Updating an existing key must refresh recency without evicting. put(1,10) overwrites key 1's value and makes it most recently used; both keys survive, so get(1)=10 and get(2)=2.

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

Expected Output: [1, 1, 3]

Explanation: Touching the current LRU entry protects it. get(1) makes key 1 most recently used, so the later put(3,3) evicts key 2 instead; get(1)=1 and get(3)=3.

Input: (['LRUCache','get','put','get'], [[1],[0],[0,5],[0]])

Expected Output: [-1, 5]

Explanation: get on an empty cache returns -1. After put(0,5), get(0)=5 (key and value of 0 are valid boundary values).

Hints

Combine a hash map (key -> node) for O(1) lookup with a doubly linked list that keeps entries ordered by recency; the head end is most recently used, the tail end is least recently used.
Use two sentinel nodes (a dummy head and dummy tail) so insertion and removal never have to special-case the ends of the list — every real node always has a non-null prev and next.
On both a get hit and a put on an existing key, unlink the node from its current position and re-insert it right behind the head (most recently used). On eviction, remove the node just before the tail and delete its key from the map.
When updating an existing key in put, refresh recency but do NOT evict — the size did not grow. Only a brand-new key at full capacity triggers an eviction.

Quick Overview