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 you could have gone forward to, as a real browser does.
The lesson asks for a BrowserHistory struct. Constructor(homepage) starts the tab on the homepage. Visit(url) goes to a new page and erases every page ahead of the current one. Back(steps) goes back steps pages, or as far as it can if fewer are behind, and returns the url it ends on. Forward(steps) does the same in the other direction.
Take a tab that starts on home.com and visits a.com, b.com and c.com. Then Back(2) returns a.com, with b.com and c.com still ahead. Visit("d.com") erases both, so the history is home.com, a.com, d.com. A Forward(1) now stays on d.com, because no page is ahead.
Approach: one list and two indexes
The natural first design uses two stacks: one for the pages behind and one for the pages ahead. Back(steps) moves a page from one stack to the other, one step at a time, so it takes O(steps). The statement wants every call in O(1), whatever the number of steps.
That is possible by keeping all the pages in one list, in the order they were visited, with two indexes:
currentis the index of the page the tab is on.lastis the index of the last page thatForwardcan reach.
Back and Forward then only change current: one subtraction or addition, capped at an end of the valid range. Back can't go below index 0, the homepage, and Forward can't go past last.
Visit needs to erase the pages ahead without paying for it. It doesn't remove them from the list. It writes the new url at the index just after current if that index already exists, or appends it if the list ends there, and then sets last to current. Pages after last may still sit in the list, but Forward never reaches them, and later visits write over them.
Step by step
- Declare
historyas a[]string, the pages in visit order. - Declare
currentas anint, the index of the page the tab is on. - Declare
lastas anint, the index of the last pageForwardcan reach. - In
Constructor, return a struct whosehistoryholds just the homepage.currentandlastare not named, so they start at 0: the tab is on the homepage and it is also the last page. - In
Visit, increasethis.currentby one with++. The new page goes right after the current one. - If that index is still inside the slice (
this.current < len(this.history)), a page that this visit erases sits there. Overwrite it withurl, which takesO(1). - Otherwise append
urland store the result back. The list only grows when the history reaches further than it ever did. - Set
this.lasttothis.current. This one line erases the forward history. - In
Back, setthis.currentto the larger of 0 andthis.current - steps, with the built-inmax. - Return
this.history[this.current]. - In
Forward, setthis.currentto the smaller ofthis.lastandthis.current + steps, with the built-inmin. The cap islast, not the end of the list. - Return
this.history[this.current].
The solution in Go
type BrowserHistory struct {
history []string
current int
last int
}
func Constructor(homepage string) BrowserHistory {
return BrowserHistory{history: []string{homepage}}
}
func (this *BrowserHistory) Visit(url string) {
this.current++
if this.current < len(this.history) {
this.history[this.current] = url
} else {
this.history = append(this.history, url)
}
this.last = this.current
}
func (this *BrowserHistory) Back(steps int) string {
this.current = max(0, this.current-steps)
return this.history[this.current]
}
func (this *BrowserHistory) Forward(steps int) string {
this.current = min(this.last, this.current+steps)
return this.history[this.current]
}
The Go details worth a closer look:
- Built-in
minandmax. Since Go 1.21 they are part of the language and work on ints, so no import is needed. - Slices grow with
append.appendmay allocate a bigger array, so its result is stored back inthis.history. Assigning to an existing index, as inthis.history[this.current] = url, changes the element in place. - Zero values. The fields left out of the struct literal in
Constructorare 0. - Pointer receivers. All methods change the struct, so they use
*BrowserHistory.
Complexity
Time: O(1) for every call. Back and Forward are one arithmetic step and one read, whatever steps is. Visit is one write or one amortized O(1) append.
Space: O(n) for the pages in the list, which never holds more than the longest history the tab has had.
Edge cases and common mistakes
- Going back too far. From
b.comwith only two pages behind,Back(5)stops at the homepage. Nothing behind the homepage meansBack(1)on a new tab returns the homepage itself. - Going forward too far.
Forward(9)stops at the last reachable page. - Capping
Forwardat the end of the list. Afterhome.com,a.com,b.com,c.com,Back(2)andVisit("d.com"), the list is[home.com a.com d.com c.com]andlastis 2. The pagec.comis still in the list, butForwardmust stop atd.com. - Forgetting to set
lastinVisit. The erased pages would become reachable again. - Always appending in
Visit. The erased pages would stay in the middle of the list and the indexes would no longer match the pages. - Letting
currentgo negative. Withoutmax(0, …)a largestepswould index out of range and panic.
Testing
For a tab started on home.com: Back(1) returns home.com. After visiting a.com and b.com, Back(5) returns home.com, Forward(1) returns a.com and Forward(9) returns b.com.
For a tab started on home.com with a.com, b.com, c.com visited, Back(2) returns a.com. After Visit("d.com") the three fields are history = [home.com a.com d.com c.com], current = 2 and last = 2. Then Forward(1) returns d.com, Back(1) returns a.com and Forward(2) returns d.com.
