How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Lyft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Lyft during technical interviews.

Implement paginated retrieval of transactions

Quick Overview

Implement paginated retrieval of transactions evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Lyft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

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.

Quick Answer: Implement paginated retrieval of transactions evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'offset', 0, 2)

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

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'offset', 2, 2)

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

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 100], [3, 11, 2.0, 100]], 'offset', 0, 2)

Expected Output: {'page': [[3, 11, 2.0, 100], [2, 10, 7.0, 100]], 'hasNext': True, 'nextCursor': [100, 2], 'total': 3}

Explanation: All three share createdAt=100, so the id DESC tiebreak orders them 3, 2, 1. Demonstrates stable ordering on equal timestamps.

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'cursor', None, 2)

Expected Output: {'page': [[2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'hasNext': True, 'nextCursor': [150, 3], 'total': None}

Explanation: Cursor mode with a null cursor starts from the beginning; total is null in cursor mode.

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 200], [3, 11, 2.0, 150]], 'cursor', [150, 3], 2)

Expected Output: {'page': [[1, 10, 5.0, 100]], 'hasNext': False, 'nextCursor': None, 'total': None}

Explanation: Continuing from cursor [150, 3], the only row strictly after is [1,...,100]. Stream exhausted, so nextCursor is null.

Input: ([[1, 10, 5.0, 100], [2, 10, 7.0, 100], [3, 11, 2.0, 100]], 'cursor', [100, 3], 2)

Expected Output: {'page': [[2, 10, 7.0, 100], [1, 10, 5.0, 100]], 'hasNext': False, 'nextCursor': None, 'total': None}

Explanation: Cursor on a tied timestamp: [100, 3] excludes id 3 and returns id 2 then id 1 via the (createdAt, id) tuple comparison.

Input: ([], 'offset', 0, 5)

Expected Output: {'page': [], 'hasNext': False, 'nextCursor': None, 'total': 0}

Explanation: Empty input, offset mode: empty page, total 0, no cursor.

Input: ([], 'cursor', None, 5)

Expected Output: {'page': [], 'hasNext': False, 'nextCursor': None, 'total': None}

Explanation: Empty input, cursor mode: empty page, total null.

Input: ([[1, 10, 5.0, 100]], 'cursor', [100, 1], 3)

Expected Output: {'page': [], 'hasNext': False, 'nextCursor': None, 'total': None}

Explanation: Cursor points at the only row, so nothing is strictly after it — empty page, no further cursor.

Hints

Define a single total order: createdAt DESC, then id DESC. The id tiebreak is what makes pagination stable across equal timestamps.
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.
Only emit nextCursor in cursor mode when hasNext is true; once the stream is exhausted, return null so the caller knows to stop.
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.

Quick Overview