FoundationalProblem 1 of 20

FoundationalStarter

Browser History

Memento PatternIterator Pattern

Back, forward, and visit. Looks like two stacks but it's really one doubly-linked list with a cursor — and the cursor discards the forward branch whenever something new loads.

Key Abstractions

HistoryEntry

One visited URL plus a timestamp and optional title

History

Doubly-linked list with a current-node pointer. Back/forward move the pointer.

Tab

Owns its own History. Each browser tab is independent.

Browser

Manages tabs and the active tab

Class Diagram

The Key Insight

The two-stacks-instead-of-one trap burns most candidates. A back-stack and forward-stack model works for simple back/forward — until someone goes back three, then clicks a link, and the forward-stack now holds entries from an obsolete timeline. The mental model has to be "cursor into a timeline" not "two piles."

A doubly-linked list with a current-node pointer nails it. Back moves the pointer left. Forward moves it right. Visit appends to the right of the pointer and drops everything that was there. O(1) every operation. The forward-branch-dies-on-new-visit rule is enforced in exactly one place: the visit() method.

Per-tab isolation is the second detail interviewers probe. Every tab has its own History. Shared history across tabs would mean clicking "back" in tab A affects tab B — nobody wants that. Same class, separate instance.

Requirements

Functional

Visit a URL, appending to history
Back and forward by a count of steps
Visiting after going back discards the forward branch
Multiple tabs, each with independent history
Report current URL at any time

Non-Functional

O(1) per visit, back, forward
Bounded memory — drop oldest entries when capacity exceeded
Tab operations must not leak across tabs

Design Decisions

Why a linked list over an array with an index?

Arrays work fine until capacity trimming kicks in. Trimming the head of an array is O(n). A doubly-linked list pops the head in O(1). On modern hardware the cache wins of the array matter less at these sizes than the cleaner semantics of the list.

Why truncate forward on every visit?

The alternative — keeping old forward entries as a "branch tree" — means the back-button doesn't correspond to what the user actually did. Browsers universally truncate on visit. The user expectation is linear history.

Why separate History from Tab?

History is the pure data structure. Tab wraps it with a tab ID and any tab-level concerns (title, favicon, loading state). The history could also back a file-explorer's breadcrumb or a wizard's step tracker. Pulling it apart keeps it reusable.

Why head-trim on capacity overflow instead of tail-trim?

Capacity protects against a multi-day session that visited 50,000 pages. The oldest entries are the least useful — nobody goes back 50,000 clicks. Dropping from the head keeps the most-recent N pages reachable, which is what people actually want.

Interview Follow-ups

"How would you implement 'history search' (Ctrl+H)?" A separate VisitLog that tails the visit() call, storing entries even after they're trimmed. Queried separately from navigation history.
"How do you persist across browser restarts?" Serialize the linked list to a list of URL strings plus the cursor index. On load, rebuild. Forward branch is typically discarded on restart — matches Chrome's behavior.
"What about private/incognito mode?" Swap History with a no-op implementation that never records. Same interface, different Strategy.
"How do you handle redirects?" The server-side 302 resolves before the entry is recorded. The final URL is what lands in history. Client-side redirects (meta refresh, JS) are more debatable — Chrome records the final URL as one entry.

Code Implementation

  1  from __future__ import annotations
  2  from dataclasses import dataclass, field
  3  from datetime import datetime
  4  import uuid
  5  
  6  
  7  class HistoryEntry:
  8      __slots__ = ("url", "title", "visited_at", "prev", "next")
  9  
 10      def __init__(self, url: str, title: str = ""):
 11          self.url = url
 12          self.title = title
 13          self.visited_at = datetime.now()
 14          self.prev: "HistoryEntry | None" = None
 15          self.next: "HistoryEntry | None" = None
 16  
 17  
 18  class History:
 19      """Doubly-linked list of entries with a cursor. Back/forward move the cursor."""
 20  
 21      def __init__(self, capacity: int = 200):
 22          if capacity <= 0:
 23              raise ValueError("capacity must be positive")
 24          self._capacity = capacity
 25          self._current: HistoryEntry | None = None
 26          self._head: HistoryEntry | None = None  # oldest entry — for capacity trim
 27          self._size = 0
 28  
 29      def visit(self, url: str, title: str = "") -> None:
 30          entry = HistoryEntry(url, title)
 31          if self._current is None:
 32              self._current = self._head = entry
 33              self._size = 1
 34              return
 35  
 36          # Visiting always truncates forward history.
 37          self._truncate_forward()
 38  
 39          self._current.next = entry
 40          entry.prev = self._current
 41          self._current = entry
 42          self._size += 1
 43  
 44          # Trim from the head if we blew past capacity.
 45          while self._size > self._capacity and self._head is not self._current:
 46              victim = self._head
 47              self._head = victim.next
 48              if self._head is not None:
 49                  self._head.prev = None
 50              victim.next = None
 51              self._size -= 1
 52  
 53      def _truncate_forward(self) -> None:
 54          node = self._current.next
 55          while node is not None:
 56              nxt = node.next
 57              node.prev = node.next = None
 58              node = nxt
 59              self._size -= 1
 60          self._current.next = None
 61  
 62      def back(self, steps: int = 1) -> str | None:
 63          if steps < 0:
 64              raise ValueError("steps must be non-negative")
 65          while steps > 0 and self._current and self._current.prev:
 66              self._current = self._current.prev
 67              steps -= 1
 68          return self._current.url if self._current else None
 69  
 70      def forward(self, steps: int = 1) -> str | None:
 71          if steps < 0:
 72              raise ValueError("steps must be non-negative")
 73          while steps > 0 and self._current and self._current.next:
 74              self._current = self._current.next
 75              steps -= 1
 76          return self._current.url if self._current else None
 77  
 78      def current_url(self) -> str | None:
 79          return self._current.url if self._current else None
 80  
 81      def can_go_back(self) -> bool:
 82          return self._current is not None and self._current.prev is not None
 83  
 84      def can_go_forward(self) -> bool:
 85          return self._current is not None and self._current.next is not None
 86  
 87      def clear(self) -> None:
 88          """Wipe history — privacy feature ("clear browsing data")."""
 89          # Break internal links so GC reclaims the nodes promptly.
 90          node = self._head
 91          while node is not None:
 92              nxt = node.next
 93              node.prev = node.next = None
 94              node = nxt
 95          self._head = self._current = None
 96          self._size = 0
 97  
 98  
 99  class Tab:
