Design Browser History — Solution in Python, Java & C++
Design Browser History solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Design Browser History is a medium coding problem on arrays and stack, asked in Amazon, Google, Microsoft and Bloomberg interviews.
- Difficulty: Medium
- Topics: Arrays, Stack
- Asked at: Amazon, Google, Microsoft, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Model a single browser tab: it starts on a home page, visits other pages, and can move back and forward through its history.
Write the class BrowserHistory:
BrowserHistory(String homepage)opens the tab onhomepage.void visit(String url)goes from the current page tourl. This erases all forward history.String back(int steps)moves backstepspages — or as far as the history allows, if fewer thanstepspages lie behind — and returns the page it ends on.String forward(int steps)moves forwardstepspages — or as far as possible — and returns the page it ends on.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.
Example 1
Input: ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["codekairo.com"],["mail.com"],["maps.com"],["news.com"],[1],[1],[1],["docs.com"],[2],[2],[7]]
Output: [null,null,null,null,"maps.com","mail.com","maps.com",null,"docs.com","mail.com","codekairo.com"]
Explanation: After three visits the history is codekairo.com, mail.com, maps.com, news.com. Two single steps back land on maps.com then mail.com, and one forward on maps.com. Visiting docs.com from there drops news.com, so forward(2) cannot move. back(2) reaches mail.com, and back(7) stops at the home page.
Example 2
Input: ["BrowserHistory","back","forward","visit","back"]
[["home"],[3],[3],["a.in"],[100]]
Output: [null,"home","home",null,"home"]
Explanation: With only the home page, neither back nor forward can move. After visiting a.in, back(100) returns to home.
Constraints
1 <= homepage.length, url.length <= 20homepage and url consist of lowercase English letters and '.'1 <= steps <= 100At most 5000 calls are made to visit, back and forward
Hints for Design Browser History
Hint 1
The history is a line of pages with a cursor on the current one; back and forward just move the cursor.
Hint 2
Keep the pages in an array with an index
curfor the current page and an indexlastfor the furthest page you can go forward to.Hint 3
visitwrites the new page atcur + 1(overwriting whatever was there) and setslast = cur.backclampscur - stepsat 0,forwardclampscur + stepsatlast— both O(1).
How to solve Design Browser History
One array and two indices: cur, the page being shown, and last, the end of the forward history. Erasing the forward history is just moving last — the stale entries are overwritten later.
Approach
- Start with
pages = [homepage],cur = last = 0. visit(url):cur++; writeurlatpages[cur](append if the array is that short); setlast = cur.back(steps):cur = max(0, cur - steps); returnpages[cur].forward(steps):cur = min(last, cur + steps); returnpages[cur].
Why it works
pages[0..last] is always exactly the tab's history and cur its position in it: a visit keeps the pages up to the current one, adds the new page right after it and makes it the end, which is what erasing the forward history means. Moving back or forward can never leave [0, last], and clamping gives the "as far as possible" rule.
Complexity
- Time —
O(1) per call (amortised for the array growth) - Space —
O(number of visits)
Pitfalls
- Forgetting to reset
laston a visit letsforwardreach pages that were erased. - Using
pages.length - 1as the forward limit has the same bug when stale entries remain pastlast. - Two stacks (back and forward) also work, but each step of
back/forwardis then O(1) per page moved, O(steps) per call.
Reference solution
Python
class BrowserHistory:
def __init__(self, homepage: str):
self.pages = [homepage]
self.cur = 0
self.last = 0 # pages[0..last] is the history
def visit(self, url: str) -> None:
self.cur += 1
if self.cur == len(self.pages):
self.pages.append(url)
else:
self.pages[self.cur] = url
self.last = self.cur # erases the forward history
def back(self, steps: int) -> str:
self.cur = max(0, self.cur - steps)
return self.pages[self.cur]
def forward(self, steps: int) -> str:
self.cur = min(self.last, self.cur + steps)
return self.pages[self.cur]Java
class BrowserHistory {
private List<String> pages = new ArrayList<>();
private int cur = 0, last = 0; // pages[0..last] is the history
public BrowserHistory(String homepage) {
pages.add(homepage);
}
public void visit(String url) {
cur++;
if (cur == pages.size()) pages.add(url); else pages.set(cur, url);
last = cur; // erases the forward history
}
public String back(int steps) {
cur = Math.max(0, cur - steps);
return pages.get(cur);
}
public String forward(int steps) {
cur = Math.min(last, cur + steps);
return pages.get(cur);
}
}C++
class BrowserHistory {
vector<string> pages;
int cur = 0, last = 0; // pages[0..last] is the history
public:
BrowserHistory(string homepage) : pages{homepage} {}
void visit(string url) {
cur++;
if (cur == (int)pages.size()) pages.push_back(url); else pages[cur] = url;
last = cur; // erases the forward history
}
string back(int steps) {
cur = max(0, cur - steps);
return pages[cur];
}
string forward(int steps) {
cur = min(last, cur + steps);
return pages[cur];
}
};JavaScript
var BrowserHistory = function(homepage) {
this.pages = [homepage];
this.cur = 0;
this.last = 0; // pages[0..last] is the history
};
BrowserHistory.prototype.visit = function(url) {
this.pages[++this.cur] = url;
this.last = this.cur; // erases the forward history
};
BrowserHistory.prototype.back = function(steps) {
this.cur = Math.max(0, this.cur - steps);
return this.pages[this.cur];
};
BrowserHistory.prototype.forward = function(steps) {
this.cur = Math.min(this.last, this.cur + steps);
return this.pages[this.cur];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Stack Data Structure