Interview Preplinked-list-advancedmediumAmazonGoogleFacebook

Design Browser History (Forward/Back)

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

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.

class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]  # STEP 1
        self.forward_stack = []      # STEP 1

    def visit(self, url: str) -> None:
        self.back_stack.append(url)  # STEP 2,3,4,8
        self.forward_stack.clear()   # STEP 2,3,4,8

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())  # STEP 5,6,10,11
            steps -= 1
        return self.back_stack[-1]  # STEP 5,6,7,9,10,11

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())  # STEP 7,9
            steps -= 1
        return self.back_stack[-1]  # STEP 7,9

if __name__ == '__main__':
    browserHistory = BrowserHistory("leetcode.com")  # STEP 1
    browserHistory.visit("google.com")               # STEP 2
    browserHistory.visit("facebook.com")             # STEP 3
    browserHistory.visit("youtube.com")              # STEP 4
    print(browserHistory.back(1))                      # STEP 5
    print(browserHistory.back(1))                      # STEP 6
    print(browserHistory.forward(1))                   # STEP 7
    browserHistory.visit("linkedin.com")             # STEP 8
    print(browserHistory.forward(2))                   # STEP 9
    print(browserHistory.back(2))                       # STEP 10
    print(browserHistory.back(7))                       # STEP 11

📊

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

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

Start learning this pattern below

Initialize BrowserHistory with homepage

Visit 'google.com'

Visit 'facebook.com'

Visit 'youtube.com'

Back 1 step

Back 1 step again

Forward 1 step

Visit 'linkedin.com' after going back and forward

Forward 2 steps (no effect)

Back 2 steps

Back 7 steps (limited by history)

Key Takeaways

Practice

Solution

Step 1: Calculate total nodes and part sizes

Step 2: Assign nodes to parts

Final Answer:

Quick Check:

Solution

Step 1: Identify the accumulation operation

Step 2: Understand impact on single-node lists

Final Answer:

Quick Check:

Solution

Step 1: Analyze Step 3 separation loop

Step 2: Identify fix

Final Answer:

Quick Check:

Solution

Step 1: Analyze group reversal cost

Step 2: Count total groups and total nodes processed

Final Answer:

Quick Check:

Solution

Step 1: Understand node reuse requirement

Step 2: Evaluate algorithm changes

Step 3: Discard other options

Final Answer:

Quick Check: