Design Browser History (Forward/Back) - Watch the Algorithm Execute, Step by Step
Watching each operation step-by-step reveals how the back and forward stacks interact, clarifying the logic behind clearing forward history on visits and limiting back navigation.
Step 1/11
·Active fill★Answer cell
setup
leetcode.com
insert
leetcode.com
→
google.com
insert
leetcode.com
→
google.com
→
facebook.com
insert
leetcode.com
→
google.com
→
facebook.com
→
youtube.com
shrink
leetcode.com
→
google.com
→
facebook.com
→
youtube.com
Result: facebook.com
shrink
leetcode.com
→
google.com
→
facebook.com
→
youtube.com
Result: google.com
expand
leetcode.com
→
google.com
→
facebook.com
→
youtube.com
Result: facebook.com
insert
leetcode.com
→
google.com
→
facebook.com
→
youtube.com
→
linkedin.com
expand
leetcode.com
→
google.com
→
facebook.com
→
linkedin.com
→
youtube.com
Result: linkedin.com
shrink
leetcode.com
→
google.com
→
facebook.com
→
linkedin.com
→
youtube.com
Result: google.com
shrink
leetcode.com
→
google.com
→
facebook.com
→
linkedin.com
→
youtube.com
Result: leetcode.com
Key Takeaways
✓ The back and forward stacks represent the browsing history and future navigation paths respectively.
This is hard to see from code alone because the stacks' interaction is implicit; visualization makes it explicit.
✓ Visiting a new page clears the forward stack, preventing forward navigation beyond the new page.
Understanding this clearing behavior is crucial to grasp why forward navigation sometimes does nothing.
✓ Back navigation stops at the homepage, ensuring there is always at least one page in the back stack.
This boundary condition is subtle in code but clear when watching the stacks shrink visually.
Practice
(1/5)
1. Given the following recursive code to convert a binary number in a linked list to an integer, what is the final output when the linked list is 1 -> 0 -> 1?
easy
A. 3
B. 7
C. 6
D. 5
Solution
Step 1: Trace helper with node1 (val=1), acc=0
acc = (0 << 1) | 1 = 1; recurse with node2
Step 2: Trace helper with node2 (val=0), acc=1
acc = (1 << 1) | 0 = 2; recurse with node3
Step 3: Trace helper with node3 (val=1), acc=2
acc = (2 << 1) | 1 = 5; recurse with None
Step 4: Trace helper with None, acc=5
Return acc=5
Final Answer:
Option D -> Option D
Quick Check:
Binary 101 equals decimal 5 [OK]
Hint: Shift and OR accumulate bits from left to right [OK]
Common Mistakes:
Off-by-one errors in shifting
Confusing bitwise OR with addition
Returning intermediate instead of final accumulated value
2. Given the following code for odd-even linked list rearrangement, what is the output list after running the function on the input list [1, 2, 3, 4]?
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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
odd.next = even_head
return head
# Input list: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
new_head = oddEvenList(head)
curr = new_head
res = []
while curr:
res.append(curr.val)
curr = curr.next
print(res)
easy
A. [1, 2, 3, 4]
B. [1, 3, 2, 4]
C. [2, 4, 1, 3]
D. [1, 3, 4, 2]
Solution
Step 1: Trace first iteration of while loop
odd=1, even=2, even.next=3; odd.next=3, odd moves to 3; even.next=4, even moves to 4.
Step 2: Loop ends as even.next is null; link odd.next to even_head (2)
Final list order: 1 -> 3 -> 2 -> 4.
Final Answer:
Option B -> Option B
Quick Check:
Output matches expected odd-even rearrangement for input [1,2,3,4] [OK]
Hint: Odd nodes first, then even nodes in original order [OK]
Common Mistakes:
Confusing node values with indices
Off-by-one errors in pointer updates
3. What is the time complexity of the recursive approach that converts a binary number in a linked list to an integer by accumulating the value with bit shifts?
medium
A. O(n log n) due to bit shifts at each node
B. O(n^2) because recursion stack causes repeated computations
C. O(n) because each node is visited once with constant work
D. O(n) time but O(n^2) space due to recursion stack
Solution
Step 1: Analyze time per node
Each node is processed once, performing a constant number of bit operations (shift and OR).
Step 2: Consider recursion overhead
Recursion depth is n, but no repeated computations occur; each call does O(1) work.
Final Answer:
Option C -> Option C
Quick Check:
Linear traversal with constant work per node [OK]
Hint: Bit shifts are O(1) operations, not O(log n) [OK]
Common Mistakes:
Assuming bit shifts cost O(log n)
Confusing recursion stack space with time complexity
Thinking recursion causes repeated work
4. Examine the following buggy code snippet from an optimal linked list implementation. Which line contains the subtle bug that can cause the tail pointer to point to a deleted node after a deletion at the tail?
medium
A. Line 8: self.tail = prev
B. Line 6: prev.next = prev.next.next
C. Line 3: if index < 0 or index >= self.size:
D. Line 7: if index == self.size - 1:
Solution
Step 1: Understand tail update condition
The tail pointer should update when deleting the last node, which is at index size-1 before deletion.
Step 2: Identify bug
At line 8, the tail pointer is set to prev, but prev may not be the correct new tail if the deleted node was the last node. The tail pointer should be updated after size decrement and possibly set to the correct node.
Step 3: Correct fix
Update tail pointer after size decrement and ensure it points to the last node in the list.
Final Answer:
Option A -> Option A
Quick Check:
Tail pointer update must correctly reflect the new last node after deletion [OK]
Hint: Tail pointer update must be done carefully after deletion [OK]
Common Mistakes:
Updating tail before size decrement
Not updating tail on last node deletion
Incorrect traversal to prev node
5. What is the time and space complexity of the optimal in-place odd-even linked list rearrangement algorithm for a list of length n?
medium
A. Time: O(n), Space: O(1) because each node is visited once and rearranged in-place
B. Time: O(n log n), Space: O(1) due to sorting nodes by index parity
C. Time: O(n), Space: O(n) due to auxiliary lists for odd and even nodes
D. Time: O(n^2), Space: O(1) because of nested pointer updates
Solution
Step 1: Identify loop iterations
The while loop advances even and odd pointers through the list, each node visited once -> O(n) time.
Step 2: Analyze space usage
No extra data structures are created; rearrangement is done by pointer manipulation -> O(1) space.
Final Answer:
Option A -> Option A
Quick Check:
Linear time and constant space is standard for in-place linked list rearrangement [OK]
Hint: One pass with two pointers -> O(n) time, no extra lists -> O(1) space [OK]
Common Mistakes:
Assuming nested loops cause O(n^2) time
Confusing auxiliary space with recursion stack
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.