PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part question evaluates stateful system design, ordered event processing and scheduling semantics for an in-memory banking command processor, combinatorial optimization and capacity-constrained selection for the 0/1 knapsack transaction packing, and API/interface design for pagination over in-memory collections.

  • hard
  • Coinbase
  • Coding & Algorithms
  • Software Engineer

Implement banking, knapsack, and pagination tasks

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

## Problem A — Banking system command processor Implement an in-memory banking system that processes a sequence of commands in timestamp order. ### Entities - **Account** identified by a unique string `accountId`. - **Balance** is a non-negative integer amount. ### Commands (examples shown; you may define an equivalent input format) 1. `CREATE accountId` - Create a new account with balance 0. - If the account already exists, the command should be handled deterministically (e.g., ignore or error). 2. `DEPOSIT accountId amount` - Add `amount` to the account. 3. `TRANSFER fromId toId amount` - Move funds from `fromId` to `toId` if sufficient funds exist. 4. `TOP_SPENDERS k` - Return the top `k` accounts ranked by **total outgoing spend** (e.g., sum of successful `TRANSFER` amounts sent by the account). Define deterministic tie-breaking (e.g., by `accountId`). 5. `SCHEDULE_PAYMENT fromId toId amount executeAt` - Schedule a delayed transfer to run at time `executeAt`. - Scheduled payments should execute automatically at/after their scheduled time when processing later commands. 6. `CANCEL_PAYMENT paymentId` - Cancel a previously scheduled payment if it has not executed. 7. `MERGE targetId sourceId` - Merge `sourceId` into `targetId`: - `targetId` receives `sourceId`’s remaining balance. - Define what happens to scheduled payments involving `sourceId` (e.g., re-point to `targetId`, or cancel), and ensure the behavior is consistent. 8. `BALANCE accountId` - Output the current balance. ### Output Return outputs for query-like commands (e.g., `TOP_SPENDERS`, `BALANCE`, possibly errors) in the order encountered. ### Notes / constraints - Assume up to large numbers of commands; aim for efficient data structures. - Clearly define edge-case behavior (invalid accounts, negative amounts, cancel-after-execute, merge semantics, etc.). --- ## Problem B — Max-fee transaction packing (0/1 knapsack) You are given `N` transactions, each with: - `id` (unique identifier) - `size` (positive integer) - `fee` (non-negative integer) You have a fixed **block size limit of 100** (i.e., total size of chosen transactions must be `<= 100`). ### Task Choose a subset of transactions to **maximize total fee**. ### Output - Return the maximum achievable total fee. - If required, also return one optimal chosen set of `id`s with a deterministic tie-break rule (e.g., smallest number of transactions; then lexicographically smallest list of ids). --- ## Problem C — Design and implement a pagination utility Design an interface and implement a pagination helper over an in-memory collection. ### Requirements - Input: a list/array of items (you can assume strings or objects with `id`). - Support `pageSize` and returning items page-by-page. - Your design should specify function/class signatures (e.g., `getPage(pageNumber)`, or cursor-based `next(cursor)` returning `(items, nextCursor)`), including inputs/outputs. ### Constraints / considerations - Handle edge cases (empty list, last page, invalid page token). - Discuss tradeoffs between offset-based pagination and cursor-based pagination. - If you choose cursor-based pagination, define how the cursor is generated and validated.

Quick Answer: This multi-part question evaluates stateful system design, ordered event processing and scheduling semantics for an in-memory banking command processor, combinatorial optimization and capacity-constrained selection for the 0/1 knapsack transaction packing, and API/interface design for pagination over in-memory collections.

Banking System Command Processor

Implement an in-memory banking system that processes a sequence of commands in timestamp order. Each command is a list `[timestamp, op, *args]`, processed in the given order. The supported operations are: - `CREATE accountId` — create an account with balance 0. If it already exists, ignore. - `DEPOSIT accountId amount` — add `amount` to the account (ignored if the account does not exist or `amount < 0`). - `TRANSFER fromId toId amount` — move funds from `fromId` to `toId` if both accounts exist and `fromId` has sufficient balance. Successful transfers count toward the sender's total outgoing spend. - `TOP_SPENDERS k` — return a list of up to `k` accountIds ranked by total outgoing spend (descending), tie-broken by accountId (ascending). Accounts with zero spend are excluded. - `SCHEDULE_PAYMENT fromId toId amount executeAt` — schedule a delayed transfer. Returns a deterministic paymentId (`p1`, `p2`, ... assigned in schedule order). Scheduled payments execute lazily: before processing each command, every pending payment with `executeAt <= currentTimestamp` runs in `(executeAt, paymentId)` order. - `CANCEL_PAYMENT paymentId` — cancel a payment that has not yet executed or been cancelled. Returns `True` if cancelled, else `False`. - `MERGE targetId sourceId` — move `sourceId`'s balance and spend into `targetId`, re-point any pending scheduled payments referencing `sourceId` to `targetId`, then delete `sourceId`. - `BALANCE accountId` — return the current balance, or `None` if the account does not exist. Return a list of outputs for the query-like commands (`TOP_SPENDERS`, `SCHEDULE_PAYMENT`, `CANCEL_PAYMENT`, `BALANCE`) in the order encountered.

