Implement single-tab browser history navigation
Overview
This question evaluates understanding of data structures, stateful API behavior, amortized time complexity, set membership tracking, and edge-case handling for implementing browser-like history navigation in the coding & algorithms domain.
Chime
Sep 6, 2025, 12:00 AM
Software Engineer
Technical Screen
Coding & Algorithms
0
0
Implement a BrowserSession for a single-tab browser.
APIs:
- BrowserSession(string homepage): Initialize with homepage; current page starts at homepage.
- void visit(string url): Navigate to url from the current page and clear any forward history.
- string back(int steps): Move up to steps back in history; if fewer pages exist, move as far as possible. Return the current url after the move.
- string forward(int steps): Move up to steps forward in history; if fewer pages exist, move as far as possible. Return the current url after the move.
Bonus:
- bool haveVisited(string url): Return whether the session has ever visited url at least once since construction, regardless of whether it is currently in back/forward history.
Requirements:
- Target O(
- amortized time per operation and O(n) space for n total visits.
- Define how to handle edge cases (e.g., steps <= 0, visiting the same url consecutively, empty forward history).
- Describe and justify your data structure choices (e.g., two stacks, doubly linked list + cursor, dynamic array + index) and their trade-offs in time/space.