Design Browser History (Forward/Back)

📋

Problem

Imagine you are building a web browser that allows users to navigate back and forth through their browsing history seamlessly.

Design a browser history system that supports visiting new URLs, moving back by a certain number of steps, and moving forward by a certain number of steps. Implement the BrowserHistory class with the following methods: - BrowserHistory(string homepage): Initializes the object with the homepage. - void visit(string url): Visits url from the current page. It clears up all the forward history. - string back(int steps): Move steps back in history. Return the current URL after moving back. - string forward(int steps): Move steps forward in history. Return the current URL after moving forward.

1 ≤ steps ≤ 1001 ≤ url.length ≤ 20At most 5000 calls will be made to visit, back, and forward.

Edge cases: Back steps more than history length → returns earliest pageForward steps more than forward history → returns latest pageVisit after back truncates forward history

</>

IDE

class BrowserHistory: def __init__(self, homepage: str): ... def visit(self, url: str) -> None: ... def back(self, steps: int) -> str: ... def forward(self, steps: int) -> str: ...public class BrowserHistory { public BrowserHistory(String homepage) { ... } public void visit(String url) { ... } public String back(int steps) { ... } public String forward(int steps) { ... } }class BrowserHistory { public: BrowserHistory(string homepage) { ... } void visit(string url) { ... } string back(int steps) { ... } string forward(int steps) { ... } };class BrowserHistory { constructor(homepage) { ... } visit(url) { ... } back(steps) { ... } forward(steps) { ... } }

class BrowserHistory:
    def __init__(self, homepage: str):
        # Write your solution here
        pass
    def visit(self, url: str) -> None:
        pass
    def back(self, steps: int) -> str:
        pass
    def forward(self, steps: int) -> str:
        pass

public class BrowserHistory {
    public BrowserHistory(String homepage) {
        // Write your solution here
    }
    public void visit(String url) {
    }
    public String back(int steps) {
        return "";
    }
    public String forward(int steps) {
        return "";
    }
}

#include <string>
using namespace std;
class BrowserHistory {
public:
    BrowserHistory(string homepage) {
        // Write your solution here
    }
    void visit(string url) {
    }
    string back(int steps) {
        return "";
    }
    string forward(int steps) {
        return "";
    }
};

class BrowserHistory {
    constructor(homepage) {
        // Write your solution here
    }
    visit(url) {
    }
    back(steps) {
        return "";
    }
    forward(steps) {
        return "";
    }
}

Common Bugs to Avoid

Wrong: "youtube.com" instead of "facebook.com" after back(1) in canonical testNot truncating forward history on visit, so forward pointer moves incorrectly.✅ On visit, slice history list to current index + 1 before appending new URL.

Wrong: "page1.com" instead of "startpage.com" after back(1) when at startBack pointer moves below zero, allowing invalid negative index.✅ Clamp back pointer with max(0, curr - steps).

Wrong: "page2.com" instead of "page3.com" after forward(1) following visitForward history not cleared after visit following back.✅ Truncate forward history on visit by slicing history list to curr + 1.

Wrong: Timeout or TLE on large inputUsing list slicing or linear operations on visit causing O(n) per visit.✅ Use doubly linked list or two stacks to achieve O(1) amortized visit, back, and forward.

✓

Test Cases

Focus on handling empty and minimal history cases correctly, especially pointer bounds.

Test sequences mixing back, forward, and visit carefully to catch truncation bugs.

Optimize your data structure to avoid linear operations on visit; consider linked lists or stacks.

t1_01basic

Input{"commands":["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"],"args":[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]}

