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

What role is this question designed for?

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

Build an Account Transfer Ledger | Stripe Coding Question

Quick Overview

This question evaluates the ability to implement transaction processing, state management, validation of transfers (including rejects and platform lending), and reasoning about algorithmic time and space efficiency for maintaining account balances and borrowed totals.

Build an Account Transfer Ledger

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement a transaction processor for a payment platform. You are given a list of transaction records. Each record contains: - `id`: unique transaction identifier - `timestamp`: integer time value - `type`: either `deposit` or `transfer` - `from_account`: sender account for transfers, otherwise empty - `to_account`: receiver account - `amount`: positive integer All account balances start at `0`. Process transactions in increasing order of `timestamp`. If multiple transactions have the same timestamp, preserve their original input order. Your task has three parts: 1. **Compute balances** - A `deposit` adds `amount` to `to_account`. - A `transfer` moves `amount` from `from_account` to `to_account`. Return the final balance of every account. 2. **Reject invalid transfers** - Before applying a `transfer`, check whether `from_account` has enough balance. - If not, reject that transfer and leave all balances unchanged for that record. Return the final balances and the list of rejected transaction ids. 3. **Allow platform loans** - Extend part 2 with a platform lending feature. - If a transfer would fail because the sender is short by `d`, the platform may automatically lend exactly `d` to that sender, and then the transfer proceeds. - Track the total amount borrowed by each account. Return final balances and per-account borrowed totals. Discuss the expected time and space complexity of your approach.

Quick Answer: This question evaluates the ability to implement transaction processing, state management, validation of transfers (including rejects and platform lending), and reasoning about algorithmic time and space efficiency for maintaining account balances and borrowed totals.

Part 1: Compute Final Account Balances

You are building a transaction ledger for a payment platform. Each transaction record has an id, timestamp, type, from_account, to_account, and amount. All account balances start at 0. Process all transactions in increasing order of timestamp. If multiple transactions have the same timestamp, keep their original input order. Rules: - A deposit adds amount to to_account. - A transfer moves amount from from_account to to_account. - In this version, transfers are always applied, even if the sender becomes negative. Return the final balance of every account mentioned in the input.

Constraints

0 <= len(transactions) <= 200000
0 <= timestamp <= 10^9
1 <= amount <= 10^9
Each transaction id is unique
type is either "deposit" or "transfer"
For deposits, from_account is an empty string

Loading coding console...

Examples

Input: [{"id": "t1", "timestamp": 5, "type": "deposit", "from_account": "", "to_account": "A", "amount": 100}, {"id": "t2", "timestamp": 2, "type": "deposit", "from_account": "", "to_account": "B", "amount": 40}, {"id": "t3", "timestamp": 3, "type": "transfer", "from_account": "B", "to_account": "A", "amount": 15}, {"id": "t4", "timestamp": 5, "type": "transfer", "from_account": "A", "to_account": "C", "amount": 30}]

Expected Output: {"A": 85, "B": 25, "C": 30}

Explanation: Process in timestamp order: B gets 40, then B sends 15 to A, then A gets 100, then A sends 30 to C.

Input: [{"id": "t1", "timestamp": 1, "type": "transfer", "from_account": "A", "to_account": "B", "amount": 50}, {"id": "t2", "timestamp": 2, "type": "deposit", "from_account": "", "to_account": "A", "amount": 20}]

Expected Output: {"A": -30, "B": 50}

Explanation: Part 1 does not reject transfers, so A can go negative.

Input: []

Expected Output: {}

Explanation: Edge case: no transactions means no accounts and no balances.

Input: [{"id": "t1", "timestamp": 7, "type": "deposit", "from_account": "", "to_account": "Z", "amount": 7}]

Expected Output: {"Z": 7}

Explanation: Edge case: a single deposit creates one account with that balance.

Part 2: Reject Transfers with Insufficient Funds

You are given transaction records for a payment platform. Each record has an id, timestamp, type, from_account, to_account, and amount. All account balances start at 0. Process transactions in increasing order of timestamp. If multiple transactions have the same timestamp, preserve their original input order. Rules: - A deposit adds amount to to_account. - A transfer moves amount from from_account to to_account only if from_account currently has at least amount. - If a transfer does not have enough funds, reject it and leave all balances unchanged for that record. Return both the final balances and the list of rejected transaction ids in the order they were processed.

Constraints

0 <= len(transactions) <= 200000
0 <= timestamp <= 10^9
1 <= amount <= 10^9
Each transaction id is unique
type is either "deposit" or "transfer"
For deposits, from_account is an empty string

