Design Browser History
Medium · Design · Array · Linked List · Stack · Design · Doubly-Linked List · Data Stream
Problem
Model the history of a single browser tab. The tab starts on a homepage; from there you can visit new pages and move back or forward through the pages you have seen.
Implement BrowserHistory:
- BrowserHistory(string homepage) opens the tab on homepage.
- void visit(string url) goes to url from the current page and erases all forward history.
- string back(int steps) moves back up to steps pages (stopping at the oldest page) and returns the current URL.
- string forward(int steps) moves forward up to steps pages (stopping at the newest page) and returns the current URL.
Each test is a list of calls: ops[i] is the method name (the first is the class) and args[i] its arguments. The expected output lists each call’s return value, None for the constructor and visit.
Examples
Input: ops = ["BrowserHistory","visit","visit","back","back","forward","visit","forward","back"], args = [["home.io"],["a.io"],["b.io"],[1],[5],[1],["c.io"],[2],[1]] Output: [None, None, None, 'a.io', 'home.io', 'a.io', None, 'c.io', 'a.io']
Back 5 stops at home.io. Visiting c.io from a.io erases b.io, so forward stays on c.io.
Input: ops = ["BrowserHistory","back","forward"], args = [["x.com"],[3],[3]] Output: [None, 'x.com', 'x.com']
With a single page there is nowhere to move.
Input: ops = ["BrowserHistory","visit","visit","visit","back","forward"], args = [["h.io"],["p.io"],["q.io"],["r.io"],[2],[7]] Output: [None, None, None, None, 'p.io', 'r.io']
Back 2 lands on p.io; forward 7 stops at the newest page, r.io.
Constraints
- 1 <= len(homepage), len(url) <= 20
- 1 <= steps <= 100
- homepage and url contain '.' or lowercase English letters
- At most 5000 calls are made to visit, back and forward
Approaches
- Two stacks, one step at a time — time O(steps) per move, space O(n)
Follow-up
Real browsers keep a tree, not a line: going back and visiting a new page does not throw the old forward pages away, it starts a new branch. To support that, store each page as a node with a parent and a list of children, and let forward follow the most recently visited child.
Related problems
Start free on Cariara · Coding problems · System design studio
