⚡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