Space
Open
From Fieldwork
Scales
Archive
Tests our understanding of linear data structures and how to manage "state" pointers.
While we can solve this using two stacks (one for "back" and one for "forward"), the most canonical and efficient Python solution uses a dynamic array (List) and a single integer pointer. This approach is generally preferred because it offers O(1) access to any point in the history without moving elements between stacks.
class BrowserHistory:
def __init__(self, homepage: str):
# Initialize with the homepage
self.history = [homepage]
self.pos = 0 # Current index
self.top = 0 # The current 'end' of valid history
def visit(self, url: str) -> None:
self.pos += 1
# If we are visiting a new page from the middle of history,
# we overwrite the next slot.
if self.pos < len(self.history):
self.history[self.pos] = url
else:
self.history.append(url)
# After a visit, the 'top' is always our current position
# effectively deleting any forward history.
self.top = self.pos
def back(self, steps: int) -> str:
# Move back, but don't go past index 0
self.pos = max(0, self.pos - steps)
return self.history[self.pos]
def forward(self, steps: int) -> str:
# Move forward, but don't go past the 'top'
self.pos = min(self.top, self.pos + steps)
return self.history[self.pos]
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode