Katkat

Implement a Contribution Ledger With Per-Rail Settlement Delays

StripeSoftware Engineer · Technical Screen

Last updated

Implement process_ledger(commands), an ordered ledger for a community funding platform where contributions arrive over different payment rails, each with its own settlement delay, cutoff time, and per-window contribution limit.

A community crowd-funding platform accepts contributions into member accounts over three payment rails: CARD, ACH, and WIRE. The rails differ in three independent ways: how many ticks after acceptance the funds settle, a cutoff tick-of-day that decides which settlement window a contribution falls into, and the maximum amount a rail will accept into one account within one window. Implement process_ledger(commands), which processes commands strictly in the order given and returns one string joining every query's result with commas.

There are three kinds of command, each starting with a tick (the ledger's current time when that command runs; commands arrive in non-decreasing tick order):

  • ("INIT", tick, account_id) — create a new account. Re-initializing an existing account_id produces "ERROR".
  • ("DEPOSIT", tick, account_id, rail, cents) — contribute cents into account_id via rail. A deposit to an unknown account produces "ERROR". A deposit that would push that rail's per-window total for that account over its limit produces "REJECTED" and does not count against anything. Otherwise it produces "ACCEPTED", counts against the window's limit immediately, and settles rail.settlement_delay ticks later.
  • ("QUERY", tick, account_id) — report "{settled_cents}/{accepted_cents}" for account_id: settled funds are those whose settlement tick has passed; accepted is the running total of every accepted deposit regardless of settlement. An unknown account produces "ERROR".

Rail policy (fixed for this exercise, write it as an explicit table rather than inline constants):

CARD: settlement_delay=0,  cutoff=24, window_length=24, limit_cents=20000   (per account, per window)
ACH:  settlement_delay=3,  cutoff=17, window_length=24, limit_cents=5000
WIRE: settlement_delay=1,  cutoff=12, window_length=24, limit_cents=500000

A rail's settlement window for a tick is tick // window_length, except a tick whose time-of-day (tick % window_length) is at or after cutoff belongs to the next window instead of the current one.

Example

INIT(0, 'alice')
DEPOSIT(1, 'alice', CARD, 1000)   -> ACCEPTED   (settles instantly: delay 0)
DEPOSIT(2, 'alice', ACH, 2000)    -> ACCEPTED   (settles at tick 5)
QUERY(3, 'alice')                 -> '1000/3000'
QUERY(5, 'alice')                 -> '3000/3000'   (ACH settles by tick 5)
DEPOSIT(6, 'alice', ACH, 4500)    -> REJECTED   (2000 + 4500 > 5000 ACH window limit)
QUERY(6, 'alice')                 -> '3000/3000'

process_ledger([...]) -> 'ACCEPTED,ACCEPTED,1000/3000,3000/3000,REJECTED,3000/3000'

Constraints

  • Up to 100,000 commands and 10,000 distinct accounts.
  • All amounts fit in a 64-bit integer; compute everything in integer cents.
  • A rejected deposit must not affect the window limit, the accepted total, or any pending settlement.

Hints

Hint 1

Separate the moment a deposit is accepted, the moment it starts counting against a limit, and the moment it settles — this problem exists because those three moments differ.

Hint 2

Settle any pending deposits whose time has come before answering a query or checking a new deposit's limit, so settled totals are never stale.

Hint 3

Compute the settlement window from the rail's cutoff before checking the limit — a deposit right at the cutoff belongs to the next window.

Hint 4

Keep the per-window running total per account per rail in its own map, separate from the account's overall accepted and settled totals.

Follow-up questions

  • How would you support a rail whose settlement delay depends on the deposit amount (e.g. large wires take longer)?
  • How would you report settled and pending amounts separately in a query, instead of just a combined accepted total?
  • How would you make the per-window limit configurable per account rather than fixed per rail?
  • If commands could arrive slightly out of timestamp order from different services, how would you change the design?