Design Browser History

Intuition

Browsing is a straight line of pages with a cursor pointing at the page you are on. Everything before the cursor is your back history and everything after it is your forward history. When you visit a new page, any forward pages become unreachable, so we discard them and append the new page right after the cursor. Moving back or forward is just shifting the cursor, clamped so it never leaves the valid range of pages. Because the pages are stored in a contiguous array, every operation is a simple index update and lookup.

Algorithm walkthrough

1. 1Initialize the history list with the homepage and set the current index to 0.
2. 2For visit(url), drop every entry after the current index, append url, and advance the current index to point at it.
3. 3For back(steps), subtract steps from the current index but never go below 0, then return the url at that index.
4. 4For forward(steps), add steps to the current index but never exceed the last valid index, then return the url at that index.
5. 5Truncating on visit is what enforces the rule that navigating to a new page erases the forward history.
6. 6Each operation touches only the index and, at most, trims or appends to the tail, so it is effectively constant time per navigation.

Implementation

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

    def visit(self, url: str) -> None:
        del self.history[self.current + 1:]
        self.history.append(url)
        self.current += 1

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

    def forward(self, steps: int) -> str:
        self.current = min(len(self.history) - 1, self.current + steps)
        return self.history[self.current]