Design Browser History

Medium
2067.

Design Browser History

Design Browser History is a medium coding problem on arrays and stack, asked in Amazon, Google, Microsoft and Bloomberg interviews.

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 on homepage.
  • void visit(String url) goes from the current page to url. This erases all forward history.
  • String back(int steps) moves back steps pages — or as far as the history allows, if fewer than steps pages lie behind — and returns the page it ends on.
  • String forward(int steps) moves forward steps pages — 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 <= 20
  • homepage and url consist of lowercase English letters and '.'
  • 1 <= steps <= 100
  • At most 5000 calls are made to visit, back and forward
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} homepage
 */
var BrowserHistory = function(homepage) {
    
};

/**
 * @param {string} url
 * @return {void}
 */
BrowserHistory.prototype.visit = function(url) {
    
};

/**
 * @param {number} steps
 * @return {string}
 */
BrowserHistory.prototype.back = function(steps) {
    
};

/**
 * @param {number} steps
 * @return {string}
 */
BrowserHistory.prototype.forward = function(steps) {
    
};

Sign in to run your own test cases

Sign in

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 on homepage.
  • void visit(String url) goes from the current page to url. This erases all forward history.
  • String back(int steps) moves back steps pages — or as far as the history allows, if fewer than steps pages lie behind — and returns the page it ends on.
  • String forward(int steps) moves forward steps pages — 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 <= 20
  • homepage and url consist of lowercase English letters and '.'
  • 1 <= steps <= 100
  • At most 5000 calls are made to visit, back and forward

Hints for Design Browser History

  1. Hint 1

    The history is a line of pages with a cursor on the current one; back and forward just move the cursor.

  2. Hint 2

    Keep the pages in an array with an index cur for the current page and an index last for the furthest page you can go forward to.

  3. Hint 3

    visit writes the new page at cur + 1 (overwriting whatever was there) and sets last = cur. back clamps cur - steps at 0, forward clamps cur + steps at last — 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

  1. Start with pages = [homepage], cur = last = 0.
  2. visit(url): cur++; write url at pages[cur] (append if the array is that short); set last = cur.
  3. back(steps): cur = max(0, cur - steps); return pages[cur].
  4. forward(steps): cur = min(last, cur + steps); return pages[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 last on a visit lets forward reach pages that were erased.
  • Using pages.length - 1 as the forward limit has the same bug when stale entries remain past last.
  • Two stacks (back and forward) also work, but each step of back/forward is 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