How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Chime.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Chime during technical interviews.

Implement single-tab browser history navigation

Q: Implement single-tab browser history navigation

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.

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.

Input: (['BrowserSession', 'back', 'forward'], [['only.com'], [5], [5]])

Expected Output: [None, 'only.com', 'only.com']

Explanation: Single-page edge case: with only the homepage, both back(5) and forward(5) clamp and return only.com.

Input: (['BrowserSession', 'visit', 'back', 'forward', 'back'], [['p.com'], ['q.com'], [0], [0], [-3]])

Expected Output: [None, None, 'q.com', 'q.com', 'q.com']

Explanation: steps <= 0 edge case: after visit(q.com) the cursor is on q.com; back(0), forward(0), and back(-3) all leave the cursor unmoved on q.com.

Input: (['BrowserSession', 'visit', 'visit', 'back', 'visit', 'forward', 'haveVisited'], [['h.com'], ['x.com'], ['y.com'], [2], ['z.com'], [3], ['y.com']])

Expected Output: [None, None, None, 'h.com', None, 'z.com', True]

Explanation: visit-clears-forward edge case: after back(2) to h.com, visit(z.com) truncates the forward history (x and y drop out of the live list), so forward(3) clamps to z.com. y.com is still haveVisited=true even though it was truncated.

Hints

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

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.