Schedule and cancel delayed payments
Company: Meta
Role: Software Engineer
Category: System Design
Difficulty: medium
Interview Round: Online Assessment
##### Question
Extend an existing in-memory payment system (immediate `transfer`s between accounts, plus a top-N spenders/payers leaderboard) with **scheduled payments** that execute after a delay, and the ability to cancel them before they run.
Implement the following:
1. **Schedule a payment.** `String schedulePayment(long timestamp, String sourceAccountId, String targetAccountId, int amount, long delay)` records a future payment that becomes due at `timestamp + delay` and returns a unique `paymentId` (a.k.a. `scheduleId`).
2. **Cancel a scheduled payment.** Support cancellation of a not-yet-executed payment, returning a boolean indicating success. Handle both forms the interviewer may ask for:
- `boolean cancel(String paymentId)` — cancel by id alone.
- `boolean cancelScheduledPayment(long timestamp, String accountId, String scheduleId)` — cancel with an authorization check that `accountId` matches the payment's `sourceAccountId`.
- Cancels must be **idempotent**: only the first successful `PENDING -> CANCELED` transition returns `true`; repeat calls (or calls on an already-executed/canceled payment) return `false`.
3. **Run due payments in chronological order.** Provide a runner, e.g. `String runDue(long now)` / `String processDuePayments(long now)`, that executes every payment whose due time is `<= now`, strictly in chronological (due-time) order, and returns a **string summary of the execution sequence**. Decide and state a deterministic tie-breaker for payments with the same due time (e.g. insertion order via a sequence number). Two summary formats appear in practice — be ready to produce either:
- concatenate the affected account ids in execution order (e.g. two payments `S1->T1` then `S2->T2` yields `"S1T1S2T2"` or comma-separated), and/or
- concatenate `"{sourceAccountId}{amount}"` per executed payment (e.g. `"C20A10"`).
4. **Pending-store data structures.** Manage pending items with **maps, not lists**, for efficient O(1) lookup and cancel. A typical design pairs a hash map `byId` (for cancel/lookup) with a time-ordered structure for chronological execution — either a min-heap keyed by due time, or a navigable/ordered map keyed by due time. Justify your choice and analyze the time complexity of each operation.
5. **Funds-reservation policy.** Specify **when funds are reserved**: at schedule time (place a hold) versus at execution time. Discuss the trade-offs (no long-term balance locking and better UX for long delays vs. the risk that execution fails on insufficient funds) and state which you implement.
6. **Failure / insufficient-funds handling.** Define what happens when the source has insufficient funds at execution time (e.g. mark the payment `FAILED`, apply no balance change, and exclude it from the summary). State your retry/overdraft policy, if any.
7. **Leaderboard integration.** Executed scheduled payments count as outgoing spend and must update the existing **top-N spenders/payers** structure for the source account — treat them exactly like immediate transfers, and update the balance and the leaderboard atomically so spend is never double-counted.
8. **Concurrency, idempotency, and clock assumptions.** State your time-source and concurrency assumptions and make `runDue`/`processDuePayments` safe to re-invoke: each payment must transition through execution at most once (e.g. via per-payment CAS/state machine), and cancel-vs-execute races must resolve deterministically.
Analyze the time and space complexity of `schedulePayment`, `cancel`/`cancelScheduledPayment`, and the runner.
Overview: Meta software-engineer system-design take-home: extend an in-memory payment system with scheduled (delayed) payments that execute after a delay, can be canceled, and run in chronological order returning a string execution summary. It tests maps-based pending stores (byId hash map + min-heap or navigable map by due time), funds-reservation timing, insufficient-funds and idempotent-cancel handling, concurrency/idempotency of the runner, and atomic top-N spenders updates.