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

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Shopify during technical interviews.

Implement an LRU Cache | Shopify Coding Question

Implement an LRU Cache

Company: Shopify

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

## Problem: LRU Cache (LeetCode 146) Design and implement a **Least Recently Used (LRU) Cache** that supports the following operations in **average O(1) time**. ### Requirements Implement a class `LRUCache` with: - `LRUCache(int capacity)`: Initialize the cache with a **positive** capacity. - `int get(int key)`: Return the value of the key if it exists; otherwise return `-1`. - Accessing a key counts as using it, so it becomes **most recently used**. - `void put(int key, int value)`: Insert or update the value of the key. - If the key exists, update its value and mark it as **most recently used**. - If inserting causes the cache to exceed capacity, **evict** the **least recently used** key. ### Notes / Constraints - Keys and values are integers. - Aim for **O(1)** average time per `get` and `put`. - You may use any language, standard library containers, and write unit tests. ### Example If `capacity = 2`: 1. `put(1, 1)` -> cache = {1=1} 2. `put(2, 2)` -> cache = {1=1, 2=2} 3. `get(1)` -> returns `1`, cache order becomes [2 (LRU), 1 (MRU)] 4. `put(3, 3)` -> evicts key `2`, cache = {1=1, 3=3} 5. `get(2)` -> returns `-1`

Quick Answer: This question evaluates competence in designing efficient cache mechanisms and mastery of data-structure strategies to support average O(1) get and put operations.

Design and implement a Least Recently Used (LRU) Cache supporting `get` and `put` in average O(1) time (LeetCode 146). Implement a class `LRUCache`: - `LRUCache(int capacity)` initializes the cache with a positive capacity. - `int get(int key)` returns the value of the key if present, otherwise `-1`. Accessing a key marks it as most recently used. - `void put(int key, int value)` inserts or updates a key. Updating marks it most recently used. If inserting exceeds capacity, evict the least recently used key. ### Harness encoding Because this is a class-design problem, your solution is driven as a sequence of operations. Implement the function `solution(operations, arguments)`: - `operations` is a list of method-name strings: `"LRUCache"` (the constructor, always first), `"get"`, or `"put"`. - `arguments` is a parallel list of argument lists for each operation (`[capacity]` for the constructor, `[key]` for `get`, `[key, value]` for `put`). - Return a list the same length as `operations`: the constructor and each `put` contribute `null` (`None` in Python); each `get` contributes its returned value. ### Example For `capacity = 2`: ``` operations = ["LRUCache", "put", "put", "get", "put", "get"] arguments = [[2], [1, 1], [2, 2], [1], [3, 3], [2]] ``` 1. `put(1, 1)` -> cache {1=1} 2. `put(2, 2)` -> cache {1=1, 2=2} 3. `get(1)` -> returns 1, order becomes [2 (LRU), 1 (MRU)] 4. `put(3, 3)` -> evicts key 2, cache {1=1, 3=3} 5. `get(2)` -> returns -1 Return: `[null, null, null, 1, null, -1]`.

Constraints

1 <= capacity
Keys and values are integers (LeetCode 146 uses 0 <= key, value <= 10^4 / 10^5).
operations[0] is always "LRUCache" (the constructor).
Each non-constructor operation is either "get" (args [key]) or "put" (args [key, value]).
get and put must run in average O(1) time.

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: Canonical LeetCode 146 trace with capacity 2. get(1)=1 promotes key 1; put(3,3) evicts key 2 -> get(2)=-1; put(4,4) evicts key 1 -> get(1)=-1; key 3 and 4 remain -> get(3)=3, get(4)=4.

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

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

Explanation: The example from the prompt: get(1)=1 makes key 1 MRU, so put(3,3) evicts the now-least-recently-used key 2, giving get(2)=-1.

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

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

Explanation: Capacity-1 edge case: putting key 2 immediately evicts key 1, so get(1)=-1 and get(2)=20.

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

Expected Output: [None, -1]

Explanation: Edge case: get on an empty cache for a key that was never inserted returns -1.

Input: (['LRUCache', 'put', 'put', 'get'], [[2], [5, 100], [5, 200], [5]])

Expected Output: [None, None, None, 200]

Explanation: Re-putting an existing key updates its value (and marks it MRU) without changing the size; get(5) returns the updated 200.

Hints

Combine a hash map (key -> node) for O(1) lookup with a structure that maintains usage order so the least-recently-used entry is found in O(1).
A doubly linked list with sentinel head/tail nodes lets you move a node to the front and pop from the back in O(1). Python's OrderedDict (move_to_end / popitem) and Java's LinkedHashMap in access-order mode encapsulate exactly this.
On get: if the key is missing return -1; otherwise mark it most-recently-used before returning its value.
On put: update or insert, mark it most-recently-used, then if size exceeds capacity evict the least-recently-used entry (the back of the list / first inserted ordered entry).

Quick Overview

This question evaluates competence in designing efficient cache mechanisms and mastery of data-structure strategies to support average O(1) get and put operations.