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 Software Engineer candidates at Meta during technical interviews.

Copy linked list with random pointers efficiently

Quick Overview

Copy linked list with random pointers efficiently evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given the head of a singly linked list where each node has next and random pointers, create a deep copy of the list. First provide an O(n) time, O(n) extra space solution using a hash map from original nodes to copies. Then implement an O(n) time, O( 1) extra space approach by interleaving copied nodes with original nodes, fixing random pointers, and restoring the original list. Discuss pitfalls such as null randoms, self-references, and cycles.

Quick Answer: Copy linked list with random pointers efficiently evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given a singly linked list of length n. Each node has a `next` pointer and an additional `random` pointer that may point to ANY node in the list or to null. Construct a **deep copy** of the list: the copy must have exactly n brand-new nodes whose values match the originals, with `next` and `random` pointers wired entirely among the copied nodes (no copied pointer may reference an original node). After copying, the original list must be left unchanged. **Input / output encoding.** Because raw pointers are not portable, the list is encoded as an array of `[val, random_index]` pairs, one per node in `next` order. `random_index` is the 0-based index of the node that this node's `random` pointer targets, or `-1` if `random` is null. You receive this encoded array; build the list, deep-copy it, then return the copied list re-encoded in the same `[val, random_index]` format. **Example.** `[[7,-1],[13,0],[11,4],[10,2],[1,0]]` means node 0 has value 7 and random=null, node 1 has value 13 and random points to node 0, etc. A correct deep copy round-trips to the identical encoding. Aim for the optimal **O(n) time, O(1) extra space** approach (interleaving copied nodes between originals) that the interviewer pushes for after the hash-map solution. Watch the pitfalls called out in the question: null randoms, a node whose random points to itself, and randoms that form cycles.

Constraints

0 <= n <= 1000
-10^4 <= node value <= 10^4
random_index is -1 (null) or a valid 0-based index in [0, n-1]
The original list must remain unchanged after the copy (interleave technique must fully restore it)
No copied pointer may reference an original node (true deep copy)

Examples

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

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

Explanation: Classic LC-138 example. Node 0 (7) has null random; node 1 (13) -> node 0; node 2 (11) -> node 4; node 3 (10) -> node 2; node 4 (1) -> node 0. The deep copy round-trips to the identical encoding, confirming every value and random index was reproduced.

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

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

Explanation: Both nodes' random pointers target node 1 (the second node), including node 1 pointing to itself — a self-reference. The interleaving method resolves it correctly without special handling.

Input: ([],)

Expected Output: []

Explanation: Empty list edge case: nothing to copy, return an empty encoding.

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

Expected Output: [[5, 0]]

Explanation: Single node whose random points to itself. Exercises the self-reference pitfall on a one-element list.

Input: ([[3, -1]],)

Expected Output: [[3, -1]]

Explanation: Single node with a null random pointer.

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

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

Explanation: All random pointers null — verifies the next chain alone is copied correctly and nulls stay null.

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

Expected Output: [[-7, 2], [0, 0], [4, 1]]

Explanation: Negative and zero values plus randoms forming a cross/cycle pattern (0->2, 1->0, 2->1). Confirms value sign handling and cyclic random pointers.

Hints

Baseline (O(n) space): make a copy of every node first, store a map from each original node to its copy, then do a second pass setting copy.next = map[orig.next] and copy.random = map[orig.random].
To reach O(1) extra space, eliminate the map by weaving each copy directly behind its original: A -> A' -> B -> B' -> ... Now the copy of any node X is simply X.next.
With the interleaving in place, random wiring is local: for each original node cur, set cur.next.random = cur.random.next (skip when cur.random is null). cur.random.next is exactly the copy of cur.random.
Finally, unzip the two lists in a third pass so the original list is restored to its initial state and the copied list stands alone. Handle the last node's next carefully to avoid a None dereference.
Pitfalls: a null random must stay null; a self-reference (random points to its own node) and random cycles are handled automatically because cur.random.next always resolves to the right copy — no special-casing needed.

Quick Overview