Deep-Copy a Linked List with Random Pointers
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Deep-copy a singly linked list in which every node has both a `next` pointer and a `random` pointer. The portable input representation uses parallel arrays of node records; the result must describe newly created records without sharing any input node.
## Function Contract
Implement `copy_random_list(values, next_index, random_index, head)` and return `[copied_values, copied_next, copied_random, copied_head]`. In the result, copied nodes are ordered by following `next` from `head`; indices therefore refer to that returned order. Use `-1` for a null pointer.
## Rules
- Only nodes reachable from `head` by repeatedly following `next` belong to the list and appear in the result.
- The reachable `next` chain is acyclic and every reachable node's random pointer is null or targets another reachable node.
- Preserve values, `next` relationships, and `random` relationships exactly after remapping indices.
- Build independent copied node records and do not mutate any input array.
- If `head == -1`, return `[[], [], [], -1]`.
## Constraints
- `0 <= len(values) == len(next_index) == len(random_index) <= 100000`.
- Every non-null index is in `[0, len(values) - 1]`.
- Values are signed 32-bit integers.
## Examples
```text
values = [7, 13, 11]
next_index = [1, 2, -1]
random_index = [-1, 0, 1]
head = 0
output = [[7, 13, 11], [1, 2, -1], [-1, 0, 1], 0]
```
The output arrays encode three newly created nodes; matching numeric indices do not imply shared object identity with the input.
Overview: Deep-copy the reachable chain of a linked list whose nodes have both next and random pointers. Reindex copied nodes in next-chain order, preserve null and random relationships, exclude unreachable records, and ensure the result shares no node with the input.
A singly linked list is encoded by parallel arrays values, next_index, and random_index plus a head index. Follow next from head to identify the list; unreachable records are excluded. The reachable next chain is acyclic, and each reachable random pointer is null or targets another reachable node. Return [copied_values, copied_next, copied_random, copied_head], ordering copied nodes by following next from head and remapping all indices to that returned order. Use -1 for null. Do not mutate any input array. If head is -1, return [[], [], [], -1].
Constraints
- 0 <= len(values) == len(next_index) == len(random_index) <= 100000.
- Every non-null index is in [0, len(values) - 1], and -1 represents null.
- The reachable next chain is acyclic, and every reachable random pointer is null or points within that chain.
- Values are signed 32-bit integers.
Examples
Input: ([7, 13, 11], [1, 2, -1], [-1, 0, 1], 0)
Expected Output: [[7, 13, 11], [1, 2, -1], [-1, 0, 1], 0]
Explanation: The example chain already uses traversal order, so its indices remain unchanged.
Input: ([], [], [], -1)
Expected Output: [[], [], [], -1]
Explanation: A null head produces the canonical empty copied representation.
Hints
- First record the reachable nodes in the exact order obtained by following next from head.
- Complete the old-to-new index map before remapping random pointers.