We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Design Browser History

Number: 1582

Difficulty: Medium

Paid? No

Companies: Bloomberg, Amazon, Uber, Roblox, Microsoft, Google, Apple, Splunk, Cisco

Problem Description

Design a BrowserHistory class to simulate a browser with one tab that starts at a given homepage. The class should support visiting new URLs, moving back by a specified number of steps in the history, and moving forward in the history. When visiting a new page, clear all forward history.

Key Insights

  • Use a list (or similar data structure) to store the browsing history.
  • Maintain an index pointer to track the current page.
  • When visiting a URL, remove all forward history beyond the current page.
  • For the back operation, decrement the pointer by the given steps, ensuring it does not go below 0.
  • For the forward operation, increment the pointer by the given steps, ensuring it does not exceed the last visited page.

Space and Time Complexity

Time Complexity:

  • visit: O(1) on average (slicing the forward history may take O(n) in worst-case but steps are bounded).
  • back and forward: O(1) per operation.

Space Complexity:

  • O(n) where n is the number of visited URLs.

Solution

We maintain an array (or list) for the history and an integer pointer to mark the current page.
When visiting a new URL, we remove any forward history, append the new URL, and update the pointer.
For back, we decrement the pointer ensuring it does not go below zero; for forward, we increase the pointer ensuring it does not exceed the available history.
This approach ensures that all operations run efficiently with minimal overhead.

Code Solutions

# Python Implementation of BrowserHistory

class BrowserHistory:
    def __init__(self, homepage: str):
        # Initialize history with the homepage and set current index to 0
        self.history = [homepage]
        self.curr = 0

    def visit(self, url: str) -> None:
        # Clear forward history by slicing the current history up to and including current page
        self.history = self.history[:self.curr + 1]
        # Append the new URL to history
        self.history.append(url)
        # Move current pointer to the end of the history
        self.curr += 1

    def back(self, steps: int) -> str:
        # Move the pointer 'steps' back but don't go below index 0
        self.curr = max(0, self.curr - steps)
        # Return the URL at the new current position
        return self.history[self.curr]

    def forward(self, steps: int) -> str:
        # Move the pointer 'steps' forward but don't exceed the last index in history
        self.curr = min(len(self.history) - 1, self.curr + steps)
        # Return the URL at the new current position
        return self.history[self.curr]
← Back to All Questions