Airbnb·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Airbnb software engineering interview that went deep into system design for a financial ledger. The question had a lot of moving parts and I definitely underestimated how long the complexity analysis portion would take.

Questions Asked (1)

Design and implement a transaction ledger that processes a stream of payment and refund records. Each payment has an id, userId, amount, and timestamp. Each refund has the same fields plus an optional reference to a prior payment. You need to pick data structures, implement addPayment, addRefund (with a pluggable priority rule), and getUserBalance. Refunds without a payment reference should select which prior payments to offset based on a comparator (e.g. most recent first, largest amount first). Support partial and multiple refunds per payment, and for each refund return the list of (paymentId, refundedAmount) pairs it consumed. Then analyze time and space complexity for each operation.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This one hit me harder than expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and edge cases, then propose a data model that supports efficient lookups and updates. For refunds without a reference, use a pluggable comparator to select payments, and implement a greedy offsetting algorithm that returns consumed pairs. Finally, analyze time and space complexity for each operation, discussing trade-offs.

Pro tip: Demonstrate awareness of real-world constraints like concurrency, idempotency, and auditability; mention that in production you'd likely use a database with transactions and indexes, but for this exercise you'll focus on in-memory data structures.

1. Clarify requirements and edge cases

Ask about refund behavior: can refunds exceed payment amount? Are partial refunds allowed? What if no payments match? How to handle duplicate IDs? This shows thoroughness.

2. Design data structures

Propose using a hash map for payments by ID, and for each user, a list or priority queue of payments sorted by the comparator (e.g., most recent first). Also track refunds and remaining amounts per payment.

3. Implement addPayment and addRefund

addPayment inserts into maps and updates user's payment list. addRefund with reference directly offsets that payment; without reference, iterate through user's payments in comparator order, consuming amounts until refund is satisfied, collecting (paymentId, amount) pairs.

4. Implement getUserBalance

Compute balance as sum of remaining amounts of all payments for the user (or maintain a running balance updated on each operation).

5. Analyze complexity and trade-offs

Discuss time complexity: addPayment O(1) or O(log n) if maintaining sorted structure; addRefund O(k) where k is number of payments touched; getUserBalance O(1) if maintained. Space O(n + m). Mention alternative approaches like using a balanced BST or segment tree for better refund performance.

Key Points to Mention

Use of hash maps for O(1) payment lookup by ID.
Maintaining per-user payment lists sorted by the pluggable comparator (e.g., using a priority queue or sorted list).
Greedy algorithm for refund offsetting: always pick the next payment according to comparator until refund amount is exhausted.
Handling partial refunds by tracking remaining amount per payment and updating it.
Returning list of (paymentId, refundedAmount) pairs for each refund.
Complexity analysis: addPayment O(1), addRefund O(k log n) if using heap, getUserBalance O(1) with running total.
Trade-offs: maintaining sorted order vs. sorting on demand; using a heap for dynamic updates vs. static sorted list.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.