Search Results Pagination: Implement Cursor-Based Pagination for a Search API

Question

## Problem

You are implementing pagination for a search endpoint. Given a sorted list of results and a cursor (an opaque token encoding the last seen position), return the next page of results and the next cursor. The cursor should be stable even if new items are inserted.

```python
def paginate(results: list[dict], cursor: str | None, page_size: int) -> dict:
    # returns {"items": [...], "next_cursor": str | None}
    pass

def encode_cursor(item_id: str) -> str: ...
def decode_cursor(cursor: str) -> str: ...  # returns item_id
```

**Example:**
```
results (sorted by score desc, then id asc):
  [{id:"a",score:10}, {id:"b",score:8}, {id:"c",score:7}, {id:"d",score:5}]

paginate(results, cursor=None, page_size=2)
-> {items: [{id:"a",...},{id:"b",...}], next_cursor: encode("b")}

paginate(results, cursor=encode("b"), page_size=2)
-> {items: [{id:"c",...},{id:"d",...}], next_cursor: null}
```

## Follow-ups

1. Why is cursor-based pagination preferred over offset-based for large datasets?
2. What happens to your cursor if the item it points to is deleted between pages?
3. How would you implement bidirectional pagination (previous page support)?
4. How would you design the cursor to be tamper-proof (signed token)?

Search Results Pagination: Implement Cursor-Based Pagination for a Search API

Question Details

Full Details

Topics

More from Airbnb