Interview Prepcustom-data-structuresmediumAmazonMicrosoftGoogleFacebook

Copy List with Random Pointer

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

</>

IDE

def copyRandomList(head: 'Node') -> 'Node':

def copyRandomList(head):
    # Write your solution here
    pass

class Solution {
    public Node copyRandomList(Node head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

Node* copyRandomList(Node* head) {
    // Write your solution here
    return nullptr;
}

function copyRandomList(head) {
    // Write your solution here
}

0/10

Common Bugs to Avoid

Wrong: Random pointers in copied list point to original nodes instead of copied nodes.Forgot to use a mapping from original to copied nodes when assigning random pointers.✅ Use a dictionary/map to store original->copy node mapping and assign random pointers using this map.

Wrong: Function crashes or returns non-null for empty input.No base case handling for empty input (null head).✅ Add a check at the start: if head is null, return null immediately.

Wrong: Infinite recursion or timeout on inputs with cycles in random pointers.No visited map or memoization to handle cycles in random pointers.✅ Use a map to track visited nodes and avoid revisiting during recursion or iteration.

Wrong: Random pointers in copied list do not preserve shared references, creating multiple copies of the same node.Assigning random pointers without reusing copied nodes from the map.✅ Always assign random pointers using the map to ensure shared references point to the same copied node.

Wrong: Solution times out on large inputs.Using exponential or quadratic time approach instead of O(n).✅ Implement O(n) time solution using hash map or node weaving technique.

✓

Test Cases

t1_01basic

Input{"head":[[7,null],[13,0],[11,4],[10,2],[1,0]]}

Expected[[7,null],[13,0],[11,4],[10,2],[1,0]]

The list has 5 nodes. Each node's random pointer points to the index given (or null). The output is a deep copy with the same structure and random pointers.

t1_02basic

Input{"head":[[1,null],[2,0],[3,1]]}

Expected[[1,null],[2,0],[3,1]]

List of 3 nodes where random pointers form a chain back to previous nodes. The deep copy must replicate this structure exactly.

Practice

(1/5)

1. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

3. Examine the following buggy remove method from the optimized Insert Delete GetRandom O(1) with duplicates data structure. Which line contains the subtle bug that can cause incorrect behavior or runtime errors?

def remove(self, val: int) -> bool:
    if val not in self.idx_map or not self.idx_map[val]:
        return false
    remove_idx = self.idx_map[val].pop()
    last_val = self.nums[-1]
    self.nums[remove_idx] = last_val
    self.idx_map[last_val].add(remove_idx)
    # BUG: missing discard of old index for last_val
    self.nums.pop()
    if not self.idx_map[val]:
        del self.idx_map[val]
    return true

medium

A. Missing line to discard old index of last_val from idx_map[last_val]

B. Line adding remove_idx to idx_map[last_val] (self.idx_map[last_val].add(remove_idx))

C. Line popping remove_idx from idx_map[val] (remove_idx = self.idx_map[val].pop())

D. Line removing the last element from nums (self.nums.pop())

Copy List with Random Pointer

Start learning this pattern below

Practice

Solution

Step 1: Trace cache state after each operation

Step 2: Evaluate get(1) after put(4,4)

Final Answer:

Quick Check:

Solution

Step 1: Identify the costly operation

Step 2: Analyze nested traversal effect

Final Answer:

Quick Check:

Solution

Step 1: Understand index updates during removal

Step 2: Identify missing discard

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse implications

Step 2: Ensure reuse is treated as new insertion

Step 3: Confirm O(1) operations

Final Answer:

Quick Check:

Solution

Step 1: Understand tweet reuse impact

Step 2: Adjust data structures

Final Answer:

Quick Check: