Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleFacebook

Design Browser History (Forward/Back)

Choose your preparation mode4 modes available

Start learning this pattern below

Jump into concepts and practice - no test required

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

Initialize BrowserHistory with homepage

Create the back stack with the homepage 'leetcode.com' as the only node. The forward stack is empty initially.

💡 Initialization sets the starting point for browsing history, ensuring there is always at least one page in the back stack.
Line:self.back_stack = [homepage] self.forward_stack = []
💡 The homepage is the base of the back stack and navigation cannot go back beyond it.
📊
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 fillAnswer 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 code snippet for splitting a linked list into k=3 parts, and the input list 1->2->3->4, what is the returned list of parts (values only)?
easy
A. [[1, 2], [3, 4], []]
B. [[1, 2], [3], [4]]
C. [[1, 2], [3], [4, None]]
D. [[1], [2], [3, 4]]

Solution

  1. Step 1: Calculate total nodes and part sizes

    Total nodes = 4, k = 3, so part_size = 1, remainder = 1. First remainder parts get one extra node.
  2. Step 2: Assign nodes to parts

    Part 0 size = 2 nodes (1,2), Part 1 size = 1 node (3), Part 2 size = 1 node (4). The returned parts are [[1,2],[3],[4]].
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum of parts equals original list length and sizes differ by at most one [OK]
Hint: Remainder nodes assigned to first parts -> first part larger [OK]
Common Mistakes:
  • Assigning remainder nodes to last parts
  • Off-by-one in part sizes
  • Returning fewer than k parts
2. Consider the following buggy recursive code to convert a binary number in a linked list to an integer. Which line contains the subtle bug that causes incorrect output for single-node lists?
medium
A. Line X: using addition instead of bitwise OR to accumulate bits
B. Line 7: base case check for None node
C. Line 3: __init__ method of ListNode
D. Line 9: recursive call with node.next and updated acc

Solution

  1. Step 1: Identify the accumulation operation

    The code uses bitwise OR instead of addition to combine bits: acc = (acc << 1) | node.val.
  2. Step 2: Understand impact on single-node lists

    Bitwise OR correctly sets bits without carry, ensuring accurate accumulation for all list lengths.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Bitwise OR correctly sets bits without carry, addition may overflow [OK]
Hint: Use bitwise OR, not addition, to accumulate bits [OK]
Common Mistakes:
  • Using + instead of | causes wrong bit accumulation
  • Misunderstanding bitwise operations vs arithmetic
  • Assuming addition and OR are interchangeable for bits
3. Identify the bug in the following code snippet implementing the optimal approach to copy a list with random pointers:
medium
A. Line assigning curr.next.random = curr.random.next misses null check for curr.random
B. In Step 3, copy_curr is never advanced, causing incorrect separation
C. In Step 1, new_node is linked incorrectly to curr.next
D. The function returns copy_head before fully separating the lists

Solution

  1. Step 1: Analyze Step 3 separation loop

    copy_curr is initialized but never advanced inside the loop, so copied list links are not updated correctly.
  2. Step 2: Identify fix

    Adding copy_curr = copy_curr.next inside the loop after updating copy_curr.next fixes the bug.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Without advancing copy_curr, copied list remains partially linked [OK]
Hint: Check if both original and copy pointers advance in separation loop [OK]
Common Mistakes:
  • Forgetting to advance copy_curr in separation
  • Assuming random pointer null checks are missing (they are present)
  • Mislinking new_node in Step 1 (correct here)
4. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?
medium
A. O(nk), because each group reversal takes O(k) and there are n/k groups.
B. O(n), because each node is visited and reversed exactly once.
C. O(n log k), because reversing each group involves log k steps due to pointer updates.
D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

  1. Step 1: Analyze group reversal cost

    Each group of k nodes is reversed in O(k) time.
  2. Step 2: Count total groups and total nodes processed

    There are approximately n/k groups, so total time is O(k * n/k) = O(n).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Each node is processed once during reversal [OK]
Hint: Total nodes processed once -> O(n) time [OK]
Common Mistakes:
  • Multiplying n by k incorrectly
  • Assuming log k factor in reversal
  • Ignoring that groups partition the list
5. Suppose the problem is modified so that the linked list nodes can be reused across parts (i.e., nodes can appear in multiple parts). Which of the following changes to the algorithm correctly handles this variant?
hard
A. No changes needed; the original algorithm already supports node reuse by splitting normally.
B. Modify the algorithm to skip cutting pointers and just record start nodes for each part, allowing overlap.
C. Use a hash map to track nodes already assigned and avoid duplicates during splitting.
D. Instead of cutting the list, create new nodes for each part to allow reuse without modifying the original list.

Solution

  1. Step 1: Understand node reuse requirement

    Nodes can appear in multiple parts, so original list must remain intact.
  2. Step 2: Evaluate algorithm changes

    Original algorithm cuts pointers, destroying original list structure. To allow reuse, new nodes must be created for each part.
  3. Step 3: Discard other options

    Skipping cutting pointers causes overlapping parts but does not create separate nodes. Hash map tracking is unnecessary and inefficient.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Creating new nodes preserves original list and allows reuse [OK]
Hint: Node reuse requires copying nodes, not pointer cutting [OK]
Common Mistakes:
  • Assuming original algorithm supports reuse
  • Trying to reuse nodes without copying
  • Overcomplicating with tracking structures