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

from __future__ import annotations
from dataclasses import dataclass, field
from datetime import datetime
import uuid


class HistoryEntry:
    __slots__ = ("url", "title", "visited_at", "prev", "next")

    def __init__(self, url: str, title: str = ""):
        self.url = url
        self.title = title
        self.visited_at = datetime.now()
        self.prev: "HistoryEntry | None" = None
        self.next: "HistoryEntry | None" = None


class History:
    """Doubly-linked list of entries with a cursor. Back/forward move the cursor."""

    def __init__(self, capacity: int = 200):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self._capacity = capacity
        self._current: HistoryEntry | None = None
        self._head: HistoryEntry | None = None  # oldest entry — for capacity trim
        self._size = 0

    def visit(self, url: str, title: str = "") -> None:
        entry = HistoryEntry(url, title)
        if self._current is None:
            self._current = self._head = entry
            self._size = 1
            return

        # Visiting always truncates forward history.
        self._truncate_forward()

        self._current.next = entry
        entry.prev = self._current
        self._current = entry
        self._size += 1

        # Trim from the head if we blew past capacity.
        while self._size > self._capacity and self._head is not self._current:
            victim = self._head
            self._head = victim.next
            if self._head is not None:
                self._head.prev = None
            victim.next = None
            self._size -= 1

    def _truncate_forward(self) -> None:
        node = self._current.next
        while node is not None:
            nxt = node.next
            node.prev = node.next = None
            node = nxt
            self._size -= 1
        self._current.next = None

    def back(self, steps: int = 1) -> str | None:
        if steps < 0:
            raise ValueError("steps must be non-negative")
        while steps > 0 and self._current and self._current.prev:
            self._current = self._current.prev
            steps -= 1
        return self._current.url if self._current else None

    def forward(self, steps: int = 1) -> str | None:
        if steps < 0:
            raise ValueError("steps must be non-negative")
        while steps > 0 and self._current and self._current.next:
            self._current = self._current.next
            steps -= 1
        return self._current.url if self._current else None

    def current_url(self) -> str | None:
        return self._current.url if self._current else None

    def can_go_back(self) -> bool:
        return self._current is not None and self._current.prev is not None

    def can_go_forward(self) -> bool:
        return self._current is not None and self._current.next is not None

    def clear(self) -> None:
        """Wipe history — privacy feature ("clear browsing data")."""
        # Break internal links so GC reclaims the nodes promptly.
        node = self._head
        while node is not None:
            nxt = node.next
            node.prev = node.next = None
            node = nxt
        self._head = self._current = None
        self._size = 0


class Tab:
    """One browser tab with its own isolated history."""

    def __init__(self, initial_url: str | None = None, capacity: int = 200):
        self.id = str(uuid.uuid4())[:8]
        self._history = History(capacity=capacity)
        if initial_url:
            self._history.visit(initial_url)

    def visit(self, url: str, title: str = "") -> None:
        self._history.visit(url, title)

    def back(self, steps: int = 1) -> str | None:
        return self._history.back(steps)

    def forward(self, steps: int = 1) -> str | None:
        return self._history.forward(steps)

    def current_url(self) -> str | None:
        return self._history.current_url()

    def clear_history(self) -> None:
        self._history.clear()

    @property
    def history(self) -> History:
        return self._history


class Browser:
    """Owns multiple tabs and the active tab pointer."""

    def __init__(self):
        self._tabs: dict[str, Tab] = {}
        self._active: str | None = None

    def open_tab(self, url: str) -> str:
        tab = Tab(url)
        self._tabs[tab.id] = tab
        self._active = tab.id
        return tab.id

    def close_tab(self, tab_id: str) -> None:
        if tab_id not in self._tabs:
            raise ValueError("Unknown tab")
        del self._tabs[tab_id]
        if self._active == tab_id:
            self._active = next(iter(self._tabs), None)

    def clear_all_history(self) -> None:
        """Browser-level Clear All Browsing Data."""
        for tab in self._tabs.values():
            tab.clear_history()

    def switch_to(self, tab_id: str) -> None:
        if tab_id not in self._tabs:
            raise ValueError("Unknown tab")
        self._active = tab_id

    @property
    def active(self) -> Tab | None:
        return self._tabs.get(self._active) if self._active else None


if __name__ == "__main__":
    browser = Browser()
    tab_id = browser.open_tab("https://google.com")
    tab = browser.active

    tab.visit("https://google.com/search?q=lld")
    tab.visit("https://crackingwalnuts.com")
    print(f"Current: {tab.current_url()}")            # crackingwalnuts.com

    tab.back()
    print(f"After back: {tab.current_url()}")          # google.com/search
    tab.back()
    print(f"After back x2: {tab.current_url()}")       # google.com

    tab.forward(2)
    print(f"After forward x2: {tab.current_url()}")    # crackingwalnuts.com

    # Branching: go back, then visit something new. Forward path is erased.
    tab.back()
    tab.visit("https://news.ycombinator.com")
    print(f"After branch: {tab.current_url()}")        # hn
    assert not tab.history.can_go_forward()
    print("Forward history correctly cleared after branching.")

    # Second tab is independent.
    second = browser.open_tab("https://github.com")
    assert browser.active.current_url() == "https://github.com"
    browser.switch_to(tab_id)
    assert browser.active.current_url() == "https://news.ycombinator.com"
    print("Tab isolation verified.")

    # Clear-all-browsing-data leaves every tab with an empty history.
    browser.clear_all_history()
    for t in (browser._tabs[tab_id], browser._tabs[second]):
        assert t.current_url() is None
        assert not t.history.can_go_back()
    print("Clear-all wiped every tab's history.")

import java.time.Instant;
import java.util.*;

class HistoryEntry {
    final String url;
    final String title;
    final Instant visitedAt;
    HistoryEntry prev, next;

    HistoryEntry(String url, String title) {
        this.url = url;
        this.title = title;
        this.visitedAt = Instant.now();
    }
}

class History {
    private final int capacity;
    private HistoryEntry current;
    private HistoryEntry head;
    private int size = 0;

    History(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
    }

    void visit(String url, String title) {
        HistoryEntry e = new HistoryEntry(url, title);
        if (current == null) {
            current = head = e;
            size = 1;
            return;
        }
        truncateForward();
        current.next = e;
        e.prev = current;
        current = e;
        size++;
        while (size > capacity && head != current) {
            HistoryEntry victim = head;
            head = victim.next;
            if (head != null) head.prev = null;
            victim.next = null;
            size--;
        }
    }

    private void truncateForward() {
        HistoryEntry n = current.next;
        while (n != null) {
            HistoryEntry nxt = n.next;
            n.prev = null; n.next = null;
            n = nxt;
            size--;
        }
        current.next = null;
    }

    String back(int steps) {
        if (steps < 0) throw new IllegalArgumentException("non-negative");
        while (steps > 0 && current != null && current.prev != null) {
            current = current.prev;
            steps--;
        }
        return current == null ? null : current.url;
    }

    String forward(int steps) {
        if (steps < 0) throw new IllegalArgumentException("non-negative");
        while (steps > 0 && current != null && current.next != null) {
            current = current.next;
            steps--;
        }
        return current == null ? null : current.url;
    }

    String currentUrl() { return current == null ? null : current.url; }
    boolean canGoBack() { return current != null && current.prev != null; }
    boolean canGoForward() { return current != null && current.next != null; }

    void clear() {
        HistoryEntry n = head;
        while (n != null) {
            HistoryEntry nxt = n.next;
            n.prev = null; n.next = null;
            n = nxt;
        }
        head = null; current = null; size = 0;
    }
}

class Tab {
    final String id = UUID.randomUUID().toString().substring(0, 8);
    private final History history;

    Tab(String initialUrl) {
        this.history = new History(200);
        if (initialUrl != null) history.visit(initialUrl, "");
    }

    void visit(String url) { history.visit(url, ""); }
    String back(int steps) { return history.back(steps); }
    String forward(int steps) { return history.forward(steps); }
    String currentUrl() { return history.currentUrl(); }
    void clearHistory() { history.clear(); }
    History history() { return history; }
}

public class Browser {
    private final Map<String, Tab> tabs = new LinkedHashMap<>();
    private String activeTabId;

    public String openTab(String url) {
        Tab t = new Tab(url);
        tabs.put(t.id, t);
        activeTabId = t.id;
        return t.id;
    }

    public void closeTab(String id) {
        if (!tabs.containsKey(id)) throw new IllegalArgumentException("Unknown tab");
        tabs.remove(id);
        if (id.equals(activeTabId))
            activeTabId = tabs.isEmpty() ? null : tabs.keySet().iterator().next();
    }

    public void switchTo(String id) {
        if (!tabs.containsKey(id)) throw new IllegalArgumentException("Unknown tab");
        activeTabId = id;
    }

    public Tab active() { return activeTabId == null ? null : tabs.get(activeTabId); }

    public void clearAllHistory() {
        for (Tab t : tabs.values()) t.clearHistory();
    }

    public static void main(String[] args) {
        Browser b = new Browser();
        String tabId = b.openTab("https://google.com");
        Tab t = b.active();

        t.visit("https://google.com/search?q=lld");
        t.visit("https://crackingwalnuts.com");
        System.out.println("Current: " + t.currentUrl());

        t.back(1);
        System.out.println("Back: " + t.currentUrl());
        t.back(1);
        System.out.println("Back x2: " + t.currentUrl());
        t.forward(2);
        System.out.println("Forward x2: " + t.currentUrl());

        t.back(1);
        t.visit("https://news.ycombinator.com");
        System.out.println("Branched: " + t.currentUrl());
        System.out.println("Can go forward: " + t.history().canGoForward());

        b.clearAllHistory();
        System.out.println("After clear-all, currentUrl: " + t.currentUrl()
            + " canGoBack: " + t.history().canGoBack());
    }
}

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