Coding - Query Pagination - Coinbase Interview Question | DarkInterview

Query Pagination

CodingOnsite, PhoneSoftware EngineerReported Jul, 2026High Frequency

Problem Overview

Design and implement a transaction query system with filtering and cursor-based pagination. You are given a dataset of financial transactions and need to build an interface that supports filtering by multiple fields and paginating through results efficiently.

A key aspect of this problem is that the interviewer does not prescribe what methods to create or what their signatures should be. You need to design a clean, usable API yourself.

For simplicity, we'll work with an in-memory dataset, but you should consider how your design would translate to a real database-backed implementation. [Source: darkinterview.com]

Sample Dataset

transactions = [
    {"time": 1,  "id": 11, "user_id": 1, "currency": 1, "amount": 10},
    {"time": 2,  "id": 12, "user_id": 1, "currency": 3, "amount": 11},
    {"time": 3,  "id": 13, "user_id": 2, "currency": 2, "amount": -10},
    {"time": 4,  "id": 14, "user_id": 2, "currency": 2, "amount": 12},
    {"time": 5,  "id": 15, "user_id": 1, "currency": 1, "amount": 10},
    {"time": 6,  "id": 16, "user_id": 1, "currency": 2, "amount": 13},
    {"time": 7,  "id": 17, "user_id": 1, "currency": 2, "amount": 13},
    {"time": 8,  "id": 18, "user_id": 1, "currency": 2, "amount": 10},
    {"time": 9,  "id": 19, "user_id": 1, "currency": 1, "amount": 15},
    {"time": 10, "id": 20, "user_id": 1, "currency": 1, "amount": 15},
    {"time": 10, "id": 21, "user_id": 1, "currency": 1, "amount": 16},
    {"time": 11, "id": 22, "user_id": 1, "currency": 1, "amount": 5},
    {"time": 11, "id": 23, "user_id": 1, "currency": 2, "amount": 5},
    {"time": 12, "id": 24, "user_id": 1, "currency": 2, "amount": 6},
    {"time": 13, "id": 25, "user_id": 1, "currency": 1, "amount": 10},
]

Part 1: Filtering

Problem Statement

Build a transaction query system that allows filtering by any combination of the following fields:

Time range: Filter transactions within a [start_time, end_time] range (inclusive)
User ID: Filter transactions belonging to a specific user
Currency: Filter transactions for a specific currency
Amount range: Filter transactions within a [min_amount, max_amount] range (inclusive)

Design the interface so that filters can be set independently and combined. The caller should be able to set one or more filters, then execute the query to get matching results.

Design Considerations

Think about: [Source: darkinterview.com]

How should filters be configured — individual setter methods, a builder pattern, or constructor parameters?
How should the query be executed — a separate execute() method, or does setting filters immediately return results?
Should filters be reusable and modifiable after creation?

Example Usage

query = TransactionQuery(transactions)

# Filter by user
query.set_user_id(1)
results = query.execute()
# Returns all transactions where user_id == 1

# Filter by time range and currency
query = TransactionQuery(transactions)
query.set_time_range(5, 10)
query.set_currency(1)
results = query.execute()
# Returns transactions where 5 <= time <= 10 AND currency == 1
# -> [{"time": 5, "id": 15, ...}, {"time": 9, "id": 19, ...},
#     {"time": 10, "id": 20, ...}, {"time": 10, "id": 21, ...}]

Part 1 Solution

class TransactionQuery:
    def __init__(self, transactions: list):
        self.transactions = transactions
        self.filters = {}

    def set_user_id(self, user_id: int) -> 'TransactionQuery':
        """Filter by user ID."""
        self.filters['user_id'] = user_id
        return self

    def set_currency(self, currency: int) -> 'TransactionQuery':
        """Filter by currency."""
        self.filters['currency'] = currency
        return self

    def set_time_range(self, start: int, end: int) -> 'TransactionQuery':
        """Filter by time range [start, end] inclusive."""
        self.filters['time_start'] = start
        self.filters['time_end'] = end
        return self

    def set_amount_range(self, min_amt: float, max_amt: float) -> 'TransactionQuery':
        """Filter by amount range [min, max] inclusive."""
        self.filters['amount_min'] = min_amt
        self.filters['amount_max'] = max_amt
         

     () -> :
        
           .filters  txn[] != .filters[]:
             
           .filters  txn[] != .filters[]:
             
           .filters  txn[] < .filters[]:
             
           .filters  txn[] > .filters[]:
             
           .filters  txn[] < .filters[]:
             
           .filters  txn[] > .filters[]:
             
         

     () -> :
        
         [txn  txn  .transactions  ._matches(txn)]

