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 Technical Screen rounds at TikTok.

What role is this question designed for?

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

Implement an LRU cache | TikTok Coding Question

Implement an LRU cache

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

## Problem: LRU Cache Design and implement a data structure that supports an **LRU (Least Recently Used) cache** with a fixed capacity. ### Requirements Implement a cache with the following operations: - `get(key) -> value` - If `key` exists in the cache, return its value and mark the entry as **most recently used**. - If `key` does not exist, return `-1`. - `put(key, value) -> void` - Insert or update the `(key, value)` pair. - If inserting causes the number of keys to exceed `capacity`, evict the **least recently used** entry. - Updating an existing key should also mark it as **most recently used**. ### Performance Constraints - Target time complexity: **O(1)** average for both `get` and `put`. - Space complexity: **O(capacity)**. ### Example Assume `capacity = 2`: - `put(1, 10)` - `put(2, 20)` - `get(1) -> 10` (now key `1` is most recently used) - `put(3, 30)` (evicts key `2` as least recently used) - `get(2) -> -1` ### Notes You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.

Quick Answer: This question evaluates understanding of cache design and eviction policies (LRU), along with competency in selecting and reasoning about data structures and complexity to support efficient get and put operations under capacity constraints.

Design and implement a data structure that supports an **LRU (Least Recently Used) cache** with a fixed `capacity`, supporting two operations in O(1) average time: - `get(key)` — return the value if `key` is present and mark it **most recently used**; otherwise return `-1`. - `put(key, value)` — insert or update the pair and mark it **most recently used**; if this makes the number of keys exceed `capacity`, evict the **least recently used** entry. To make this runnable, your function is given the `capacity` and a list of `operations`. Replay them against your cache and return a list containing the result of every `get` operation, in order. **Operation encoding** - `put`: `["put", key, value]` — performs `put(key, value)`, produces no output. - `get`: `["get", key]` — performs `get(key)`, appends its return value (the value, or `-1`) to the output list. **Example** (`capacity = 2`) Operations: `[["put",1,10], ["put",2,20], ["get",1], ["put",3,30], ["get",2], ["get",3]]` - `put(1,10)`, `put(2,20)` → cache `{1:10, 2:20}` - `get(1)` → `10` (key 1 now most recently used) - `put(3,30)` → exceeds capacity, evict least recently used key `2` → `{1:10, 3:30}` - `get(2)` → `-1` (evicted) - `get(3)` → `30` Return: `[10, -1, 30]`. Aim for O(1) average per operation using a hash map plus a doubly linked list (or an ordered map).

Constraints

1 <= capacity
0 <= number of operations
Keys and values are integers
get on a missing key returns -1
put that updates an existing key marks it most recently used and does NOT evict
Both get and put must be O(1) average time

Examples

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

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

Explanation: After put(1,10),put(2,20): {1,2}. get(1)=10 makes 1 MRU. put(3,30) evicts LRU key 2 -> {1,3}. get(2)=-1 (evicted), get(3)=30, get(1)=10.

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: Classic LeetCode trace: get(1)=1; put(3) evicts 2 so get(2)=-1; put(4) evicts 1 so get(1)=-1; get(3)=3; get(4)=4.

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

Expected Output: [1, -1, 2]

Explanation: Capacity 1: put(2,1); get(2)=1; put(3,2) evicts 2; get(2)=-1; get(3)=2.

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

Expected Output: [20]

Explanation: Updating an existing key overwrites the value and marks it MRU without evicting; get(1)=20.

Input: (2, [['get', 0]])

Expected Output: [-1]

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

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

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

Explanation: Cache fills to {1,2,3}; get(1) makes 1 MRU; put(4) evicts LRU key 2; get(2)=-1, get(1)=1, get(3)=3, get(4)=4.

Hints

Combine a hash map (key -> node) with a doubly linked list ordered from least to most recently used. The map gives O(1) lookup; the list gives O(1) reordering and eviction.
On get/put of an existing key, move that node to the most-recently-used end. On a brand-new put, append it and, if size exceeds capacity, remove the node at the least-recently-used end.
An ordered hash map (Python OrderedDict / collections, Java LinkedHashMap, JS Map) gives the same behavior: move_to_end on access, popitem(last=False) to evict the oldest.

Quick Overview

This question evaluates understanding of cache design and eviction policies (LRU), along with competency in selecting and reasoning about data structures and complexity to support efficient get and put operations under capacity constraints.