Back and Forward History
Problem
Simulate the history of a single browser tab that starts on a home page. A visit opens a new page after the current one and throws away every page you could previously have gone forward to. A back of k moves up to k pages towards the start, and a forward of k moves up to k pages towards the newest one, stopping early when there is nowhere left to go. Given the home page and a list of operations, return the page you are on after each back or forward, in order.
Examples
Input: home = "home"
ops = [("visit", "a"), ("visit", "b"), ("back", 1),
("visit", "c"), ("forward", 1), ("back", 5)]
Output: ['a', 'c', 'home']
Why: visiting c from a drops b, so forward has nowhere to goInput: home = "x", ops = [("back", 2), ("forward", 3)]
Output: ['x', 'x']
Why: edge case, a fresh tab cannot move either wayHints
0 / 3
Every page needs to know both the page before it and the page after it, and back and forward only ever walk one of those links.
A visit does not delete the forward pages one by one. Pointing the current page at a brand new next page makes them unreachable in a single move.
Keep a node per page with prev and next links and a pointer to the current node. Visit links a new node after the current one and moves there; back and forward step along prev or next up to k times, stopping when the link is empty.
Solution
Each page is a node with links to the page before and after it, and a pointer marks where the tab is. A visit hangs a new node after the current one, which silently cuts off the old forward pages, then moves onto it. Back and forward follow prev or next links one step at a time and stop at the first missing link, so overshooting is harmless. A visit is O(1), a move of k steps is O(k), and space is O(number of visits).
class Page:
def __init__(self, url, prev=None): self.url, self.prev, self.next = url, prev, None
def run_history(home, ops):
current, seen = Page(home), []
for op, arg in ops:
if op == "visit":
current.next = Page(arg, current) # the old forward pages become unreachable
current = current.next
continue
for _ in range(arg): # back or forward, at most arg steps
step = current.prev if op == "back" else current.next
if step is None:
break
current = step
seen.append(current.url)
return seen
print(run_history("home", [("visit", "a"), ("visit", "b"), ("back", 1), ("visit", "c"), ("forward", 1), ("back", 5)])) # -> ['a', 'c', 'home']
print(run_history("x", [("back", 2), ("forward", 3)])) # -> ['x', 'x']
print(run_history("x", [])) # -> []Stuck on the idea rather than the code? Doubly Linked Lists covers it.