Constraints

  • Balances are non-negative integers.
  • A TRANSFER only succeeds if both accounts exist and the sender has sufficient funds.
  • TOP_SPENDERS ranks by total successful outgoing transfer amount, descending, tie-broken by accountId ascending; zero-spend accounts are excluded.
  • Scheduled payments execute at the first command whose timestamp is >= executeAt, in (executeAt, paymentId) order.
  • MERGE re-points pending scheduled payments from source to target and deletes the source account.

Examples

Input: [[1, 'CREATE', 'alice'], [2, 'CREATE', 'bob'], [3, 'DEPOSIT', 'alice', 100], [4, 'TRANSFER', 'alice', 'bob', 30], [5, 'BALANCE', 'alice'], [6, 'BALANCE', 'bob']]

Expected Output: [70, 30]

Explanation: Alice deposits 100, transfers 30 to Bob, leaving 70; Bob has 30.

Input: [[1, 'CREATE', 'a'], [1, 'CREATE', 'b'], [1, 'CREATE', 'c'], [2, 'DEPOSIT', 'a', 100], [2, 'DEPOSIT', 'b', 100], [3, 'TRANSFER', 'a', 'c', 50], [4, 'TRANSFER', 'a', 'c', 10], [5, 'TRANSFER', 'b', 'c', 40], [6, 'TOP_SPENDERS', 2]]

Expected Output: [['a', 'b']]

Explanation: a spends 60, b spends 40, c spends 0; top 2 spenders are a then b.

Input: [[1, 'CREATE', 'a'], [1, 'CREATE', 'b'], [2, 'DEPOSIT', 'a', 50], [3, 'SCHEDULE_PAYMENT', 'a', 'b', 20, 10], [5, 'BALANCE', 'b'], [12, 'BALANCE', 'b'], [13, 'BALANCE', 'a']]

Expected Output: ['p1', 0, 20, 30]

Explanation: Payment p1 is scheduled for t=10. At t=5 it hasn't run (b=0); by t=12 it has (b=20, a=30).

Input: [[1, 'CREATE', 'a'], [1, 'CREATE', 'b'], [2, 'DEPOSIT', 'a', 50], [3, 'SCHEDULE_PAYMENT', 'a', 'b', 20, 10], [4, 'CANCEL_PAYMENT', 'p1'], [12, 'BALANCE', 'b'], [12, 'BALANCE', 'a']]

Expected Output: ['p1', True, 0, 50]

Explanation: p1 is cancelled before its execute time, so no funds move.

Input: [[1, 'CREATE', 'a'], [1, 'CREATE', 'b'], [2, 'DEPOSIT', 'a', 30], [3, 'DEPOSIT', 'b', 20], [4, 'MERGE', 'a', 'b'], [5, 'BALANCE', 'a'], [6, 'BALANCE', 'b']]

Expected Output: [50, null]

Explanation: Merging b into a moves b's 20 into a (now 50) and deletes b, so b's balance is None.

Input: [[1, 'TRANSFER', 'x', 'y', 10], [2, 'BALANCE', 'x']]

Expected Output: [null]

Explanation: Transfer against non-existent accounts is a no-op; x still does not exist.

Input: [[1, 'CREATE', 'a'], [2, 'DEPOSIT', 'a', 10], [3, 'TRANSFER', 'a', 'a', 5], [4, 'BALANCE', 'a'], [5, 'TOP_SPENDERS', 3]]

Expected Output: [10, ['a']]

Explanation: A self-transfer leaves the balance unchanged at 10 but still counts 5 toward outgoing spend, so a appears in TOP_SPENDERS.

Input: []

Expected Output: []

Explanation: No commands produce no outputs.

Hints

  1. Use a hash map for balances and a separate hash map for cumulative outgoing spend so TOP_SPENDERS is a simple sort.
  2. Process scheduled payments lazily: before handling each command, sweep any pending payment whose executeAt has passed.
  3. Assign payment IDs deterministically (p1, p2, ...) so CANCEL_PAYMENT and tie-breaking are reproducible.
  4. For MERGE, remember to fold the source's spend into the target and re-point any still-pending scheduled payments.

Max-Fee Transaction Packing (0/1 Knapsack)

