⚡Flashcard Drill➔
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

  1. Keep the history in a list plus an index pointing at the current page.
  2. visit truncates everything after the current index, then appends.
  3. back and forward move the index and clamp it to [0, len - 1].
  4. The truncation on visit is 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 back at 0: the index could go negative and Python would silently wrap around.
  • Forgetting to clamp forward at the end: the index could exceed the list length.
  • Storing only the current URL: the history is needed for back and forward.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 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]