Quick Overview

This question evaluates understanding of cursor-based pagination, deterministic ordering with tie-breakers, cursor encoding, and in-memory data-structure management for efficient filtered queries.

Implement cursor-based query pagination

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are building a small **in-memory database** that stores rows with the following fields: - `id` (string, unique) - `score` (integer) - `payload` (string) You need to support a **read API** that returns results in a deterministic order and supports **pagination**. ## Requirements 1. Store rows in memory (you may assume a single process). 2. Implement a query that returns all rows with `score >= minScore`. 3. Results must be sorted by: 1) `score` ascending 2) `id` ascending (tie-breaker) 4. Pagination must be **cursor-based** (not offset-based): - The client provides a `cursor` representing “the last row seen”. - The server returns up to `pageSize` rows **after** that cursor, plus a `nextCursor`. - If there are no more rows, `nextCursor = null`. ## Function signature (conceptual) - Input: `minScore`, `pageSize`, `cursor` (nullable) - Output: `(rows[], nextCursor)` ## Follow-ups - How do you encode the cursor so it is stable and unambiguous? - How do you avoid duplicates or missing rows across pages when there are many rows with the same `score`? - What is the time complexity of your approach, and how would you improve it for large datasets? ## Constraints - Up to 1,000,000 rows. - `pageSize` up to 1,000. - Assume no concurrent writes during a single paginated scan (you can state this assumption explicitly).

Quick Answer: This question evaluates understanding of cursor-based pagination, deterministic ordering with tie-breakers, cursor encoding, and in-memory data-structure management for efficient filtered queries.

Part 1: In-Memory Cursor-Based Pagination by Score and ID

Build a read query for an in-memory table of rows. Each row is represented as [id, score, payload], where id is a unique string, score is an integer, and payload is a string. Return rows with score >= minScore sorted by score ascending, then id ascending. Pagination is cursor-based: cursor is None for the first page, or [lastScore, lastId] representing the last row seen by the client. Return up to pageSize rows strictly after the cursor. Return nextCursor as [score, id] for the last row returned only if more matching rows remain; otherwise return None. Assume no concurrent writes during one paginated scan.

Constraints

  • 0 <= len(rows) <= 1,000,000
  • All row ids are unique strings.
  • Scores are integers.
  • 1 <= pageSize <= 1,000
  • cursor is either None or a two-element list [score, id].
  • No concurrent writes occur during a single paginated scan.

Examples

Input: ([['r2', 20, 'B'], ['r1', 10, 'A'], ['r3', 20, 'C'], ['r0', 5, 'Z']], 10, 2, None)

Expected Output: ([['r1', 10, 'A'], ['r2', 20, 'B']], [20, 'r2'])

Explanation: Rows with score >= 10 are r1, r2, and r3 after sorting. The first page returns r1 and r2, and r3 remains.

Input: ([['r2', 20, 'B'], ['r1', 10, 'A'], ['r3', 20, 'C'], ['r0', 5, 'Z']], 10, 2, [20, 'r2'])

Expected Output: ([['r3', 20, 'C']], None)

Explanation: The cursor excludes all keys <= (20, r2), so only r3 remains.

Hints

  1. Sort using the same fields that define the cursor: first score, then id.
  2. The cursor is exclusive: a row is eligible only if (score, id) is greater than the cursor key.

Part 2: Stable and Unambiguous Cursor Encoding

Implement a stable cursor encoder and decoder. A cursor represents the last row seen as [score, id]. To avoid delimiter ambiguity, encode a non-null cursor as a compact JSON array string with no extra spaces, for example [10,"rowA"]. A null cursor remains None. The function receives a list of operations. Each operation is ['encode', value] or ['decode', value]. For encode, value is None or [score, id]. For decode, value is None or a token produced by this encoding format.

