Katkat
Back

Implement cursor-based query pagination

CoinbaseSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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

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

Follow-up questions

  • 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?