How should I practice Copy a Random-Pointer List in Constant Space?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Apple onsite interview problems in FastPrep.

Is Copy a Random-Pointer List in Constant Space associated with Apple?

FastPrep tags this as a Apple onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Linked List

Copy a Random-Pointer List in Constant Space

Learn this problem

● Medium

AppleFULLTIMEONSITE INTERVIEW

Problem statement

A linked list has one node per row of nodes. Row i is [value, randomIndex]:

The node's next pointer goes to row i + 1, or is null for the final row.
randomIndex is the row index reached by its random pointer, or -1 for null.

Build the list, create a deep copy, and separate the two lists. The copy phase must use O(1) auxiliary space beyond the newly allocated clone nodes by interleaving each clone immediately after its original node. Restore every original next pointer exactly, wire every clone's next and random pointers to clone nodes, and null-terminate the clone tail.

Immediately after separation, serialize the restored original. Then, when the list is non-empty, change the original node at mutationIndex to newValue and redirect its random pointer to newRandomIndex, where -1 means null. Return [restoredOriginal, mutatedOriginal, deepCopy]. The copy must retain the pre-mutation values and random links. For an empty list, mutationIndex and newRandomIndex are -1 and all three snapshots are empty. Adapter storage and returned snapshots do not count toward the copy phase's auxiliary-space bound.

Function

copyRandomListConstantSpace(nodes: int[][], mutationIndex: int, newValue: int, newRandomIndex: int) → int[][][]

Examples

Example 1

nodes = [[7,-1],[13,0],[11,4],[10,2],[1,0]]mutationIndex = 2newValue = 99newRandomIndex = 1return = [[[7,-1],[13,0],[11,4],[10,2],[1,0]],[[7,-1],[13,0],[99,1],[10,2],[1,0]],[[7,-1],[13,0],[11,4],[10,2],[1,0]]]

The first snapshot proves restoration. Mutating original node 2 changes only the middle snapshot; the clone keeps value 11 and random target 4.

Example 2

nodes = []mutationIndex = -1newValue = 0newRandomIndex = -1return = [[],[],[]]

An empty list has empty restored, mutated, and clone snapshots.

Example 3

nodes = [[5,0],[5,0]]mutationIndex = 0newValue = 8newRandomIndex = 1return = [[[5,0],[5,0]],[[8,1],[5,0]],[[5,0],[5,0]]]

Equal values do not identify nodes. The mutation redirects only the original first node to row 1; the clone's random links still target clone row 0.

Constraints

0 <= nodes.length <= 100000.
Every row contains exactly [value, randomIndex].
All node values and newValue fit a signed 32-bit integer.
Every stored random index and newRandomIndex is -1 or a valid row index.
For a non-empty list, 0 <= mutationIndex < nodes.length. For an empty list, mutationIndex == -1.
The clone phase must use O(1) auxiliary space beyond clone nodes and must not use a map from original nodes to clones.
The returned snapshots and adapter storage are excluded from the clone phase's auxiliary-space bound.