Quick 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.

Implement single-tab browser history navigation

Company: Chime

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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(homepage)` — initialize the session; the current page starts at `homepage`. - `visit(url)` — navigate to `url` from the current page and clear any forward history. - `back(steps)` — move up to `steps` pages back; if fewer pages exist, move as far as possible. Return the current url after the move. - `forward(steps)` — move up to `steps` pages forward; if fewer pages exist, move as far as possible. Return the current url after the move. - `haveVisited(url)` — return whether the session has **ever** visited `url` at least once since construction, regardless of whether it currently sits in back/forward history. **Driver contract for this console** You implement a single function `solution(operations, args)`: - `operations` is a list of method-name strings; the first is always `"BrowserSession"`. - `args` is a parallel list of argument lists for each operation. - Replay the operations against one `BrowserSession` instance and return a list of results, one per operation. Use `None`/`null` for constructor and `visit` (which return nothing), the returned url string for `back`/`forward`, and the boolean for `haveVisited`. **Edge cases to handle** - `steps <= 0` (including negative) must not move the cursor. - `visit` must truncate any forward history before appending the new page. - `back`/`forward` past the ends clamp to the oldest / newest page. - `haveVisited` is true for every url ever visited (and for the homepage), even after that url is dropped from the live forward history by a later `visit`. **Constraints** - Target O(1) amortized time per operation, O(n) space for n total visits. - Justify your data structure (dynamic array + index, two stacks, or doubly linked list + cursor) and the time/space trade-offs.

Constraints

  • The first operation is always BrowserSession(homepage).
  • Urls are non-empty strings; the current page always exists.
  • steps may be 0 or negative; non-positive steps must not move the cursor.
  • back/forward clamp at the oldest/newest page rather than erroring.
  • haveVisited is true for any url ever visited (and the homepage), even after a later visit() drops it from the live forward history.
  • Target O(1) amortized time per operation and O(n) space for n total visits.

Examples

Input: (['BrowserSession', 'visit', 'visit', 'visit', 'back', 'back', 'forward', 'visit', 'forward', 'back', 'back'], [['leetcode.com'], ['google.com'], ['facebook.com'], ['youtube.com'], [1], [1], [1], ['linkedin.com'], [2], [2], [7]])

Expected Output: [None, None, None, None, 'facebook.com', 'google.com', 'facebook.com', None, 'linkedin.com', 'google.com', 'leetcode.com']

Explanation: Canonical LeetCode-1472 sequence. After visiting google/facebook/youtube the cursor is at youtube; back(1)->facebook, back(1)->google, forward(1)->facebook, then visit(linkedin) clears the forward history (youtube is gone) and lands on linkedin. forward(2) is clamped to linkedin (newest), back(2)->google, back(7) clamps to the homepage leetcode.com.

Input: (['BrowserSession', 'visit', 'visit', 'haveVisited', 'haveVisited', 'back', 'haveVisited'], [['home.com'], ['a.com'], ['b.com'], ['a.com'], ['z.com'], [1], ['b.com']])

Expected Output: [None, None, None, True, False, 'a.com', True]

Explanation: haveVisited bonus: a.com was visited so it is true; z.com never was so it is false. After back(1) lands on a.com, b.com is still considered visited because the visited set is never shrunk.

Hints

  1. A dynamic array of urls plus an integer cursor gives O(1) back/forward by just clamping the index — no node rewiring needed. A doubly linked list + cursor is the classic alternative but costs more pointers and worse cache locality for the same asymptotics.
  2. visit must drop the forward history first: truncate the array to cursor+1, then append. That truncation is what makes 'visit after going back' branch correctly.
  3. haveVisited can't read the live history (a page can be truncated away), so track every visited url in a separate hash set that you never shrink.
  4. Clamp steps before moving: back -> max(0, cur - steps), forward -> min(len-1, cur + steps), and treat steps <= 0 as a no-op so the cursor stays put.

Loading coding console...