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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Browser History

Difficulty: Medium

Problem Description

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps. Implement the BrowserHistory class with appropriate methods to manage the browsing history.

Key Insights

  • The browser maintains a history of visited URLs, allowing back and forward navigation.
  • Each visit clears the forward history, meaning only the current page and the back history are retained.
  • The back and forward methods need to handle cases where the user tries to navigate beyond the available history.

Space and Time Complexity

Time Complexity: O(1) for visit, back, and forward operations, but O(n) in the worst-case scenario for maintaining the history if we were to store all URLs. Space Complexity: O(n) for storing the history of URLs.

Solution

We can use a list (or array) to store the history of visited URLs. We will maintain two pointers: one for the current position in the history and another to keep track of the number of valid back and forward operations. When visiting a new URL, we will clear the forward history and update the current position. The back and forward methods will adjust the current position based on the steps requested, ensuring they do not exceed the available history.

Code Solutions

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.current_index = 0

    def visit(self, url: str) -> None:
        self.history = self.history[:self.current_index + 1]  # Clear forward history
        self.history.append(url)
        self.current_index += 1

    def back(self, steps: int) -> str:
        self.current_index = max(0, self.current_index - steps)  # Move back
        return self.history[self.current_index]

    def forward(self, steps: int) -> str:
        self.current_index = min(len(self.history) - 1, self.current_index + steps)  # Move forward
        return self.history[self.current_index]
← Back to All Questions