Design Browser History

Problem

Design a browser history for a single tab. Implement BrowserHistory(String homepage), void visit(String url) — visit url from the current page and clear all forward history; String back(int steps) — move back up to steps pages (clamped at the homepage) and return the current url; String forward(int steps) — move forward up to steps pages (clamped at the most recent) and return the current url.

Constraints

• 1 ≤ url.length ≤ 20
• 1 ≤ steps ≤ 100
• at most 5000 total calls

Approach — Stack

This is a Stack problem. The idea: scan the input once, pushing work onto a stack and popping when the top can be resolved, so the stack always reflects what's still open. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

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

    def visit(self, url):
        del self.history[self.cur + 1:]
        self.history.append(url)
        self.cur += 1

    def back(self, steps):
        self.cur = max(0, self.cur - steps)
        return self.history[self.cur]

    def forward(self, steps):
        self.cur = min(len(self.history) - 1, self.cur + steps)
        return self.history[self.cur]

Java

import java.util.*;

class BrowserHistory {
    // Two stacks — the canonical undo / redo design. Pages behind you
    // live on one stack, pages ahead (after going back) on the other.
    private final Deque<String> backStack = new ArrayDeque<>();
    private final Deque<String> forwardStack = new ArrayDeque<>();
    private String current;

    public BrowserHistory(String homepage) {
        current = homepage;
    }

    public void visit(String url) {
        backStack.push(current);
        current = url;
        forwardStack.clear();   // visiting destroys the forward history
    }

    public String back(int steps) {
        while (steps-- > 0 && !backStack.isEmpty()) {
            forwardStack.push(current);
            current = backStack.pop();
        }
        return current;
    }

    public String forward(int steps) {
        while (steps-- > 0 && !forwardStack.isEmpty()) {
            backStack.push(current);
            current = forwardStack.pop();
        }
        return current;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.