Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleFacebook

Design Browser History (Forward/Back)

Choose your preparation mode4 modes available
▶
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 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

  1. Step 1: Trace helper with node1 (val=1), acc=0

    acc = (0 << 1) | 1 = 1; recurse with node2
  2. Step 2: Trace helper with node2 (val=0), acc=1

    acc = (1 << 1) | 0 = 2; recurse with node3
  3. Step 3: Trace helper with node3 (val=1), acc=2

    acc = (2 << 1) | 1 = 5; recurse with None
  4. Step 4: Trace helper with None, acc=5

    Return acc=5
  5. Final Answer:

    Option D -> Option D
  6. 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

  1. 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.
  2. Step 2: Loop ends as even.next is null; link odd.next to even_head (2)

    Final list order: 1 -> 3 -> 2 -> 4.
  3. Final Answer:

    Option B -> Option B
  4. 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

  1. Step 1: Analyze time per node

    Each node is processed once, performing a constant number of bit operations (shift and OR).
  2. Step 2: Consider recursion overhead

    Recursion depth is n, but no repeated computations occur; each call does O(1) work.
  3. Final Answer:

    Option C -> Option C
  4. 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

  1. Step 1: Understand tail update condition

    The tail pointer should update when deleting the last node, which is at index size-1 before deletion.
  2. 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.
  3. Step 3: Correct fix

    Update tail pointer after size decrement and ensure it points to the last node in the list.
  4. Final Answer:

    Option A -> Option A
  5. 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

  1. Step 1: Identify loop iterations

    The while loop advances even and odd pointers through the list, each node visited once -> O(n) time.
  2. Step 2: Analyze space usage

    No extra data structures are created; rearrangement is done by pointer manipulation -> O(1) space.
  3. Final Answer:

    Option A -> Option A
  4. 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 unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard