Summary
System design round at Chime for a software engineering role. The whole thing was a single extended problem about evolving a browser history structure to support multiple tabs, which sounds manageable until you're 20 minutes in and someone asks about concurrent tab access.
Questions Asked(4)
I started with the per-tab history piece since that felt familiar, basically a doubly-linked list or two stacks approach.
Suggested Approach
Start by clarifying the scope and constraints of the system, then define the API surface with clear method signatures before choosing data structures that efficiently support each operation. Ground your design in real browser behavior — each tab maintains its own independent history stack with a current pointer, while the browser manages a collection of active tabs.
Clarify Requirements & Constraints
Ask clarifying questions: Is history per-tab or global? Is there a max history depth? Should closed tab history be recoverable? This shows structured thinking and prevents wasted design effort.
Define the API Surface
Sketch out each method signature with parameters and return types — e.g., openTab() -> tabId, visit(tabId, url), back(tabId) -> url, forward(tabId) -> url, closeTab(tabId), switchTab(tabId), haveVisited(url) -> bool. Explain the intent and expected behavior of each.
Choose Data Structures
Model each tab's history as a doubly-linked list or array with a current index pointer to support O(1) back/forward navigation, and manage all tabs in a HashMap<tabId, TabHistory> for O(1) tab lookup. For haveVisited, maintain a global HashSet<url> updated on every visit call.
Walk Through Key Operations
Trace through visit (truncate forward history, append URL, advance pointer), back (decrement pointer if possible), and forward (increment pointer if possible) to validate your data structure choices and surface edge cases like being at the beginning or end of history.
Discuss Trade-offs & Extensions
Address memory management (capping history depth with a deque), thread safety if tabs can be accessed concurrently, and optional features like tab grouping or session persistence — demonstrating you can reason about production-level concerns.
Key Points to Mention
Map gives O(1) lookup by tabId which is nice, but a list preserves insertion order which matters if you want to render tabs left-to-right like a real browser.
Suggested Approach
Start by clarifying the access patterns and operations needed (lookup by ID, ordered traversal, insertion, deletion), then systematically compare Map vs List across those dimensions. Ground your recommendation in concrete complexity tradeoffs rather than stating a preference without justification.
Define the Core Operations
Begin by enumerating the operations the tab collection must support: create a tab, close a tab, switch to a tab by ID, reorder tabs, and iterate over all tabs. Clarifying these upfront anchors the entire tradeoff discussion.
Analyze Map Characteristics
Explain that a Map (hash map) provides O(1) average-case lookup, insertion, and deletion by tab ID, making it ideal for direct access patterns. However, it does not preserve insertion order natively and requires additional overhead for ordered iteration.
Analyze List Characteristics
Explain that a List (array or linked list) preserves order naturally and supports O(n) sequential traversal efficiently, but lookup and deletion by tab ID degrade to O(n) without an index. Reordering (drag-and-drop) is O(1) for linked lists but O(n) for arrays due to shifting.
Discuss Memory Implications
Note that a Map carries higher memory overhead per entry due to hash buckets and potential load-factor resizing, while an array is more cache-friendly and memory-compact. For a browser with hundreds of tabs, this difference becomes meaningful.
Propose a Hybrid Solution and Justify
Recommend a hybrid approach: a Map keyed by tab ID for O(1) lookups combined with an ordered array or doubly-linked list of IDs to maintain tab order. Explain that this trades a small amount of extra memory for optimal complexity across all key operations.
Key Points to Mention
Blanked for a second here.
Suggested Approach
Frame your answer around the specific concurrency challenges that arise with multiple browser tabs (shared state, race conditions, stale data) and then walk through a layered strategy combining immutability, locking primitives, and architectural patterns. Ground your response in real trade-offs relevant to a fintech context like Chime, where data consistency is critical for things like account balances and transactions. Demonstrate that you understand both the browser-side and backend dimensions of the problem.
Define the Concurrency Problem
Clearly articulate what 'concurrent tabs' means in practice — multiple JavaScript execution contexts potentially reading and writing shared state (localStorage, IndexedDB, server resources) simultaneously. Identify the specific failure modes: race conditions, stale reads, and conflicting writes.
Establish Immutability at the State Layer
Explain how treating shared state as immutable (e.g., using Redux with immutable updates or libraries like Immer) prevents accidental mutation and makes state changes predictable and traceable. Immutability also simplifies debugging and enables time-travel debugging.
Coordinate Across Tabs with Browser APIs
Discuss browser-native mechanisms like BroadcastChannel API for cross-tab messaging, SharedWorker for a single shared execution context, or localStorage events to synchronize state changes across tabs. Explain the trade-offs between these approaches in terms of complexity and browser support.
Apply Locking and Conflict Resolution Strategies
Cover optimistic locking (using ETags or version numbers on API responses) to detect and handle conflicting writes without blocking, versus pessimistic locking for high-stakes operations like payment submissions. Mention the Web Locks API as a browser primitive for coordinating access to shared resources.
Address Backend Consistency and Idempotency
Emphasize that true thread safety in a multi-tab scenario requires backend support — idempotent API endpoints prevent duplicate transactions if the same action fires from two tabs, and server-side optimistic concurrency control (e.g., database row versioning) ensures data integrity. Tie this back to Chime's fintech context where double-charging or duplicate transfers are unacceptable.
Key Points to Mention
Short answer: I didn't have a good one.
Suggested Approach
Frame your answer around the trade-off triangle of memory efficiency, correctness, and user experience — explaining how capping or eviction directly impacts whether haveVisited returns accurate results. Walk through concrete scenarios where a URL gets evicted and then revisited, showing you understand the real-world consequences. Tie your analysis back to cross-tab consistency, since shared state introduces additional complexity around eviction ordering and synchronization.
Define the Problem Space
Clarify what haveVisited needs to guarantee — exact correctness vs. approximate — and what the memory budget is. Establish whether the history store is shared across tabs (e.g., via a service worker, IndexedDB, or in-memory shared store) or per-tab.
Explain Eviction Policy Options
Walk through common eviction strategies: LRU (Least Recently Used), LFU (Least Frequently Used), FIFO, and TTL-based expiry. Explain how each one decides which URLs get dropped and why that matters for haveVisited accuracy.
Analyze Behavioral Impact
Describe the failure mode: if a URL is evicted and the user revisits it, haveVisited returns false (a false negative), causing the system to treat it as new — which could trigger duplicate crawls, re-highlighting links, or redundant API calls. Quantify the risk based on eviction aggressiveness.
Address Cross-Tab Complexity
Explain that shared state across tabs means eviction in one tab can silently invalidate haveVisited results in another tab, creating race conditions or stale reads. Discuss synchronization mechanisms like BroadcastChannel, SharedWorker, or a centralized store with versioning to mitigate this.
Propose Mitigation Strategies
Recommend solutions such as tiered storage (hot in-memory cache + persistent IndexedDB fallback), probabilistic structures like Bloom filters for memory-bounded approximate tracking, or priority-based eviction that protects recently active tabs' URLs from being purged.
Key Points to Mention
Discussion(4)
Sign in to join the discussion.
Separate set for visited URLs is exactly right. The insight you landed on is the key one: haveVisited is a membership query, not a history traversal query, so it shouldn't share a data structure with the navigable history buffer. Those two things have different eviction semantics by definition.
Per-tab locks is the right instinct and I'd have said the same thing. The gap is exactly what you described: switchTab touches shared state (whatever field tracks the currently active tab), so you need a separate lock or atomic for that, otherwise you have a race between a tab switch and a concurrent visit call that could corrupt which tab's history gets the new entry.
One thing worth floating in that conversation is whether you even need mutable shared state for active tab. If the browser UI layer owns "which tab is active" and just passes the tabId into every API call explicitly, the backend history manager becomes stateless with respect to active tab and the whole problem goes away. I've found that interviewers at fintechs like Chime tend to respond well when you question whether shared mutable state is necessary at all rather than just reaching for a lock.
Using both a map and an ordered list isn't papering over a gap, that's actually the standard pattern. A map keyed by tabId for O(1) access, plus a Vec or array of IDs to preserve display order. The real question is what "ordering" means when tabs get closed and reopened. If you close tab 2 and open a new one, does it go at the end or fill the gap? Most browsers append at the end, which makes the ordered list append-only until a close, and close is just a removal from both structures.
The memory angle worth mentioning: the ordered list only holds IDs, so the overhead is tiny. The map holds the actual history stacks, which is where your real memory cost lives.
The openTab return type question is one I've fumbled too, and the reason it trips people up is that it looks like a trivial implementation detail until you realize the tabId is basically a capability token that every other API call depends on. Returning a plain integer is fine, but you should be ready to defend it. An object wrapper buys you forward compatibility (attach metadata later without breaking callers) but adds overhead and makes the API feel heavier than it needs to be for this scope. Committing to int and saying so clearly is the better move in an interview.
For the per-tab history structure, two stacks is actually cleaner to explain than a doubly-linked list because the back/forward semantics map directly: back pops from the forward stack onto the back stack, visit clears the forward stack and pushes to back. A doubly-linked list works but you have to manage a current pointer and explain truncation on new visits, which is a bit more to hold in your head under pressure.
On haveVisited, the per-tab vs global distinction is genuinely a product decision disguised as a data structure question. Chrome treats it globally (the purple link color), but per-tab visited state is a legitimate privacy feature. The honest answer is to say both are defensible, name the tradeoff (global needs a shared set with its own concurrency story, per-tab is simpler but less useful), and ask which semantic the interviewer wants. Picking one and owning it beats hedging.