Practice
copy_curr.random.val after the last iteration of the separation step (Step 3)?Solution
Step 1: Trace Step 1 (Interleaving nodes)
Original list: 1->2->3. After interleaving: 1->1'->2->2'->3->3'.Step 2: Trace Step 2 (Assign random pointers)
Node 1's random points to 3, so 1'.random = 3'. Node 2's random points to 1, so 2'.random = 1'. Node 3's random is null, so 3'.random = null.Step 3: Trace Step 3 (Separate lists)
After separation, copy_curr starts at 1'. After last iteration, copy_curr is at 3'. Its random pointer is null, so copy_curr.random.val does not exist.Final Answer:
Option C -> Option CQuick Check:
copy_curr.random is null after last iteration [OK]
- Confusing original and copied nodes during separation
- Off-by-one error in advancing copy_curr
- Assuming random pointers remain unchanged
browserHistory = BrowserHistory("leetcode.com")
browserHistory.visit("google.com")
browserHistory.visit("facebook.com")
browserHistory.visit("youtube.com")
print(browserHistory.back(1))
print(browserHistory.back(1))
print(browserHistory.forward(1))
Solution
Step 1: Trace back(1) after visiting youtube.com
back_stack = ["leetcode.com", "google.com", "facebook.com", "youtube.com"] Pop "youtube.com" to forward_stack, back_stack top is "facebook.com".Step 2: Trace back(1) again and forward(1)
Second back(1): pop "facebook.com" to forward_stack, top is "google.com". Forward(1): pop "facebook.com" from forward_stack back to back_stack, top is "facebook.com".Final Answer:
Option C -> Option CQuick Check:
Last forward returns "facebook.com" as expected [OK]
- Off-by-one errors in popping stacks
- Confusing forward and back stacks
- Returning wrong top element after operations
x. The task is to reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each partition. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?Solution
Step 1: Understand the problem constraints
The problem requires partitioning the list around value x while preserving relative order and achieving O(n) time and O(1) space.Step 2: Evaluate approaches
Approach A uses extra arrays, so space is O(n). Approach B uses extra lists, so space is O(n). Approach D sorts the list, which is O(n log n) time. Only approach C rearranges nodes in-place in one pass with constant space.Final Answer:
Option D -> Option DQuick Check:
In-place rearrangement achieves O(n) time and O(1) space [OK]
- Assuming sorting is needed to partition
- Using extra arrays or lists increases space
- Believing two separate lists always use constant space
Solution
Step 1: Identify auxiliary space usage
The optimal approach weaves copied nodes directly into the original list without using extra hash maps or recursion.Step 2: Confirm space complexity
Only new nodes are created, which is required output space, so auxiliary space is O(1).Final Answer:
Option D -> Option DQuick Check:
No extra data structures or recursion stack used [OK]
- Confusing output space with auxiliary space
- Assuming recursion is used and adds stack space
- Thinking random pointers require extra space
def oddEvenList(head):
if not head or not head.next:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
# Missing termination of even list
odd.next = even_head
return head
What is the consequence of the missing line and how to fix it?Solution
Step 1: Understand pointer termination
Without setting even.next = None, the even list may still point to old nodes, causing cycles or infinite loops.Step 2: Fix by terminating even list
Adding 'if even: even.next = None' before linking odd.next ensures even list ends properly.Final Answer:
Option D -> Option DQuick Check:
Proper termination prevents cycles and infinite traversal [OK]
- Forgetting to terminate even list causing infinite loops
- Misplacing pointer updates causing node skips
