Paginate forward and backward through results
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are asked to extend a basic pagination system to support **forward** and **backward** navigation, similar to a cursor-based API.
You are given:
- A zero-indexed array of items `items` sorted in a fixed, deterministic order.
- An integer `pageSize > 0`.
Design a paginator with the following operations:
1. `getFirstPage()` → returns the first `pageSize` items and a **cursor** representing the position after the last returned item.
2. `getNextPage(cursor)` → given a cursor returned by a previous call, return the next `pageSize` items and a new cursor. If there are no more items, return an empty list and a special "end" cursor.
3. `getPrevPage(cursor)` → given a cursor, return the **previous** page of `pageSize` items and a new cursor pointing to the start of that page. If there is no previous page, return an empty list and a "start" cursor.
Requirements:
- Define what the cursor contains (it could just be an index or a more complex token).
- All operations should run in **O(pageSize)** time.
- Handle edge cases correctly, including:
- Moving past the last page with `getNextPage`.
- Moving before the first page with `getPrevPage`.
- Cases where `len(items)` is not a multiple of `pageSize`.
Implement the data structure and its methods with clear handling of indices and cursors.
Quick Answer: This question evaluates understanding of pagination mechanics, cursor/token design, array indexing, and state management for bidirectional (forward and backward) navigation.
Implement solution(items, page_size, operations). A cursor is the integer index after the last item returned by a page. Operations are ["first"], ["next", cursor], and ["prev", cursor]. Return [page_items, new_cursor] for each operation.
Constraints
- page_size > 0
- items are already sorted in deterministic order
Examples
Input: (['a', 'b', 'c', 'd', 'e'], 2, [['first'], ['next', 2], ['next', 4], ['next', 5], ['prev', 5], ['prev', 1], ['prev', 0]])
Expected Output: [[['a', 'b'], 2], [['c', 'd'], 4], [['e'], 5], [[], 5], [['d', 'e'], 3], [['a'], 0], [[], 0]]
Input: ([1, 2, 3], 5, [['first'], ['next', 3], ['prev', 3]])
Expected Output: [[[1, 2, 3], 3], [[], 3], [[1, 2, 3], 0]]
Hints
- Use the cursor as an array boundary.
- Clamp invalid cursors into [0, len(items)].