Problem overview
You write a class BrowserHistory. A tab starts on a homepage given to the constructor. visit(url) goes to a new page and erases the pages that forward could have reached. back(steps) goes back that many pages, or as far as it can to the homepage, and returns the url it ends on. forward(steps) goes forward the same way and also returns the url it ends on.
Start on "home.com" and visit a.com, b.com and c.com. Then back(2) moves to a.com, with b.com and c.com ahead. Visiting d.com erases both of them: the history is now home.com, a.com, d.com. After that, forward(1) stays on d.com, because nothing is ahead.
Approach
The natural idea is two stacks: pages behind the current page and pages ahead. back(1) moves one page from one stack to the other, and visit clears the forward stack. It works, but back(steps) repeats that move steps times, so a call costs O(steps).
The faster design keeps all pages in a single list, in visiting order, with two indexes:
current, the index of the page the tab is on;last, the index of the last pageforwardmay reach.
Then back and forward only change current, by any number of steps with one subtraction or addition, cut off at 0 and at last.
The clever part is how visit erases the forward pages: it does not delete anything. It writes the new url at current + 1, over whatever sat there, and sets last to that index. Pages beyond last may still be in the list, but forward never goes past last, and later visits write over them. Removing the old pages for real would cost time proportional to how many there are.
Step by step
- The list.
historyis amutableListOf(homepage). The constructor'shomepagecan be used in the property initializer, and the homepage sits at index 0. - The current page.
var current = 0: the tab starts on the homepage. - The last reachable page.
var last = 0: for now, also the homepage. - Move on in
visit.current++: the new page goes right after the current one. - Overwrite if possible. If
current < history.size, an old page sits at that index and this visit erases it, so sethistory[current] = url. - Otherwise append. If the list ends at the old current page,
history.add(url). - Cut the future. After the
if/else, setlast = current. This one line makes every page after it unreachable. back. Setcurrent = maxOf(0, current - steps), so the index never goes below the homepage, then returnhistory[current].forward. Setcurrent = minOf(last, current + steps). The limit islast, not the end of the list, because the pages afterlastwere erased. Returnhistory[current].
The solution in Kotlin
class BrowserHistory(homepage: String) {
val history = mutableListOf(homepage)
var current = 0
var last = 0
fun visit(url: String) {
current++
if (current < history.size) {
history[current] = url
} else {
history.add(url)
}
last = current
}
fun back(steps: Int): String {
current = maxOf(0, current - steps)
return history[current]
}
fun forward(steps: Int): String {
current = minOf(last, current + steps)
return history[current]
}
}
Kotlin details worth knowing:
- Constructor parameters.
homepagehas noval, so it is not a property. It still can be used when the properties are initialized, which is all this class needs. - Type inference.
mutableListOf(homepage)is aMutableList<String>, becausehomepageis aString. A plainlistOfwould give a read-only list that has noaddand no assignment by index. current++on a property. Avarproperty can be incremented like a local variable.maxOfandminOf. They take two numbers and return the larger or the smaller. Together they clamp a value to a range with noif.- Indexing assignment.
history[current] = urlreplaces an element in aMutableList; it never grows the list, which is why the code checkscurrent < history.sizefirst.
Seeing it run
This code follows the example above and prints the list and both indexes after each change:
fun main() {
val tab = BrowserHistory("home.com")
tab.visit("a.com")
tab.visit("b.com")
tab.visit("c.com")
println("${tab.history} current = ${tab.current}, last = ${tab.last}")
println(tab.back(2))
println("${tab.history} current = ${tab.current}, last = ${tab.last}")
tab.visit("d.com")
println("${tab.history} current = ${tab.current}, last = ${tab.last}")
println(tab.forward(1))
println(tab.back(1))
println(tab.forward(2))
println(tab.back(100))
println(tab.forward(100))
}
It prints:
[home.com, a.com, b.com, c.com] current = 3, last = 3
a.com
[home.com, a.com, b.com, c.com] current = 1, last = 3
[home.com, a.com, d.com, c.com] current = 2, last = 2
d.com
a.com
d.com
home.com
d.com
After back(2) the list is unchanged but current is 1, while last stays 3. Visiting d.com overwrites b.com at index 2 and sets last to 2. c.com is still in the list at index 3, but forward can't reach it, so forward(1) returns d.com again. Then back(1) returns a.com and forward(2) goes only as far as d.com. The last two calls, with 100 steps, stop at home.com and d.com.
Complexity
- Time:
backandforwardare O(1), whateverstepsis.visitis O(1): an assignment, or an append, which is O(1) amortized. - Space: O(n) for the longest history, because pages are overwritten instead of kept in a separate stack.
Edge cases and common mistakes
- Going past the ends. With nothing behind the homepage,
back(1)stays put. A hugestepsvalue lands on the homepage, not at a negative index. - Using the list size as the forward limit. After a visit, stale pages remain in the list. Limiting
forwardbyhistory.size - 1would bring back erased pages. - Forgetting
last = currentinvisit. The forward history would then survive a visit. - Always using
addinvisit. After aback, the new page would land at the end of the list, behind the stale pages, instead of right after the current page. - Calling
backandforwardone page at a time. A loop of single steps gives the right answer, but costs O(steps) per call.