You are given `N` transactions, each described by `[id, size, fee]` where `size` is a positive integer and `fee` is a non-negative integer. You have a fixed block-size limit (capacity), and the total size of the chosen transactions must be `<= capacity`. Choose a subset of transactions to **maximize the total fee** and return that maximum achievable total fee. This is a classic 0/1 knapsack: each transaction is either fully included or excluded. Note: the original Coinbase prompt fixes the block size at 100; here the capacity is passed as a parameter so the solution generalizes.

Constraints

  • Each size is a positive integer; each fee is a non-negative integer.
  • Total size of chosen transactions must be <= the block-size capacity.
  • Each transaction may be chosen at most once (0/1 knapsack).
  • Greedy by fee/size ratio is NOT correct here — the bounded capacity requires DP.

Examples

Input: [['a', 30, 50], ['b', 50, 60], ['c', 20, 30], ['d', 40, 40]], 100

Expected Output: 140

Explanation: Choosing a(30)+c(20)+d(40)=90 size for fee 50+30+40=120, or a+b+c=100 size for 50+60+30=140 — the latter exactly fills capacity 100 for the max fee.

Input: [['x', 60, 100], ['y', 60, 90]], 100

Expected Output: 100

Explanation: Both items together exceed capacity 100, so only one fits; the higher fee (100) is chosen.

Input: [], 100

Expected Output: 0

Explanation: No transactions means zero fee.

Input: [['only', 150, 999]], 100

Expected Output: 0

Explanation: The single item's size 150 exceeds capacity 100, so nothing can be packed.

Input: [['a', 1, 0], ['b', 1, 0]], 100

Expected Output: 0

Explanation: All fees are zero, so the maximum fee is zero regardless of selection.

Input: [['a', 100, 10], ['b', 50, 7], ['c', 50, 7]], 100

Expected Output: 14

Explanation: Taking b+c (size 100, fee 14) beats taking a alone (size 100, fee 10).

Hints

  1. This is a 0/1 knapsack: weight = size, value = fee, capacity = block size.
  2. Use a 1-D DP array indexed by remaining capacity, iterating capacity from high to low so each item is used at most once.
  3. The answer is the maximum over all capacities (a partially filled block can still be optimal).
  4. Skip any transaction whose size already exceeds the capacity.

Pagination Utility (Offset-Based getPage)

Design and implement a pagination helper over an in-memory collection. The original interview left the interface open; here it is made concrete as an offset-based `getPage` function. Given `items` (a list), `page_size` (items per page, >= 1), and `page_number` (1-indexed), return the list of items on that page. Edge cases to handle: - Empty list → return `[]`. - The last page may be partial → return only the remaining items. - A page number beyond the end → return `[]`. - Invalid input (`page_size < 1` or `page_number < 1`) → return `[]`. Tradeoff note: offset-based pagination (used here) is simple and supports random page access but can skip/duplicate items if the underlying collection mutates between requests; cursor-based pagination is stable under inserts/deletes but only supports sequential traversal.

Constraints

  • page_number is 1-indexed.
  • page_size must be >= 1; otherwise return [].
  • Pages beyond the end of the collection return [].
  • The last page may contain fewer than page_size items.

Examples

Input: ['a', 'b', 'c', 'd', 'e'], 2, 1

Expected Output: ['a', 'b']

Explanation: Page 1 with size 2 returns the first two items.

Input: ['a', 'b', 'c', 'd', 'e'], 2, 3

Expected Output: ['e']

Explanation: Page 3 starts at offset 4 and only one item remains (the partial last page).

Input: ['a', 'b', 'c', 'd', 'e'], 2, 4

Expected Output: []

Explanation: Page 4 starts at offset 6, which is beyond the list, so it is empty.

Input: [], 3, 1

Expected Output: []

Explanation: An empty collection yields an empty page.

Input: ['a', 'b', 'c'], 5, 1

Expected Output: ['a', 'b', 'c']

Explanation: When page_size exceeds the list length, the whole list fits on page 1.

Input: ['a', 'b', 'c'], 0, 1

Expected Output: []

Explanation: A page_size of 0 is invalid, so the function returns [].

Input: ['a', 'b', 'c'], 2, 0

Expected Output: []

Explanation: A page_number of 0 is invalid (pages are 1-indexed), so the function returns [].

Input: [10, 20, 30, 40], 1, 3

Expected Output: [30]

Explanation: With page_size 1, page 3 returns the third item.

Hints

  1. Compute the start offset as (page_number - 1) * page_size.
  2. Guard invalid inputs (page_size < 1 or page_number < 1) before slicing.
  3. If the start offset is at or past the end of the list, the page is empty.
  4. Slicing naturally handles the partial last page — no special-casing needed.
Last updated: Jun 28, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement a Coin-Constrained Jump Strategy - Coinbase (hard)
  • Implement an In-Memory Database - Coinbase (hard)
  • Implement Game Physics and Block Mining - Coinbase (hard)
  • Compute Total Manual Distance - Coinbase (medium)
  • Implement a Flappy Bird Jump Agent - Coinbase