Bird
Raised Fist0
Interview Preplinked-list-advancedmediumAmazonGoogleFacebook

Design Browser History (Forward/Back)

Choose your preparation mode4 modes available
📋
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 "";
    }
}
0/9
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
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"]

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

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"]

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

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

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.

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

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

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"]

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

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"]

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

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"]

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

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"]

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

t4_01performance
Input{"_description":"n=5000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. 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
2. Given the following code for partitioning a linked list around value x = 3, and the input list: 1 -> 4 -> 2 -> 5, what is the final reordered list returned by the function?
easy
A. 1 -> 4 -> 2 -> 5
B. 1 -> 2 -> 4 -> 5
C. 2 -> 1 -> 4 -> 5
D. 4 -> 1 -> 2 -> 5

Solution

  1. Step 1: Trace initial pointers with input 1 -> 4 -> 2 -> 5 and x=3

    Start with dummy -> 1 -> 4 -> 2 -> 5, less_tail and prev at dummy, current at 1.
  2. Step 2: Process nodes

    Node 1 < 3, less_tail.next == current, move less_tail and prev forward. Node 4 >= 3, move prev and current forward. Node 2 < 3, less_tail.next != current, so remove 2 and insert after less_tail. Final list: 1 -> 2 -> 4 -> 5.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Nodes less than 3 appear first in original order, then others [OK]
Hint: Track less_tail and prev carefully to avoid skipping nodes [OK]
Common Mistakes:
  • Swapping values instead of nodes
  • Incorrect pointer updates causing lost nodes
  • Assuming order changes within partitions
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 space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?
medium
A. O(n) -- recursion stack uses space proportional to list length
B. O(1) -- only constant extra pointers used
C. O(log n) -- recursion depth is halved each call
D. O(n^2) -- due to repeated pointer updates in recursion

Solution

  1. Step 1: Identify recursion depth

    The helper function recurses once per node, so recursion depth is n.
  2. Step 2: Calculate space usage

    Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Recursion stack proportional to list length [OK]
Hint: Recursion depth equals list length -> O(n) space [OK]
Common Mistakes:
  • Assuming constant space due to in-place changes
  • Confusing recursion depth with log n
  • Overestimating to quadratic space
5. Suppose the multilevel doubly linked list can contain cycles via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the in-place iterative flattening algorithm correctly handles this scenario without infinite loops?
hard
A. Ignore cycles since the algorithm naturally terminates when curr is null.
B. Remove all child pointers before flattening to break cycles.
C. Use recursion with a depth limit to avoid infinite recursion.
D. Add a visited set to track nodes already processed and skip nodes if revisited.

Solution

  1. Step 1: Understand cycle problem

    Cycles via child pointers cause infinite loops if nodes are revisited during flattening.
  2. Step 2: Evaluate solutions

    Ignoring cycles (A) causes infinite loops. Removing child pointers (B) loses data. Recursion with depth limit (C) is unreliable. Tracking visited nodes (D) prevents revisiting and infinite loops.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Visited set prevents infinite loops in cyclic structures [OK]
Hint: Cycle detection requires tracking visited nodes explicitly [OK]
Common Mistakes:
  • Assuming no cycles exist in input
  • Relying on recursion depth limits
  • Ignoring child pointers that create cycles
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