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

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Shopify during technical interviews.

Implement an LRU Cache | Shopify Coding Question

Implement an LRU Cache

Company: Shopify

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

## Problem Design and implement an **LRU (Least Recently Used) Cache** that supports the following operations in **O(1) average time**: - `get(key)`: - Return the value associated with `key` if it exists in the cache. - Otherwise return `-1`. - This operation marks `key` as **most recently used**. - `put(key, value)`: - Insert or update the `(key, value)` pair. - This operation marks `key` as **most recently used**. - If inserting causes the number of keys to exceed the cache `capacity`, evict the **least recently used** key. ## Requirements - Implement a class (or module) that is initialized with an integer `capacity`. - Both operations should run in **O(1)** average time. ## Notes / Edge Cases - Updating an existing key should overwrite its value and update its recency. - `capacity` is a positive integer. ## Example Given `capacity = 2`: 1. `put(1, 1)` 2. `put(2, 2)` 3. `get(1)` → returns `1` (key `1` becomes most recently used) 4. `put(3, 3)` → evicts key `2` 5. `get(2)` → returns `-1` 6. `put(4, 4)` → evicts key `1` 7. `get(1)` → returns `-1` 8. `get(3)` → returns `3` 9. `get(4)` → returns `4`

Quick Answer: This question evaluates a candidate's competency in designing efficient cache mechanisms and managing time and space complexity for operations required to support least-recently-used eviction.

Design and implement an **LRU (Least Recently Used) Cache** supporting two operations in **O(1) average time**: - `get(key)` returns the value for `key` if present, else `-1`, and marks `key` as most recently used. - `put(key, value)` inserts or updates the pair, marks `key` as most recently used, and evicts the least recently used key when the number of keys exceeds `capacity`. Because this judge drives your code through a single entry point, implement `solution(capacity, operations)`: - `capacity` is a positive integer — the cache size. - `operations` is a list of commands. Each command is a list whose first element is `"put"` or `"get"`: - `["put", key, value]` performs `put(key, value)` and contributes `None`/`null` to the output. - `["get", key]` performs `get(key)` and contributes the returned value (the stored value or `-1`). Return the list of results, one entry per command, in order. Internally you should still build a real O(1) LRU cache (hash map + doubly linked list, or an ordered map); the driver just records what each call would have returned. Example (`capacity = 2`): `[["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]` → `[null,null,1,null,-1,null,-1,3,4]`. After `get(1)`, key 1 is most recently used, so `put(3,3)` evicts key 2; `put(4,4)` then evicts key 1.

Constraints

1 <= capacity
0 <= number of operations <= 10^5
Each operation is ["put", key, value] or ["get", key]
Keys and values fit in a 32-bit signed integer (may be negative or zero)
get and put must each run in O(1) average time

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

Explanation: The canonical example. get(1) makes key 1 most recently used, so put(3,3) evicts key 2 (get(2) -> -1). put(4,4) then evicts key 1 (get(1) -> -1). Keys 3 and 4 remain.

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

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

Explanation: Capacity 1: putting key 2 evicts key 1, so get(1) returns -1 while get(2) returns 20.

Input: (2, [["get", 1]])

Expected Output: [-1]

Explanation: get on an empty cache returns -1.

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

Expected Output: [None, None, 5]

Explanation: Updating an existing key overwrites its value (1 -> 5) and refreshes recency.

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

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

Explanation: After filling 1,2,3, get(1) bumps key 1 to most-recent, so put(4,4) evicts the least-recently-used key 2; key 2 then misses while 3, 4, and 1 hit.

Input: (2, [["put", -1, -100], ["get", -1], ["put", 0, 0], ["put", 5, 5], ["get", -1]])

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

Explanation: Negative and zero keys/values work; after putting 0 and 5 into a size-2 cache, key -1 (least recently used) is evicted and returns -1.

Hints

Combine a hash map (key -> node) with a doubly linked list ordering nodes from least- to most-recently used; this gives O(1) lookup plus O(1) move/evict.
On get, if the key exists, move its node to the most-recently-used end before returning the value.
On put for an existing key, update the value and move it to the most-recently-used end; for a new key, insert at that end and, if size now exceeds capacity, remove the node at the least-recently-used end.
Python's collections.OrderedDict (move_to_end / popitem(last=False)) gives all of this for free, as does Java LinkedHashMap with access order.

Quick Overview

This question evaluates a candidate's competency in designing efficient cache mechanisms and managing time and space complexity for operations required to support least-recently-used eviction.