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.
🧩 Related Linked List Problems
中文速览与面试要点
设计浏览器历史记录
你有一个只支持单个标签页的浏览器,最开始你浏览的网页是 homepage,你可以访问其他的网站 url,也可以在浏览历史中后退 steps 步或前进 steps 步。请你实现 BrowserHistory 类: BrowserHistory(homepage) 初始化; visit(url) 从当前页访问 url; back(steps) 在浏览历史中后退 steps 步(如果步数超过可后退的步数,则只后退到最初访问的页面),返回后退后的页面 url; forward(steps) 在浏览历史中前进 steps 步(同样有边界限制),返回前进后的页面 url。约束:1 ≤ homepage.length ≤ 20;1 ≤ url.length ≤ 20;1 ≤ steps ≤ 100;最多调用 5000 次方法。
核心要点
- 动态数组 + 当前下标(标准解) :用列表 history 保存浏览历史, cur 指向当前页面下标。
- visit 的关键操作 :新访问会把「当前页之后的所有前进历史」清空,即 history = history[:cur+1] ,然后追加新 url。
- back / forward :用 max / min 做边界裁剪,更新 cur 并返回对应页面。
- 为什么不能只保存一个栈 :需要支持「前进」操作,因此必须保留当前页之后的历史,数组 + 下标是唯一简洁的方案。
常见陷阱
- visit 时不清空前进历史 :会导致「后退后访问新页面,再前进」能回到已废弃的页面,逻辑错误。必须截断 history[:cur+1] 。
- back 时忘记 max(0, ...) : cur 会变成负数,Python 负下标会静默索引到数组末尾,产生错误结果而不报错。这是最隐蔽的坑。
- forward 时忘记 min(len-1, ...) :会越界。
- 用两个栈实现 :可行(一个存后退、一个存前进),但 visit 时需要清空前进栈,逻辑与数组方案等价。
参考实现
class BrowserHistory:
def __init__(self, homepage: str):
self.history = [homepage]
self.cur = 0 # 当前页在 history 中的下标
def visit(self, url: str) -> None:
# 新访问会清空「前进」历史
self.history = self.history[:self.cur + 1]
self.history.append(url)
self.cur += 1
def back(self, steps: int) -> str:
self.cur = max(0, self.cur - steps)
return self.history[self.cur]
def forward(self, steps: int) -> str:
self.cur = min(len(self.history) - 1, self.cur + steps)
return self.history[self.cur]