Examples

Input: [{"id": "t1", "timestamp": 1, "type": "deposit", "from_account": "", "to_account": "A", "amount": 100}, {"id": "t2", "timestamp": 2, "type": "transfer", "from_account": "A", "to_account": "B", "amount": 70}, {"id": "t3", "timestamp": 3, "type": "transfer", "from_account": "A", "to_account": "C", "amount": 50}, {"id": "t4", "timestamp": 4, "type": "deposit", "from_account": "", "to_account": "C", "amount": 10}]

Expected Output: ({"A": 30, "B": 70, "C": 10}, ["t3"])

Explanation: After A sends 70 to B, A has 30 left. The next transfer of 50 from A is rejected.

Input: [{"id": "t1", "timestamp": 5, "type": "transfer", "from_account": "A", "to_account": "B", "amount": 10}, {"id": "t2", "timestamp": 5, "type": "deposit", "from_account": "", "to_account": "A", "amount": 10}]

Expected Output: ({"A": 10, "B": 0}, ["t1"])

Explanation: Same timestamp: the transfer is processed before the deposit because input order must be preserved.

Input: []

Expected Output: ({}, [])

Explanation: Edge case: no transactions.

Input: [{"id": "d1", "timestamp": 1, "type": "deposit", "from_account": "", "to_account": "X", "amount": 5}, {"id": "tr1", "timestamp": 2, "type": "transfer", "from_account": "X", "to_account": "Y", "amount": 5}]

Expected Output: ({"X": 0, "Y": 5}, [])

Explanation: A valid transfer is applied normally, so there are no rejected ids.

Hints

The only new logic compared with Part 1 is the conditional check before applying a transfer.
Even if a transfer is rejected, its accounts should still appear in the output balances if they were mentioned in the input.

Part 3: Auto-Lend Missing Transfer Amounts

You are given transaction records for a payment platform. Each record has an id, timestamp, type, from_account, to_account, and amount. All account balances start at 0. Process transactions in increasing order of timestamp. If multiple transactions have the same timestamp, preserve their original input order. Rules: - A deposit adds amount to to_account. - A transfer normally moves amount from from_account to to_account. - If a transfer would fail because from_account is short by d, the platform automatically lends exactly d to from_account, and then the transfer succeeds. - Track the total amount borrowed by each account across all transfers. Return the final balances and the per-account borrowed totals.

Constraints

0 <= len(transactions) <= 200000
0 <= timestamp <= 10^9
1 <= amount <= 10^9
Each transaction id is unique
type is either "deposit" or "transfer"
For deposits, from_account is an empty string

Examples

Input: [{"id": "t1", "timestamp": 1, "type": "deposit", "from_account": "", "to_account": "A", "amount": 50}, {"id": "t2", "timestamp": 2, "type": "transfer", "from_account": "A", "to_account": "B", "amount": 80}, {"id": "t3", "timestamp": 3, "type": "transfer", "from_account": "B", "to_account": "C", "amount": 60}]

Expected Output: ({"A": 0, "B": 20, "C": 60}, {"A": 30, "B": 0, "C": 0})

Explanation: A is short by 30 when sending 80, so the platform lends 30. B later has enough to send 60 to C without borrowing.

Input: [{"id": "t1", "timestamp": 1, "type": "transfer", "from_account": "A", "to_account": "B", "amount": 10}, {"id": "t2", "timestamp": 2, "type": "deposit", "from_account": "", "to_account": "A", "amount": 3}, {"id": "t3", "timestamp": 3, "type": "transfer", "from_account": "A", "to_account": "C", "amount": 5}]

Expected Output: ({"A": 0, "B": 10, "C": 5}, {"A": 12, "B": 0, "C": 0})

Explanation: A borrows 10 for the first transfer, then later borrows 2 more for the second transfer, for a total of 12.

Input: [{"id": "t1", "timestamp": 1, "type": "transfer", "from_account": "A", "to_account": "B", "amount": 5}, {"id": "t2", "timestamp": 1, "type": "transfer", "from_account": "B", "to_account": "C", "amount": 3}]

Expected Output: ({"A": 0, "B": 2, "C": 3}, {"A": 5, "B": 0, "C": 0})

Explanation: Same timestamp: the first transfer is processed first, giving B enough balance to send 3 in the second transfer.

Input: []

Expected Output: ({}, {})

Explanation: Edge case: no transactions means no balances and no borrowing.

Hints

For a transfer, if balance[from_account] < amount, the exact loan needed is amount - balance[from_account].
Borrowed totals accumulate over time and are separate from final balances.