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

What role is this question designed for?

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

Implement LRU cache and copy random list

Quick Overview

This question evaluates competency in data-structure design, pointer and memory management, and hashing-based eviction policies by combining a deep-copy of a linked list with random pointers and an LRU cache requiring O(1) operations, and it belongs to the Coding & Algorithms domain.

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Coding questions (two parts) ### Part A — Deep copy a linked list with random pointers You are given the head of a singly linked list where each node has: - `next`: pointer to the next node - `random`: pointer to any node in the list or `null` Return a **deep copy** of the list (all new nodes), preserving both `next` and `random` relationships. **Goal:** The copied list must not share any nodes with the original. --- ### Part B — Design an LRU cache Design a data structure `LRUCache` that supports: - `get(key)`: return the value for `key` if present, else `-1` - `put(key, value)`: insert or update the value The cache has a fixed capacity `C`. When inserting causes the cache to exceed `C`, it must evict the **least recently used** item. ### Requirements - Average time complexity: **O(1)** for both `get` and `put` - Keys are hashable (e.g., integers/strings)

Quick Answer: This question evaluates competency in data-structure design, pointer and memory management, and hashing-based eviction policies by combining a deep-copy of a linked list with random pointers and an LRU cache requiring O(1) operations, and it belongs to the Coding & Algorithms domain.

Copy a Linked List with Random Pointers

You are given the head of a singly linked list where each node has two pointers: - `next`: a pointer to the next node in the list (or `null` at the tail) - `random`: a pointer to **any** node in the list, or `null` Return a **deep copy** of the list. Every node in the returned list must be a brand-new node, and the copy must preserve both the `next` chain and every `random` relationship. The copied list must not share any node with the original. **Input/output encoding for this console.** Because pointers can't be passed directly, the list is given as an array `nodes` where `nodes[i] = [val, random_index]`: - `val` is the value stored at node `i`. - `random_index` is the **index** (into this same array) of the node that node `i`'s `random` points to, or `null` if it points to nothing. Implement `solution(nodes)` that returns the deep copy in the **same** `[val, random_index]` encoding. (Internally you should build real nodes and copy them with a hash map; the re-encoding step is just so the result can be compared.) **Example** ``` Input: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] Output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] ``` Node 1 (value 13) has random pointing to index 0 (value 7); node 4 (value 1) has random pointing to index 0; node 2 (value 11) has random pointing to index 4, etc.

Constraints

0 <= number of nodes <= 1000
-10^5 <= node value <= 10^5
random_index is either a valid index in [0, n-1] or null
The copy must share no node objects with the original list

Examples

Input: ([[7, None], [13, 0], [11, 4], [10, 2], [1, 0]],)

Expected Output: [[7, None], [13, 0], [11, 4], [10, 2], [1, 0]]

Explanation: Classic LeetCode example. Node 13's random -> node 7 (index 0); node 11's random -> node 1 (index 4); node 10's random -> node 11 (index 2); node 1's random -> node 7 (index 0). The deep copy preserves all of these.

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

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

Explanation: Both nodes' random pointers point at the second node (index 1), including the second node pointing at itself.

Input: ([[3, None], [3, 0], [3, None]],)

Expected Output: [[3, None], [3, 0], [3, None]]

Explanation: Duplicate values with mixed null/non-null random pointers; the copy must distinguish nodes by identity, not value.

Input: ([],)

Expected Output: []

Explanation: Edge case: empty list returns an empty list.

Input: ([[5, 0]],)

Expected Output: [[5, 0]]

Explanation: Edge case: single node whose random points to itself (index 0).

Input: ([[-1, None], [-2, 0], [-3, 1], [-4, 2]],)

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

Explanation: Negative values; each node's random points to the previous node, forming a backward chain that must be preserved.

Hints

Walk the list once to create a new node for each original node, storing the mapping old_node -> new_node in a hash map.
Walk a second time and wire up each new node's next and random by looking up the mapped copies in the hash map.
An O(1)-extra-space alternative interleaves copied nodes between originals, sets random from the interleaving, then unweaves the two lists.

Design an LRU Cache

Design a data structure `LRUCache` that operates with a fixed capacity `C` and supports two operations, both in **average O(1)** time: - `get(key)`: return the value associated with `key` if it is present, otherwise return `-1`. A successful `get` counts as a use (it makes `key` the most recently used). - `put(key, value)`: insert the key/value pair, or update the value if the key already exists. This also marks `key` as most recently used. If inserting a new key would exceed the capacity, evict the **least recently used** key first. **Input/output encoding for this console.** Since the grader calls a single function, drive the cache with two parallel arrays: - `operations`: a list of method names. The first is always `"LRUCache"` (the constructor); the rest are `"get"` or `"put"`. - `arguments`: a parallel list of argument lists. `["LRUCache", [C]]`, `["put", [key, value]]`, `["get", [key]]`. Implement `solution(operations, arguments)` that returns a list of results — one entry per operation. The constructor and every `put` produce `null`; each `get` produces its return value. **Example** ``` operations = ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] arguments = [[2], [1,1], [2,2], [1], [3,3], [2], [4,4], [1], [3], [4]] output = [null, null, null, 1, null, -1, null, -1, 3, 4] ``` After `put(3,3)` the cache (capacity 2) evicts key 2 (least recently used), so `get(2)` returns -1.

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 2 * 10^5 calls total to get and put
get and put must each 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 trace (capacity 2). put(3,3) evicts key 2; put(4,4) evicts key 1; later gets reflect the evictions.

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

Expected Output: [None, -1]

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

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: putting key 3 evicts key 2, so get(2) returns -1 and get(3) returns 2.

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

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

Explanation: Updating an existing key (1 -> 20) overwrites the value and refreshes recency; key 1 survives the insertion of key 2.

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

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

Explanation: get(1) makes key 1 most recently used, so when put(3,3) overflows it evicts key 2 instead of key 1.

Hints

Combine a hash map (key -> node) for O(1) lookup with a doubly linked list to track recency: most recently used at one end, least recently used at the other.
On get and on put-of-existing-key, move that node to the most-recently-used end.
On put, if size exceeds capacity, evict the node at the least-recently-used end and remove it from the hash map. In Python an OrderedDict (move_to_end + popitem(last=False)) gives you both behaviors for free.

Quick Overview