Design Notes:

Setter methods with method chaining — Each setter returns self, allowing chaining: query.set_user_id(1).set_currency(2).execute()
Filters stored as a dict — Simple and extensible. Adding a new filter field only requires a new setter and one line in _matches()
Database translation — In a real system, each filter would map to a SQL WHERE clause. The in-memory loop corresponds to a full table scan; with a database, you'd use indexes on user_id, time, currency, etc.

Complexity:

Operation	Time	Space
`set_*`	O(1)	O(1)
`execute`	O(N)	O(R)

Where N = total transactions, R = number of matching results. [Source: darkinterview.com]

Part 2: Cursor-Based Pagination

Problem Statement

Interviewer: "Now add pagination support. Given a page size, the caller should be able to iterate through filtered results one page at a time using cursor-based pagination."

Extend the query system to support pagination. After setting filters and a page size, the caller should be able to:

Fetch the first page of results
Fetch subsequent pages using a cursor returned from the previous call
Know when there are no more results

The cursor should be opaque to the caller — they pass back whatever cursor value they received to get the next page. [Source: darkinterview.com]

Design Considerations

Cursor representation: What should the cursor encode? An offset? A last-seen ID?
Stability: If the underlying data doesn't change, paginating from cursor 0 through the end should return every matching row exactly once
Direction: Should the caller be able to paginate backward as well as forward?

Example Usage

query = TransactionQuery(transactions)
query.set_user_id(1)
query.set_page_size(3)

# First page
page1 = query.fetch_page()
# page1.data -> first 3 matching transactions
# page1.next_cursor -> cursor to fetch the next page

# Second page
page2 = query.fetch_page(cursor=page1.next_cursor)
# page2.data -> next 3 matching transactions
# page2.next_cursor -> cursor for page 3 (or None if no more results)

# Iterate through all pages
cursor = 0
while cursor is not None:
    page = query.fetch_page(cursor=cursor)
    print(page.data)
    cursor = page.next_cursor

Part 2 Solution

class Page:
    def __init__(self, data: list, next_cursor: int = None, prev_cursor: int = None):
        self.data = data
        self.next_cursor = next_cursor
        self.prev_cursor = prev_cursor


class TransactionQuery:
    def __init__(self, transactions: list):
        self.transactions = transactions
        self.filters = {}
        self.page_size = None

    def set_user_id(self, user_id: int) -> 'TransactionQuery':
        self.filters['user_id'] = user_id
        return self

    def set_currency(self, currency: int) -> 'TransactionQuery':
        self.filters['currency'] = currency
        return self

    def set_time_range(self, start: int, end: int) -> 'TransactionQuery':
        self.filters['time_start'] = start
        self.filters['time_end'] = end
        return self

    def () -> :
        .filters[] = min_amt
        .filters[] = max_amt
         

     () -> :
        .page_size = size
         

     () -> :
           .filters  txn[] != .filters[]:
             
           .filters  txn[] != .filters[]:
             
           .filters  txn[] < .filters[]:
             
           .filters  txn[] > .filters[]:
             
           .filters  txn[] < .filters[]:
             
           .filters  txn[] > .filters[]:
             
         

     () -> :
        
         [txn  txn  .transactions  ._matches(txn)]

     () -> Page:
        
         .page_size  :
             ValueError()

        
        matched = []
        skipped = 
        remaining_after = 

         txn  .transactions:
              ._matches(txn):
                
             skipped < cursor:
                skipped += 
                
             (matched) < .page_size:
                matched.append(txn)
            :
                remaining_after = 
                

        next_cursor = cursor + (matched)  remaining_after  
        prev_cursor = cursor - .page_size  cursor >   
         prev_cursor     prev_cursor < :
            prev_cursor = 

         Page(data=matched, next_cursor=next_cursor, prev_cursor=prev_cursor)