Constraints

  • 0 <= len(operations) <= 100,000
  • Scores are integers.
  • Ids are strings and may contain punctuation such as commas, pipes, colons, or spaces.
  • Decode inputs are valid tokens produced by the specified format, or None.

Examples

Input: ([['encode', [10, 'rowA']], ['decode', '[10,"rowA"]']],)

Expected Output: ['[10,"rowA"]', [10, 'rowA']]

Explanation: The encoded cursor is compact JSON, and decoding restores the original score and id.

Input: ([['encode', [-5, 'a|b,c:42']], ['decode', '[-5,"a|b,c:42"]']],)

Expected Output: ['[-5,"a|b,c:42"]', [-5, 'a|b,c:42']]

Explanation: Punctuation inside the id does not confuse the encoding.

Hints

  1. Avoid concatenating score and id using a raw separator because ids may contain that separator.
  2. A structured format such as JSON preserves types and boundaries between fields.

Part 3: Paginate Safely Through Duplicate Scores

Many rows can have the same score, so a cursor that stores only score can skip or repeat rows. Implement a next-page helper that uses the composite cursor [score, id]. Rows are represented as [id, score, payload]. Return only the ids of rows in the next page, sorted by score ascending and id ascending. A row is after the cursor only if its composite key (score, id) is strictly greater than the cursor key.

Constraints

  • 0 <= len(rows) <= 1,000,000
  • All ids are unique strings.
  • 1 <= pageSize <= 1,000
  • Rows must be ordered by score ascending, then id ascending.
  • The cursor is exclusive.

Examples

Input: ([['b', 5, 'B'], ['a', 5, 'A'], ['c', 5, 'C'], ['d', 6, 'D']], 5, 2, [5, 'a'])

Expected Output: (['b', 'c'], [5, 'c'])

Explanation: The scan continues within score 5 using id order, returning b and c before d.

Input: ([['b', 5, 'B'], ['a', 5, 'A'], ['c', 5, 'C'], ['d', 6, 'D']], 5, 2, [5, 'c'])

Expected Output: (['d'], None)

Explanation: After cursor (5, c), only d remains.

Hints

  1. For tied scores, compare ids to decide whether a row comes after the cursor.
  2. The correct condition is key > cursorKey, not score > cursorScore.

Part 4: Indexed Pagination for Large Static Datasets

For a large static in-memory dataset, sorting and scanning for every page is inefficient. Implement a batch query function that builds a sorted index once, then answers many cursor-pagination queries using binary search. Rows are [id, score, payload]. Each query is [minScore, pageSize, cursor], where cursor is None or [lastScore, lastId]. For each query, return up to pageSize matching rows after the cursor, sorted by score then id, plus a next cursor if more matching rows remain.

Constraints

  • 0 <= len(rows) <= 1,000,000
  • 0 <= len(queries) <= 100,000
  • All ids are unique strings.
  • 1 <= pageSize <= 1,000 for every query.
  • Rows are static during the batch of queries.
  • cursor is either None or [score, id]. It may be a boundary key even if that exact row is not present.

Examples

Input: ([['r2', 20, 'B'], ['r1', 10, 'A'], ['r3', 20, 'C'], ['r0', 5, 'Z']], [[10, 2, None], [10, 2, [20, 'r2']]])

Expected Output: [[[['r1', 10, 'A'], ['r2', 20, 'B']], [20, 'r2']], [[['r3', 20, 'C']], None]]

Explanation: The sorted index is reused across both queries.

Input: ([['r2', 20, 'B'], ['r1', 10, 'A'], ['r3', 20, 'C'], ['r0', 5, 'Z']], [[20, 5, None], [21, 1, None]])

Expected Output: [[[['r2', 20, 'B'], ['r3', 20, 'C']], None], [[], None]]

Explanation: The first query returns all rows with score 20; the second has no matches.

Hints

  1. Precompute rows sorted by the composite key (score, id).
  2. For each query, combine two lower bounds: first score >= minScore, and first key > cursor.

Loading coding console...