Practice
1. Consider the following Python code snippet implementing the optimized Insert Delete GetRandom O(1) with duplicates data structure. After executing the sequence of operations below, what is the return value of the final getRandom() call?
Operations:
insert(1), insert(1), insert(2), remove(1), getRandom()
import random
class Node:
def __init__(self, val):
self.val = val
self.prev = null
self.next = null
class DoublyLinkedList:
def __init__(self):
self.head = Node(null)
self.tail = Node(null)
self.head.next = self.tail
self.tail.prev = self.head
def append(self, val):
node = Node(val)
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
return node
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def is_empty(self):
return self.head.next == self.tail
class RandomizedCollection:
def __init__(self):
self.nums = []
self.idx_map = {}
def insert(self, val: int) -> bool:
self.nums.append(val)
if val not in self.idx_map:
self.idx_map[val] = set()
self.idx_map[val].add(len(self.nums) - 1)
return len(self.idx_map[val]) == 1
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)
self.idx_map[last_val].discard(len(self.nums) - 1)
self.nums.pop()
if not self.idx_map[val]:
del self.idx_map[val]
return true
def getRandom(self) -> int:
return random.choice(self.nums)
rc = RandomizedCollection()
rc.insert(1)
rc.insert(1)
rc.insert(2)
rc.remove(1)
result = rc.getRandom()
easy
Solution
Step 1: Trace insertions
After insert(1), nums=[1], idx_map={1:{0}}; after insert(1), nums=[1,1], idx_map={1:{0,1}}; after insert(2), nums=[1,1,2], idx_map={1:{0,1},2:{2}}.Step 2: Trace removal of one 1
Remove one 1: remove_idx=1 (pop from idx_map[1]). Swap last element 2 into index 1: nums=[1,2], idx_map={1:{0},2:{1}}. So now nums has one 1 and one 2.Step 3: Analyze getRandom probabilities
nums=[1,2], so getRandom picks index 0 or 1 equally. But initially there were two 1's, after removal only one remains. So 1 and 2 are equally likely, but since the original had duplicates, the final collection has one 1 and one 2.Final Answer:
Option A -> Option AQuick Check:
After removal, one 1 and one 2 remain, so 1 is as likely as 2 [OK]
Hint: Track indices and swaps carefully to find final array state [OK]
Common Mistakes:
- Forgetting to update idx_map after swap
- Assuming getRandom returns only 2
- Ignoring that one 1 remains after removal
2. The following code attempts to copy a linked list with random pointers using the optimal weaving approach. Identify the line that contains a subtle bug that can cause incorrect random pointer assignment or list corruption.
def copyRandomList(head):
if not head:
return None
curr = head
# Step 1: Insert copied nodes
while curr:
new_node = Node(curr.val, curr.next)
curr.next = new_node
curr = new_node.next
# Step 2: Assign random pointers
curr = head
while curr:
if curr.random:
curr.next.random = curr.random # Bug here
curr = curr.next.next
# Step 3: Separate lists
curr = head
copy_head = head.next
copy_curr = copy_head
while curr:
curr.next = curr.next.next
if copy_curr.next:
copy_curr.next = copy_curr.next.next
curr = curr.next
copy_curr = copy_curr.next
return copy_headmedium
Solution
Step 1: Analyze random pointer assignment
The line assignscurr.next.random = curr.random, butcurr.randompoints to original nodes, not copied nodes.Step 2: Correct assignment
It should becurr.next.random = curr.random.nextto point to the copied node corresponding tocurr.random.Final Answer:
Option A -> Option AQuick Check:
Incorrect random pointer assignment breaks copied list correctness [OK]
Hint: Random pointer must point to copied node, not original [OK]
Common Mistakes:
- Assigning random pointer directly to original node
- Mixing original and copied nodes after weaving
- Forgetting to advance curr by two nodes
3. Consider the following buggy code snippet for the optimal UndergroundSystem implementation. What is the subtle bug causing incorrect behavior or memory leaks?
def checkOut(self, id: int, stationName: str, t: int) -> None:
prev = None
curr = self.head
while curr:
if curr.id == id:
travel_time = t - curr.time
route = (curr.station, stationName)
if route not in self.route_data:
self.route_data[route] = [0, 0]
self.route_data[route][0] += travel_time
self.route_data[route][1] += 1
# BUG: Missing removal of check-in node
return
prev = curr
curr = curr.next
medium
Solution
Step 1: Identify missing removal
The code does not remove the matched check-in node from the linked list, causing memory leaks and repeated matches.Step 2: Consequences of missing removal
Without removal, subsequent checkOut calls for the same id will find the old node again, causing incorrect data and memory growth.Final Answer:
Option C -> Option CQuick Check:
Removal of node is essential to avoid stale data [OK]
Hint: Check if matched node is removed after checkOut [OK]
Common Mistakes:
- Forgetting to unlink node after processing
4. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings? Assume merging two skylines of total length m takes O(m) time.
medium
Solution
Step 1: Identify divide and conquer recurrence
The algorithm splits buildings into halves recursively, then merges skylines in O(m) time where m is proportional to n.Step 2: Solve recurrence and analyze merge cost
Recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The width w does not affect complexity here.Final Answer:
Option C -> Option CQuick Check:
Divide and conquer with linear merge per level -> O(n log n) [OK]
Hint: Divide and conquer recurrence T(n)=2T(n/2)+O(n) -> O(n log n) [OK]
Common Mistakes:
- Confusing width w with n
- Assuming quadratic due to nested loops
5. Suppose the RangeModule must support intervals with negative coordinates and allow intervals to be added and removed multiple times (reusing intervals). Which modification to the optimal balanced BST approach is necessary to handle this correctly?
hard
Solution
Step 1: Consider negative coordinates impact
Bisect operations and interval storage must correctly handle negative values, which requires no change in data structure but careful handling of interval boundaries.Step 2: Consider interval reuse
Intervals can be added and removed multiple times, so storing intervals as half-open [start, end) and merging intervals correctly remains essential.Final Answer:
Option D -> Option DQuick Check:
Adjust bisect and interval representation for negatives and reuse [OK]
Hint: Half-open intervals and bisect handle negatives and reuse correctly [OK]
Common Mistakes:
- Thinking data structure must change to segment tree unnecessarily