Implement paginated retrieval of transactions

Given a large list of transaction records (id, userId, amount, createdAt), implement APIs to return transactions in reverse chronological order with pagination. Support both offset-based and cursor-based (createdAt,id) pagination; return page data plus metadata (hasNext, nextCursor, total if offset mode). Ensure stable ordering when multiple transactions share the same timestamp, and discuss how to keep results consistent when new records arrive between requests. Provide time/space complexities and key edge cases.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Paginated Retrieval of Transactions (Offset + Cursor)

You are given a list of transaction records, each represented as [id, userId, amount, createdAt] where id and userId are integers, amount is a number, and createdAt is an integer epoch timestamp. Return one page of transactions in reverse chronological order with stable tie-breaking, supporting two pagination modes.

Implement paginate(transactions, mode, params, pageSize):

• Sort order: primary key createdAt DESCENDING, secondary key id DESCENDING. This guarantees a total (stable) order even when several transactions share the same createdAt.

• Offset mode (mode == "offset"): params is an integer offset (treat negative as 0). Return the slice [offset, offset + pageSize) of the sorted list, plus metadata.

  • hasNext = offset + pageSize < total.
  • nextCursor = [createdAt, id] of the last row on the returned page, or null if the page is empty.
  • total = total number of transactions.

• Cursor mode (mode == "cursor"): params is either null (start from the beginning) or a cursor [createdAt, id]. Return up to pageSize rows that come strictly after the cursor in the sort order — i.e. rows whose (createdAt, id) is lexicographically less than (cursorCreatedAt, cursorId) in the DESC ordering.

  • hasNext = there is at least one row beyond this page (start + pageSize < total).
  • nextCursor = [createdAt, id] of the last row on the page only when hasNext is true; otherwise null (no cursor to hand back when the stream is exhausted).
  • total = null (cursor pagination does not compute a total).

Return a map/object with keys page, hasNext, nextCursor, total (page is the list of selected records in sorted order).

Also be ready to discuss consistency when new records arrive between requests: cursor pagination on (createdAt, id) is insertion-stable for already-seen pages (new rows with a larger createdAt appear only at the front and never shift the cursor window), whereas offset pagination can skip or duplicate rows as the underlying list grows.

Constraints

• 0 <= number of transactions <= 10^6
• Each record is [id, userId, amount, createdAt]; id values are unique integers
• createdAt is an integer timestamp; multiple records may share the same createdAt
• 1 <= pageSize
• mode is either "offset" or "cursor"
• offset >= 0 (negative offsets are clamped to 0); cursor is null or [createdAt, id]

Examples

Example 1

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'offset', 0, 2)
Output: {'page': [[2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'hasNext': True, 'nextCursor': [150, 3], 'total': 3}

Explanation: Offset mode, first page of 2. Sorted by createdAt DESC: 200, 150, 100. Returns the top two; hasNext true (1 row remains); nextCursor is the last row's (createdAt, id).

Example 2

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'offset', 2, 2)
Output: {'page': [[1, 10, 5.0, 100]], 'hasNext': False, 'nextCursor': [100, 1], 'total': 3}

Explanation: Offset mode, last partial page (offset 2). Only 1 row left; hasNext false since 2 + 2 >= 3.

Hints

1. Define a single total order: createdAt DESC, then id DESC. The id tiebreak is what makes pagination stable across equal timestamps.
2. In cursor mode, 'strictly after the cursor' means the first row whose (createdAt, id) tuple is lexicographically less than the cursor tuple under DESC ordering — compare the pair, not just createdAt.
3. Only emit nextCursor in cursor mode when hasNext is true; once the stream is exhausted, return null so the caller knows to stop.
4. Cursor pagination is resilient to inserts between requests because the (createdAt, id) anchor doesn't move; offset pagination can skip or repeat rows when new records arrive.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given a large list of transaction records (id, userId, amount, createdAt), implement APIs to return transactions in reverse chronological order with pagination. Support both offset-based and cursor-based (createdAt,id) pagination; return page data plus metadata (hasNext, nextCursor, total if offset mode). Ensure stable ordering when multiple transactions share the same timestamp, and discuss how to keep results consistent when new records arrive between requests. Provide time/space complexities and key edge cases.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.