Problem overview
A browser tab starts on a homepage. From any page it can visit a new url, go back some number of pages, or go forward again. Visiting a new page erases the pages ahead of the current one, as in a real browser. The class BrowserHistory has these methods:
BrowserHistory(homepage)starts the tab onhomepage.visit(url)moves tourland erases every page thatforwardcould have reached.back(steps)goes backstepspages, or as far as the homepage if fewer are behind. It returns the url it ends on.forward(steps)goes forwardstepspages, or as far as it can. It returns the url it ends on.
Example: a tab starts on home.com, then visits a.com, b.com and c.com. The call back(2) lands on a.com. Visiting d.com now erases b.com and c.com, so the history is home.com, a.com, d.com and forward(1) stays on d.com.
Approach: one list and two indexes
The natural first design uses two stacks: pages behind the current one and pages ahead. back(steps) pops from one stack and pushes onto the other, one page at a time, so it costs O(steps), and steps can be as large as 100,000. The task asks for O(1) per call, whatever steps is.
The faster design keeps all the pages in one list in visiting order, and moves around it with numbers. Going back or forward is then arithmetic on an index, however far it goes. Two indexes are enough:
self.current: the position of the page the tab is on.self.last: the position of the last pageforwardmay reach.
The list can be longer than self.last + 1. Pages after self.last are leftovers that a visit erased. Instead of deleting them, which takes time, the code simply never goes past self.last, and later visits write over the leftovers. A single assignment, self.last = self.current, erases the whole forward history.
Step by step
- In
__init__, setself.historyto a list holding onlyhomepage, at index 0. - Set
self.currentto 0: the tab starts on the homepage. - Set
self.lastto 0. Nothing is ahead yet, so the homepage is also the last reachable page. - In
visit, add 1 toself.current. The new page goes right after the current one. - If
self.current < len(self.history), an old, erased page sits at that position. Overwrite it withurl, which takesO(1). - Otherwise the list ends at the old current page, so append
url. - Set
self.lasttoself.current. The new page is now the last one thatforwardcan reach, and everything after it counts as erased. - In
back, setself.currenttomax(0, self.current - steps). Index 0 is the homepage, the furthest back you can go. - Return
self.history[self.current]. - In
forward, setself.currenttomin(self.last, self.current + steps). The cap isself.last, not the end of the list, because the list may hold erased leftovers. - Return
self.history[self.current]again.
The solution in Python
class BrowserHistory:
def __init__(self, homepage: str):
self.history = [homepage]
self.current = 0
self.last = 0
def visit(self, url: str) -> None:
self.current += 1
if self.current < len(self.history):
self.history[self.current] = url
else:
self.history.append(url)
self.last = self.current
def back(self, steps: int) -> str:
self.current = max(0, self.current - steps)
return self.history[self.current]
def forward(self, steps: int) -> str:
self.current = min(self.last, self.current + steps)
return self.history[self.current]
The class in use, printing the list and both indexes so the leftovers are visible:
b = BrowserHistory("home.com")
print(b.back(1))
b.visit("a.com")
b.visit("b.com")
b.visit("c.com")
print(b.history, b.current, b.last)
print(b.back(2), b.current)
b.visit("d.com")
print(b.history, b.current, b.last)
print(b.forward(1), b.back(1), b.forward(2))
b.visit("e.com")
print(b.history, b.current, b.last)
print(b.back(9), b.forward(9))
home.com
['home.com', 'a.com', 'b.com', 'c.com'] 3 3
a.com 1
['home.com', 'a.com', 'd.com', 'c.com'] 2 2
d.com a.com d.com
['home.com', 'a.com', 'd.com', 'e.com'] 3 3
home.com e.com
Reading it line by line:
back(1)on a new tab stays onhome.com, because nothing is behind it.- After
back(2)the tab is ona.com(index 1), withb.comandc.comstill in the list andlaststill 3. visit("d.com")overwritesb.comat index 2 and setslastto 2. The list still containsc.comat index 3, butforwardcan't reach it any more.forward(1)fromd.comstays put,back(1)returns toa.com, andforward(2)stops atd.combecauselastis 2.- The next visit overwrites
c.com, so the leftover is gone.back(9)goes as far ashome.com, andforward(9)as far ase.com.
Python details worth knowing:
maxandminclamp an index without anyif:max(0, ...)stops it below 0, andmin(self.last, ...)stops it aboveself.last.- A list can be assigned by position (
self.history[i] = url) only for positions that exist, which is why the code checkslen(self.history)first and appends otherwise. - Python integers don't overflow, so a large
stepssuch as 100,000 added to an index is safe.
Complexity
Time: every method is a few index operations, so visit, back and forward are O(1) (an append is O(1) amortized). Jumping 100,000 pages costs the same as jumping one.
Space: O(n), where n is the longest the history ever got. The list never shrinks, but visits reuse the leftover slots, so it doesn't grow without need.
Edge cases and common mistakes
- Going back past the homepage. Without
max(0, ...)the index would turn negative and, in Python, a negative index silently reads from the end of the list, returning the wrong page instead of an error. - Going forward past the end. The cap must be
self.last. Capping atlen(self.history) - 1would letforwardreach erased pages such asc.comabove. - Forgetting to update
self.lastinvisit. Then the forward history survives a visit. - Using
appendin every visit. After going back, the new page would land at the end of the list, after the pages that should be gone. - A visit with nothing ahead. The index equals the list length, so the page is appended: the list grows only when the history reaches further than it ever did.
Testing
Another small case, straight from the rules: from a new tab, go back, visit twice, then go back too far and forward too far.
b = BrowserHistory("home.com")
print(b.back(1))
b.visit("a.com")
b.visit("b.com")
print(b.back(5), b.forward(1), b.forward(9))
home.com
home.com a.com b.com
