NeetCode #326LC-1472MediumLinked List
← Back to All Problems#326 · #1472 · Design Browser History(设计浏览器历史记录)
📌 Problem Statement & Constraints
Design a browser history supporting
visit(url) (clears the forward history), back(steps) and forward(steps), both returning the current URL and clamped to the available range. Constraints: 1 <= url.length, homepage.length <= 20; at most 5000 calls.💡 Core Algorithmic Approaches
- Keep the history in a list plus an index pointing at the current page.
visittruncates everything after the current index, then appends.backandforwardmove the index and clamp it to[0, len - 1].- The truncation on
visitis what discards the forward history, and it is the only subtle part.
💻 Benchmark Python3 Implementation
class BrowserHistory:
def __init__(self, homepage: str):
self.history = [homepage]
self.idx = 0
def visit(self, url: str) -> None:
self.history = self.history[:self.idx + 1] # discard forward history
self.history.append(url)
self.idx += 1
def back(self, steps: int) -> str:
self.idx = max(0, self.idx - steps) # clamp at the start
return self.history[self.idx]
def forward(self, steps: int) -> str:
self.idx = min(len(self.history) - 1, self.idx + steps) # clamp at the end
return self.history[self.idx]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) for back and forward; O(k) for visit where k is the discarded suffix length (O(1) amortised in the common case).
💾 Space Complexity
O(total visits).
⚠️ Interview Pitfalls & Follow-ups
- Not truncating on
visit: the forward history would remain, which contradicts browser semantics. - Forgetting to clamp
backat 0: the index could go negative and Python would silently wrap around. - Forgetting to clamp
forwardat the end: the index could exceed the list length. - Storing only the current URL: the history is needed for
backandforward.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.