Katkat
Back

Implement single-tab browser history navigation

ChimeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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(
  1. 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.