Implement cursor-based query pagination

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

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

Example 1

Input: ([['r2', 20, 'B'], ['r1', 10, 'A'], ['r3', 20, 'C'], ['r0', 5, 'Z']], 10, 2, None)
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.

Example 2

Input: ([['r2', 20, 'B'], ['r1', 10, 'A'], ['r3', 20, 'C'], ['r0', 5, 'Z']], 10, 2, [20, 'r2'])
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

Example 1

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

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

Example 2

Input: ([['encode', [-5, 'a|b,c:42']], ['decode', '[-5,"a|b,c:42"]']],)
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

Example 1

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

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

Example 2

Input: ([['b', 5, 'B'], ['a', 5, 'A'], ['c', 5, 'C'], ['d', 6, 'D']], 5, 2, [5, 'c'])
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

Example 1

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

Explanation: The sorted index is reused across both queries.

Example 2

Input: ([['r2', 20, 'B'], ['r1', 10, 'A'], ['r3', 20, 'C'], ['r0', 5, 'Z']], [[20, 5, None], [21, 1, None]])
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.