Expected[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

⏱ Performance - must finish in 2000ms

Start at 'leetcode.com'. Visit 'google.com', 'facebook.com', 'youtube.com'. Back 1 step to 'facebook.com', back 1 step to 'google.com', forward 1 step to 'facebook.com'. Visit 'linkedin.com' which clears forward history. Forward 2 steps stays at 'linkedin.com' (no forward history). Back 2 steps to 'google.com', back 7 steps to 'leetcode.com' (can't go back further).

💡 Model history as a list with a current index pointer.

💡 Visiting a new URL truncates all forward history beyond current index.

💡 Back and forward move the pointer within valid bounds and return the URL at that position.

Why it failed: Incorrect output indicates failure to truncate forward history on visit or incorrect pointer movement in back/forward. Fix by slicing history list on visit and bounding pointer updates.

✓ Correctly handles visit, back, and forward operations with proper history truncation and pointer movement.

t1_02basic

Input{"commands":["BrowserHistory","visit","back","visit","forward","back","back"],"args":[["startpage.com"],["page1.com"],[1],["page2.com"],[1],[1],[1]]}

Expected[null,null,"startpage.com",null,"page2.com","startpage.com","startpage.com"]

⏱ Performance - must finish in 2000ms

Start at 'startpage.com'. Visit 'page1.com'. Back 1 step to 'startpage.com'. Visit 'page2.com' truncates forward history. Forward 1 step stays at 'page2.com' (no forward history). Back 1 step to 'startpage.com'. Back 1 step stays at 'startpage.com' (can't go back further).

💡 Check that visit after back clears forward history.

💡 Back cannot move beyond the first page.

💡 Forward cannot move beyond the last visited page.

Why it failed: Failing this test usually means forward history was not cleared after visit or back/forward bounds are not enforced. Fix by truncating forward history on visit and bounding pointer updates.

✓ Properly truncates forward history on visit and bounds back/forward pointer correctly.

t2_01edge

Input{"commands":["BrowserHistory","back","forward"],"args":[["homepage.com"],[1],[1]]}

Expected[null,"homepage.com","homepage.com"]

⏱ Performance - must finish in 2000ms

Start at 'homepage.com'. Back 1 step returns 'homepage.com' since no history before homepage. Forward 1 step returns 'homepage.com' since no forward history.

💡 Test behavior when no history to go back or forward.

💡 Back and forward should not move pointer beyond valid range.

💡 Return current URL if back or forward steps exceed history bounds.

Why it failed: Failing this test means back or forward moves pointer out of valid range. Fix by bounding pointer with max(0, curr - steps) and min(last_index, curr + steps). This is the empty forward/back history edge case.

✓ Correctly handles back and forward calls when no history exists.

t2_02edge

Input{"commands":["BrowserHistory","visit","back","forward"],"args":[["onlypage.com"],["onlypage.com"],[1],[1]]}

Expected[null,null,"onlypage.com","onlypage.com"]

⏱ Performance - must finish in 2000ms

Start at 'onlypage.com'. Visit same page again (allowed). Back 1 step returns 'onlypage.com' (no earlier page). Forward 1 step returns 'onlypage.com' (no forward page).

💡 Test single element repeated visits.

💡 Back and forward should handle single element history gracefully.

💡 Ensure visit truncates forward history even if URL is same.

Why it failed: Failing means forward history not truncated on visit or pointer moves incorrectly with single element. Fix by truncating forward history on visit and bounding pointer updates.

✓ Handles single element repeated visits and pointer bounds correctly.

t2_03edge

Input{"commands":["BrowserHistory","visit","visit","back","back","back","forward","forward","forward"],"args":[["start.com"],["a.com"],["b.com"],[1],[1],[1],[1],[1],[1]]}

Expected[null,null,null,"a.com","start.com","start.com","a.com","b.com","b.com"]

⏱ Performance - must finish in 2000ms

Start at 'start.com'. Visit 'a.com', then 'b.com'. Back 1 step to 'a.com', back 1 step to 'start.com', back 1 step stays at 'start.com'. Forward 1 step to 'a.com', forward 1 step to 'b.com', forward 1 step stays at 'b.com'.

💡 Test exact boundary when back or forward steps equal history length.

💡 Back and forward should not move pointer beyond earliest or latest page.

💡 Check pointer bounds carefully when steps exceed history length.

Why it failed: Failing means pointer moves beyond valid range on exact boundary steps. Fix by bounding pointer with max and min functions. This is the exact boundary edge case.

✓ Correctly handles back and forward at exact history boundaries.

t3_01corner

Input{"commands":["BrowserHistory","visit","visit","back","visit","forward"],"args":[["home.com"],["page1.com"],["page2.com"],[1],["page3.com"],[1]]}

Expected[null,null,null,"page1.com",null,"page3.com"]

⏱ Performance - must finish in 2000ms

Start at 'home.com'. Visit 'page1.com', then 'page2.com'. Back 1 step to 'page1.com'. Visit 'page3.com' truncates forward history (removes 'page2.com'). Forward 1 step stays at 'page3.com' (no forward history).

💡 Check that visiting after back truncates forward history correctly.

💡 Forward after visit should not move beyond current page.

💡 Ensure forward history is cleared on visit after back.

Why it failed: Failing means forward history not truncated after visit following back. Fix by slicing history list to current index + 1 before appending new URL. This is the forward history truncation corner case.

✓ Properly truncates forward history after visit following back.

t3_02corner

Input{"commands":["BrowserHistory","visit","back","back","forward","forward"],"args":[["start.com"],["page1.com"],[1],[1],[1],[1]]}

Expected[null,null,"start.com","start.com","page1.com","page1.com"]

⏱ Performance - must finish in 2000ms

Start at 'start.com'. Visit 'page1.com'. Back 1 step to 'start.com'. Back 1 step stays at 'start.com'. Forward 1 step to 'page1.com'. Forward 1 step stays at 'page1.com'.

💡 Test multiple back calls beyond start and multiple forward calls beyond end.

💡 Back and forward should clamp pointer within valid range.

💡 Check pointer updates do not go negative or exceed last index.

Why it failed: Failing means pointer moves out of bounds on multiple back or forward calls. Fix by bounding pointer with max(0, curr - steps) and min(last_index, curr + steps). This is the pointer bounds corner case.

✓ Correctly clamps pointer within valid history range on multiple back/forward calls.

t3_03corner

Input{"commands":["BrowserHistory","visit","visit","visit","back","back","forward","forward","back","visit","forward"],"args":[["home.com"],["a.com"],["b.com"],["c.com"],[2],[2],[2],[2],[1],["d.com"],[2]]}

Expected[null,null,null,null,"a.com","home.com","b.com","c.com","b.com",null,"d.com"]

⏱ Performance - must finish in 2000ms

Start at 'home.com'. Visit 'a.com', 'b.com', 'c.com'. Back 2 steps to 'a.com', back 2 steps stays at 'home.com'. Forward 2 steps to 'c.com', forward 2 steps stays at 'c.com'. Back 1 step to 'b.com'. Visit 'd.com' truncates forward history. Forward 2 steps stays at 'd.com'.

💡 Test complex sequence mixing back, forward, and visit operations.

💡 Ensure forward history truncation after visit works even after multiple back steps.

💡 Check pointer updates and history truncation in mixed operations.

Why it failed: Failing means forward history not truncated correctly after visit following back steps or pointer updates incorrect in mixed operations. Fix by truncating forward history on visit and bounding pointer updates. This is the mixed operations corner case.

✓ Handles complex sequences with correct pointer movement and forward history truncation.

t4_01performance

Input{"_description":"n=5000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Test with 5000 operations to ensure O(1) amortized time per operation. Brute force with list slicing may TLE.

💡 Use data structures with O(1) visit, back, and forward operations.

💡 Avoid copying or slicing large lists on visit.

💡 Implement with doubly linked list or two stacks for efficiency.

Why it failed: TLE indicates inefficient implementation, likely due to list slicing or linear operations per visit. Fix by using doubly linked list or two stacks to achieve O(1) amortized operations.

✓ Efficient implementation confirmed with O(1) amortized operations per visit, back, and forward.

Practice

1. 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

2. What is the time complexity of the addAtTail operation in the optimal linked list implementation that maintains a tail pointer and size variable?

medium

A. O(n), because traversal is needed to find the tail

B. O(log n), because the list is balanced using sentinel nodes

C. O(1), because the tail pointer allows direct access to the last node

D. O(n), because updating the size requires traversal

Solution

1. Step 1: Identify operation steps

   addAtTail uses the tail pointer to append a new node directly without traversal.

2. Step 2: Analyze complexity

   Since tail pointer gives direct access, adding at tail is O(1). Size update is O(1) as it's a simple increment.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Tail pointer eliminates traversal, so addAtTail is constant time [OK]

Hint: Tail pointer enables O(1) tail insertions [OK]

Common Mistakes:

• Assuming traversal needed to find tail
• Confusing size update cost
• Thinking sentinel nodes balance list

3. What is the time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list with total n nodes, considering the worst-case scenario where each node has a child list?

medium

A. O(n) amortized, since the total number of pointer updates and traversals sums to linear over all nodes.

B. O(n) because each node is visited a constant number of times during the flattening process.

C. O(n^2) because for each node with a child, we traverse its entire child list to find the tail.

D. O(n log n) due to repeated tail searches in nested child lists.

Solution

1. Step 1: Analyze tail-finding loop

   Although tail is found by traversing child lists, each node is visited at most once as tail or curr.

2. Step 2: Amortized analysis

   All next pointers are traversed linearly; tail searches do not overlap nodes multiple times, so total work is linear.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Each node processed once, tail searches amortize to O(n) [OK]

Hint: Tail searches look nested but total visits are linear [OK]

Common Mistakes:

• Assuming tail search is repeated fully for each child causing O(n^2)
• Confusing amortized with worst-case per iteration
• Ignoring that nodes are not revisited multiple times

4. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause incorrect backward traversal of the flattened list?

medium

A. Line: Missing child.prev = curr assignment

B. Line: if curr.next: curr.next.prev = tail

C. Line: curr.next = child

D. Line: tail.next = curr.next

Solution

1. Step 1: Identify pointer updates

   After connecting curr.next to child, child's prev pointer must point back to curr.

2. Step 2: Locate missing update

   The code misses setting child.prev = curr, breaking backward links and causing incorrect prev traversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without child.prev update, backward traversal fails [OK]

Hint: Always update both next and prev pointers when splicing lists [OK]

Common Mistakes:

• Forgetting to update child's prev pointer
• Assuming tail.next update fixes all pointers
• Confusing next and prev pointer roles

5. Suppose the linked list nodes can be reused multiple times (i.e., the list is circular or nodes can appear multiple times). Which modification to the odd-even rearrangement algorithm is necessary to handle this scenario correctly?

hard

A. Add a visited set to track nodes already processed to avoid infinite loops or duplicates

B. No modification needed; the original in-place algorithm works correctly even with reused nodes

C. Convert the list to an array first, then reorder and reconstruct the list to handle duplicates

D. Use recursion to process nodes and detect cycles automatically

Solution

1. Step 1: Identify problem with reused nodes

   If nodes are reused or list is circular, naive pointer traversal causes infinite loops or duplicates.

2. Step 2: Use a visited set

   Tracking visited nodes prevents revisiting and infinite loops, ensuring correct rearrangement.

3. Step 3: Why other options fail

   No modification ignores cycles; array conversion adds overhead; recursion risks stack overflow without cycle detection.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Visited set is standard for cycle detection in linked lists [OK]

Hint: Detect cycles with visited set to avoid infinite loops [OK]

Common Mistakes:

• Assuming original algorithm handles cycles or reused nodes
• Using recursion without cycle detection