The machine models browser history: a current page, a back stack, and a forward stack. visit(url) pushes the current page onto the back stack, sets the new current page, and — the crucial rule — clears the entire forward stack. back(steps) moves the current page up to steps toward the oldest, pushing each popped page onto the forward stack. forward(steps) mirrors it in reverse.
The stack discipline makes the clearing rule automatic: when visit fires, the machine throws away the forward stack wholesale, because any new navigation invalidates all future states. Two explicit stacks (or a list with a cursor) both work; the two-stack version makes the asymmetry visible — visit is O(1) plus a forward reset, back/forward are O(k) worst case but amortized O(1) per step because every page moves between stacks at most once per visit.
The list-plus-cursor variant is what a real browser implements: one list of all visited pages, an integer index, and a truncation on visit. It gives O(1) back/forward but O(n) truncation cost when the list resizes — the two-stack version avoids the resize by garbage-collecting the forward stack instead.
Edge cases are where this problem scores: back(0) and forward(0) return the current page unchanged; steps larger than the stack depth clamp to the oldest or newest page rather than erroring; forward after a fresh visit must return −1 (or the current page, per the interface — the stacks have nothing to give); back then visit then back again must not resurrect the truncated forward history. The clamp logic is the usual bug site — the machine must compute min(steps, len(stack)), not loop and pop blindly.
class BrowserHistory:
def __init__(self, homepage):
self.back_stack = []
self.forward_stack = []
self.current = homepage
def visit(self, url):
self.back_stack.append(self.current)
self.forward_stack.clear()
self.current = url
def back(self, steps):
for _ in range(min(steps, len(self.back_stack))):
self.forward_stack.append(self.current)
self.current = self.back_stack.pop()
return self.current
def forward(self, steps):
for _ in range(min(steps, len(self.forward_stack))):
self.back_stack.append(self.current)
self.current = self.forward_stack.pop()
return self.current