Start learning free

LESSON 414 OF 573 · STACK

Design Browser History in Scala: O(1) Back and Forward with Indexes

Practice O(1) Read the full explanation

A browser tab starts on a homepage. From the page it is on, it can visit a new page, go back a number of pages in its history, or go forward again. Visiting a new page erases the pages you could have gone forward to, the way a real browser does.

Implement the class BrowserHistory:

  • BrowserHistory(homepage) starts the tab on the page homepage.
  • visit(url) goes from the current page to url. Every page ahead of the current page (the pages forward could reach) is erased from the history.
  • back(steps) goes back steps pages. If fewer than steps pages are behind the current one, it goes back as far as it can, to the homepage. It returns the url of the page it ends on.
  • forward(steps) goes forward steps pages, or as far as it can if fewer pages are ahead. It returns the url of the page it ends on.

The input is the homepage and a list of operations, applied in order to one new BrowserHistory. The output lists what the back and forward calls return, in order. The starter code spells these names the way your language does.

 

Example 1:

Input:
    BrowserHistory("start.com")
    visit("news.com")
    visit("shop.com")
    visit("video.com")
    back(1)
    back(1)
    forward(1)
    visit("jobs.com")
    forward(2)
    back(2)
    back(7)
Output: shop.com news.com shop.com jobs.com news.com start.com
Explanation:
The history is start.com, news.com, shop.com, video.com, and the tab is on video.com.
back(1) goes to shop.com, the next back(1) to news.com, and forward(1) to shop.com again.
visit("jobs.com") erases video.com, the page that was ahead:
the history is now start.com, news.com, shop.com, jobs.com.
forward(2) can't move, because no page is ahead: it stays on jobs.com.
back(2) goes to news.com. back(7) can only go back one more page, to start.com.

Example 2:

Input:
    BrowserHistory("home.com")
    back(1)
    visit("a.com")
    visit("b.com")
    back(5)
    forward(1)
    forward(9)
Output: home.com home.com a.com b.com
Explanation: Nothing is behind the homepage, so back(1) stays on home.com. From b.com only two pages are behind,
so back(5) goes back two pages, to home.com. forward(9) goes forward as far as it can, to b.com.

Example 3:

Input:
    BrowserHistory("home.com")
    visit("a.com")
    visit("b.com")
    visit("c.com")
    back(2)
    visit("d.com")
    forward(1)
    back(1)
    forward(2)
Output: a.com d.com a.com d.com
Explanation: After back(2) the tab is on a.com, with b.com and c.com ahead. visit("d.com") erases both:
the history is now home.com, a.com, d.com. So forward(1) stays on d.com, and from a.com forward(2) can only reach d.com.

 

Constraints:

  • 1 <= homepage.length, url.length <= 20
  • homepage and url consist of lowercase English letters and '.'.
  • 1 <= steps <= 105
  • At most 105 calls in total are made to visit, back and forward.

Note:

Each call should run in O(1) time, whatever its steps. Two stacks, one for the pages behind and one for the pages ahead, also work, but they move one page at a time, so back and forward take O(steps) time.