Example Walkthrough

transactions = [
    {"time": 1,  "id": 11, "user_id": 1, "currency": 1, "amount": 10},
    {"time": 2,  "id": 12, "user_id": 1, "currency": 3, "amount": 11},
    {"time": 3,  "id": 13, "user_id": 2, "currency": 2, "amount": -10},
    {"time": 4,  "id": 14, "user_id": 2, "currency": 2, "amount": 12},
    {"time": 5,  "id": 15, "user_id": 1, "currency": 1, "amount": 10},
    {"time": 6,  "id": 16, "user_id": 1, "currency": 2, "amount": 13},
    {"time": 7,  "id": 17, "user_id": 1, : , : },
    {: ,  : , : , : , : },
    {: ,  : , : , : , : },
    {: , : , : , : , : },
    {: , : , : , : , : },
    {: , : , : , : , : },
    {: , : , : , : , : },
    {: , : , : , : , : },
    {: , : , : , : , : },
]

query = TransactionQuery(transactions)
query.set_user_id().set_currency().set_page_size()


page = query.fetch_page()




page = query.fetch_page(cursor=)




page = query.fetch_page(cursor=)




cursor = 
 cursor   :
    page = query.fetch_page(cursor=cursor)
     txn  page.data:
        ()
    cursor = page.next_cursor

Design Notes:

Offset-based cursor — The cursor is an integer representing how many matching rows to skip. This is simple and supports both forward and backward pagination
Opaque cursor — The caller treats it as a token. In a production system, the cursor could encode a last-seen id or time value for keyset pagination, which is more efficient than offset-based
Efficient scanning — The fetch_page method streams through transactions and stops as soon as a full page is collected, avoiding materializing all filtered results. This mirrors how a database would use LIMIT and OFFSET
Backward pagination — prev_cursor is computed from the current cursor position. The caller can paginate both forward and backward

Offset vs. Keyset Pagination:

Approach	Pros	Cons
Offset (used here)	Simple, supports jumping to any page	O(cursor) skip cost, unstable if rows are inserted/deleted
Keyset (`WHERE id > last_id`)	O(1) seek with index, stable under inserts	Cannot jump to arbitrary page, requires a unique ordered column

In a database-backed system, keyset pagination (using WHERE id > :last_seen_id ORDER BY id LIMIT :page_size) is preferred because the database can seek directly to the cursor position using an index, rather than scanning and skipping rows. [Source: darkinterview.com]

Complexity:

Operation	Time	Space
`fetch_page`	O(cursor + P)	O(P)

Where P = page size. The O(cursor) cost comes from skipping already-seen rows. With keyset pagination and a database index, this would be O(P).

Follow-Up Discussion Topics

Discussed in Interviews

Offset vs. keyset pagination: What are the trade-offs? When would you choose one over the other? [Source: darkinterview.com]
- Offset is simpler but degrades as the cursor grows (must skip rows)
- Keyset is more efficient but requires a unique sortable column and doesn't support arbitrary page jumps
Cursor stability: What happens if transactions are inserted or deleted between page fetches?
- Offset-based: may skip or duplicate rows
- Keyset-based: stable — always returns rows after the last-seen key
Bidirectional pagination: How would you support "previous page"?
- Offset: subtract page size from cursor
- Keyset: reverse the sort order and comparison (WHERE id < :cursor ORDER BY id DESC)
Database optimization: How would filters translate to SQL? [Source: darkinterview.com]
- Each filter becomes a WHERE clause
- Composite indexes on frequently combined filters (e.g., (user_id, time))
- The database query planner chooses the best index
Scalability: What if the transaction table has billions of rows?
- Sharding by user_id for user-specific queries
- Time-based partitioning for range queries
- Caching frequently accessed pages

Complexity Summary

Operation	Time (In-Memory)	Time (DB + Index)	Space
`set_*`	O(1)	O(1)	O(1)
`execute`	O(N)	O(log N + R)	O(R)
`fetch_page`	O(cursor + P)	O(log N + P)	O(P)

Where N = total transactions, R = matching results, P = page size.