Design payment scheduler with cancel and top-K outgoing
Company: Circle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
Quick Answer: This question evaluates knowledge of designing stateful in-memory services, efficient data structures and algorithms for scheduled task execution and top‑K outgoing aggregation, and correctness in handling cancellation, failure semantics, and related edge cases.
Constraints
- 0 <= len(balances) <= 2 * 10^5
- 0 <= len(operations) <= 2 * 10^5
- Account IDs are positive integers
- Initial balances are non-negative integers
- 1 <= amount <= 10^9
- 0 <= executeAt, now <= 10^9
- 0 <= k <= 2 * 10^5
Examples
Input: ({1: 100, 2: 50, 3: 0}, [('schedule', 1, 2, 70, 10), ('schedule', 1, 3, 40, 5), ('schedule', 2, 3, 60, 5), ('cancel', 1), ('process', 5), ('topk', 2), ('remove', 3), ('process', 10), ('cancel', 1), ('topk', 3)])
Expected Output: [1, 2, 3, True, 2, [1], True, 0, False, [1]]
Explanation: Payment 1 is canceled before execution. At time 5, payment 2 succeeds and payment 3 fails due to insufficient funds. Only account 1 has successful outgoing total, failed payment 3 can be removed, and the canceled payment is skipped later.
Input: ({1: 100, 2: 0, 3: 0, 4: 0}, [('schedule', 1, 2, 50, 7), ('schedule', 1, 3, 50, 7), ('schedule', 1, 4, 10, 7), ('process', 7), ('topk', 3), ('cancel', 2), ('remove', 2)])
Expected Output: [1, 2, 3, 3, [1], False, False]
Explanation: All three payments are due at the same time, so they are processed by paymentId order: 1, 2, then 3. The first two succeed and use up all funds; the third fails. A successful payment cannot be canceled or removed.
Input: ({1: 100, 2: 100, 3: 0, 4: 0}, [('schedule', 1, 3, 40, 1), ('schedule', 2, 4, 40, 1), ('process', 1), ('topk', 2)])
Expected Output: [1, 2, 2, [1, 2]]
Explanation: Accounts 1 and 2 each end with outgoing total 40. Because totals tie, the smaller account ID comes first.
Input: ({}, [('schedule', 5, 6, 10, 3), ('cancel', 1), ('cancel', 1), ('process', 5), ('remove', 1), ('remove', 1), ('topk', 2)])
Expected Output: [1, True, False, 0, True, False, []]
Explanation: The payment is canceled, so it is never executed. Repeated cancellation fails, removing it once succeeds, removing it again fails because it no longer exists, and no successful outgoing payments means an empty top-k list.
Input: ({1: 50, 2: 0, 3: 0}, [('schedule', 1, 2, 50, 1), ('schedule', 2, 3, 30, 2), ('process', 1), ('process', 2), ('topk', 2)])
Expected Output: [1, 2, 1, 1, [1, 2]]
Explanation: Payment 1 succeeds, so account 2 receives funds. Later, account 2 has enough balance for payment 2 to succeed. Outgoing totals are 50 for account 1 and 30 for account 2.
Solution
def solution(balances, operations):
import heapq
from collections import defaultdict
bal = dict(balances)
payments = {}
due_heap = []
outgoing = defaultdict(int)
top_heap = []
next_payment_id = 1
results = []
def ensure_account(account_id):
if account_id not in bal:
bal[account_id] = 0
for op in operations:
kind = op[0]
if kind == 'schedule':
_, payer_id, payee_id, amount, execute_at = op
ensure_account(payer_id)
ensure_account(payee_id)
payment_id = next_payment_id
next_payment_id += 1
payments[payment_id] = {
'payer': payer_id,
'payee': payee_id,
'amount': amount,
'execute_at': execute_at,
'status': 'PENDING'
}
heapq.heappush(due_heap, (execute_at, payment_id))
results.append(payment_id)
elif kind == 'cancel':
_, payment_id = op
payment = payments.get(payment_id)
if payment is not None and payment['status'] == 'PENDING':
payment['status'] = 'CANCELED'
results.append(True)
else:
results.append(False)
elif kind == 'remove':
_, payment_id = op
payment = payments.get(payment_id)
if payment is not None and payment['status'] in ('CANCELED', 'FAILED'):
del payments[payment_id]
results.append(True)
else:
results.append(False)
elif kind == 'process':
_, now = op
processed_count = 0
while due_heap and due_heap[0][0] <= now:
_, payment_id = heapq.heappop(due_heap)
payment = payments.get(payment_id)
if payment is None or payment['status'] != 'PENDING':
continue
payer_id = payment['payer']
payee_id = payment['payee']
amount = payment['amount']
if bal.get(payer_id, 0) >= amount:
bal[payer_id] -= amount
bal[payee_id] = bal.get(payee_id, 0) + amount
payment['status'] = 'SUCCESS'
outgoing[payer_id] += amount
heapq.heappush(top_heap, (-outgoing[payer_id], payer_id))
else:
payment['status'] = 'FAILED'
processed_count += 1
results.append(processed_count)
elif kind == 'topk':
_, k = op
if k <= 0:
results.append([])
continue
chosen_entries = []
used_accounts = set()
while top_heap and len(chosen_entries) < k:
neg_total, account_id = heapq.heappop(top_heap)
current_total = outgoing.get(account_id, 0)
if current_total == 0:
continue
if -neg_total != current_total:
continue
if account_id in used_accounts:
continue
chosen_entries.append((neg_total, account_id))
used_accounts.add(account_id)
answer = [account_id for _, account_id in chosen_entries]
for entry in chosen_entries:
heapq.heappush(top_heap, entry)
results.append(answer)
else:
raise ValueError('Unknown operation: ' + str(kind))
return results
Time complexity: schedule: O(log P), cancel: O(1), remove: O(1), process: O(r log P) for r due-heap entries popped in that call, topk: amortized O((k + s) log A) where s is the number of stale top-heap entries discarded and A is the number of accounts with positive outgoing totals. Space complexity: O(P + U), where P is the number of scheduled payments stored across the map/heaps and U is the number of distinct accounts seen.
Hints
- Store each payment by paymentId in a hash map so cancel, remove, and status checks are O(1).
- A min-heap ordered by (executeAt, paymentId) is useful for due payments. For top-k outgoing totals, consider a max-heap with lazy deletion because totals only increase after successful payments.