STEP 1 OF 11
    Ctrl + Enter to check

    SCALA · STACK

    Design Browser History in Scala, explained

    Problem overview

    A browser tab starts on a homepage. From the page it is on, it can visit a new page, go back some number of pages, or go forward again. Visiting a new page erases the pages that forward could have reached, as a real browser does. The class BrowserHistory(homepage: String) has three methods:

    • visit(url: String): Unit moves from the current page to url and erases everything ahead of the current page.
    • back(steps: Int): String goes back steps pages, or as far as it can (the homepage) if fewer are behind. It returns the url of the page it ends on.
    • forward(steps: Int): String goes forward steps pages, or as far as it can if fewer are ahead. It returns the url of the page it ends on.

    Example: from home.com the tab visits a.com and b.com. Then back(5) returns home.com, because only two pages are behind, and forward(9) returns b.com, the farthest page ahead. back(1) on a fresh tab returns home.com too: nothing is behind the homepage.

    Approach

    The simple way and its cost

    Two stacks work: one for the pages behind the current page and one for the pages ahead. back(steps) pops a page from the first and pushes it on the second, steps times. It is correct, but it moves one page at a time, so back and forward cost O(steps). The lesson asks for O(1) whatever steps is.

    One list and two indexes

    Keep every page in one list, history, in the order they were visited, and two numbers:

    • current, the index of the page the tab is on;
    • last, the index of the last page forward can reach.

    Now back and forward only change current, by any number of steps at once:

    • back(steps) sets current to the larger of 0 and current - steps. Index 0 is the homepage, so it never goes lower.
    • forward(steps) sets current to the smaller of last and current + steps. The cap is last, not the end of the list.

    The cap matters because of the erasing. A visit does not remove the pages ahead from the list, which would take time. It writes the new url at the next index and sets last = current. Old pages may stay in the list after last, but forward never goes past last, and later visits write over them.

    Here is a run: the tab visits a.com, b.com and c.com from home.com, goes back 2, and then visits d.com:

    afterhistorycurrentlast
    back(2)home.com, a.com, b.com, c.com13
    visit("d.com")home.com, a.com, d.com, c.com22

    The text c.com is still in the list, but last is 2, so forward can never reach it. From there, forward(1) returns d.com, back(1) returns a.com, and forward(2) returns d.com, since only one page is ahead.

    Step by step

    1. Declare history, a val holding scala.collection.mutable.ArrayBuffer[String](homepage): a growable array that starts with the homepage at index 0. The class parameter homepage can be used directly in the class body.
    2. Declare current, a var set to 0. The tab starts on the homepage.
    3. Declare last, a var set to 0. For now the homepage is also the last page forward can reach.
    4. In visit, move current ahead with current += 1. The new page goes right after the current one.
    5. Reuse an erased slot: if current < history.length, an erased page is sitting at that index, so overwrite it with history(current) = url.
    6. Otherwise grow the list: in an else, add url at the end with history += url.
    7. Set last = current. This one line erases the forward history.
    8. In back, set current = math.max(0, current - steps).
    9. Return history(current), the page where the tab ended up.
    10. In forward, set current = math.min(last, current + steps).
    11. Return history(current).

    The solution in Scala

    class BrowserHistory(homepage: String) {
    val history = scala.collection.mutable.ArrayBuffer[String](homepage)
    var current = 0
    var last = 0

    def visit(url: String): Unit = {
        current += 1
        if (current < history.length) {
            history(current) = url
        } else {
            history += url
        }
        last = current
    }

    def back(steps: Int): String = {
        current = math.max(0, current - steps)
        return history(current)
    }

    def forward(steps: Int): String = {
        current = math.min(last, current + steps)
        return history(current)
    }
}

    Using the class:

    val b = new BrowserHistory("home.com")
b.visit("a.com")
b.visit("b.com")
b.visit("c.com")
println(b.back(1))
println(b.back(1))
println(b.forward(1))
b.visit("d.com")
println(b.forward(2))
println(b.back(2))
println(b.back(7))

    b.com
a.com
b.com
d.com
a.com
home.com

    The history is home.com, a.com, b.com, c.com, and the tab is on c.com. Two backs reach a.com, and forward(1) returns to b.com. Visiting d.com overwrites c.com, so nothing is ahead and forward(2) stays on d.com. Then back(2) reaches a.com, and back(7) stops at the homepage.

    Scala details:

    • Class parameters. homepage has no val, and it is still usable in the initializer of history, because the body of a Scala class runs as its constructor.
    • ArrayBuffer[String](homepage) builds a buffer with one element. history(current) = url writes at an index, and history += url appends.
    • Fields you reassign are var. current and last change, so they are var. The buffer reference never changes, so history is a val, even though its contents do.
    • math.max and math.min come from the scala.math package, which is reachable as math without an import. Here they clamp current into the range from 0 to last.
    • current += 1 works on a var of type Int. On a val, it would not compile.

    Complexity

    Time. O(1) for every call, whatever steps is. visit does one comparison and either an overwrite or an append (amortized O(1) for the append). back and forward do one subtraction or addition, a clamp and an index read.

    Space. O(n), where n is the largest number of pages the history ever reached. Erased pages are overwritten rather than removed, so the buffer never shrinks, but it never grows beyond that largest reach.

    Edge cases and common mistakes

    • Going back past the homepage. Without math.max(0, ...), current could become negative and history(current) would throw an IndexOutOfBoundsException. With it, back(100000) from the second page returns the homepage.
    • Capping forward by the length of the list. Pages after last have been erased by a visit but may still be in the buffer. After home.com, a.com, b.com, c.com, back(2) and visit("d.com"), the buffer still ends with c.com. Capping at the last index of the buffer would let a forward step show a page that no longer exists; capping at last returns d.com.
    • Forgetting last = current in visit. Without it, last stays where it was, and forward reaches the old pages ahead.
    • Always appending in visit. After going back, the new page belongs at current + 1, not at the end of the buffer. Appending would put it after the pages that should be erased, and current would no longer point at it.
    • Visiting with nothing ahead. When current equals the last index of the buffer, current + 1 equals the length, so the else branch appends.
    • Moving forward with nothing ahead. forward then returns the current page, since math.min(last, current + steps) is current itself.

    Testing

    • Starting on home.com: back(1) returns home.com.
    • Then visit("a.com"), visit("b.com"): back(5) returns home.com, forward(1) returns a.com, and forward(9) returns b.com.
    • Starting on home.com, visit a.com, b.com, c.com: back(2) returns a.com. After visit("d.com"), forward(1) returns d.com, back(1) returns a.com, and forward(2) returns d.com.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free