100      """One browser tab with its own isolated history."""
101  
102      def __init__(self, initial_url: str | None = None, capacity: int = 200):
103          self.id = str(uuid.uuid4())[:8]
104          self._history = History(capacity=capacity)
105          if initial_url:
106              self._history.visit(initial_url)
107  
108      def visit(self, url: str, title: str = "") -> None:
109          self._history.visit(url, title)
110  
111      def back(self, steps: int = 1) -> str | None:
112          return self._history.back(steps)
113  
114      def forward(self, steps: int = 1) -> str | None:
115          return self._history.forward(steps)
116  
117      def current_url(self) -> str | None:
118          return self._history.current_url()
119  
120      def clear_history(self) -> None:
121          self._history.clear()
122  
123      @property
124      def history(self) -> History:
125          return self._history
126  
127  
128  class Browser:
129      """Owns multiple tabs and the active tab pointer."""
130  
131      def __init__(self):
132          self._tabs: dict[str, Tab] = {}
133          self._active: str | None = None
134  
135      def open_tab(self, url: str) -> str:
136          tab = Tab(url)
137          self._tabs[tab.id] = tab
138          self._active = tab.id
139          return tab.id
140  
141      def close_tab(self, tab_id: str) -> None:
142          if tab_id not in self._tabs:
143              raise ValueError("Unknown tab")
144          del self._tabs[tab_id]
145          if self._active == tab_id:
146              self._active = next(iter(self._tabs), None)
147  
148      def clear_all_history(self) -> None:
149          """Browser-level Clear All Browsing Data."""
150          for tab in self._tabs.values():
151              tab.clear_history()
152  
153      def switch_to(self, tab_id: str) -> None:
154          if tab_id not in self._tabs:
155              raise ValueError("Unknown tab")
156          self._active = tab_id
157  
158      @property
159      def active(self) -> Tab | None:
160          return self._tabs.get(self._active) if self._active else None
161  
162  
163  if __name__ == "__main__":
164      browser = Browser()
165      tab_id = browser.open_tab("https://google.com")
166      tab = browser.active
167  
168      tab.visit("https://google.com/search?q=lld")
169      tab.visit("https://crackingwalnuts.com")
170      print(f"Current: {tab.current_url()}")            # crackingwalnuts.com
171  
172      tab.back()
173      print(f"After back: {tab.current_url()}")          # google.com/search
174      tab.back()
175      print(f"After back x2: {tab.current_url()}")       # google.com
176  
177      tab.forward(2)
178      print(f"After forward x2: {tab.current_url()}")    # crackingwalnuts.com
179  
180      # Branching: go back, then visit something new. Forward path is erased.
181      tab.back()
182      tab.visit("https://news.ycombinator.com")
183      print(f"After branch: {tab.current_url()}")        # hn
184      assert not tab.history.can_go_forward()
185      print("Forward history correctly cleared after branching.")
186  
187      # Second tab is independent.
188      second = browser.open_tab("https://github.com")
189      assert browser.active.current_url() == "https://github.com"
190      browser.switch_to(tab_id)
191      assert browser.active.current_url() == "https://news.ycombinator.com"
192      print("Tab isolation verified.")
193  
194      # Clear-all-browsing-data leaves every tab with an empty history.
195      browser.clear_all_history()
196      for t in (browser._tabs[tab_id], browser._tabs[second]):
197          assert t.current_url() is None
198          assert not t.history.can_go_back()
199      print("Clear-all wiped every tab's history.")

Common Mistakes

✗Implementing back with a stack of visited pages. Forward then breaks when someone visits mid-way.
✗Mutating the current entry on forward. The entry is immutable; only the cursor moves.
✗Sharing history across tabs. Each tab needs its own independent timeline.
✗Forgetting to clear forward on visit. That leaves dead entries the user can never reach.

Key Points

✓One linked list with a cursor, not two stacks. Back is cursor.prev, forward is cursor.next.
✓Visiting a new URL discards everything after the cursor. Just like undo/redo — new action branches the future.
✓Back/forward are O(1) — just move the pointer. No copying.
✓Cap history length from the head (oldest entries) when memory matters.

Related Designs