Stripe·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Stripe coding screen, payments domain, one algorithmic problem about matching payments to invoices. Pretty clean problem once you see the indexing trick, but I spent too long second-guessing the fallback logic.

Questions Asked (1)

Given a list of payments and a list of invoices, write a matching algorithm: first try to match each payment to an invoice by its invoice ID, and if that fails, match by amount (picking the earliest-dated invoice with that amount). Return all matched pairs and flag any unmatched payments.

Algorithms & Data StructuresData ModelingSystem Design

Author's notes

I got the exact-ID lookup immediately, that part was fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose a two-pass algorithm: first build a hash map from invoice ID to invoice for O(1) lookups, and a second map from amount to a sorted list of invoices (by date) for fallback matching. Iterate through payments, attempt ID match, then amount match, tracking matched pairs and unmatched payments, and analyze time/space complexity.

Pro tip: Discuss how to handle duplicate amounts and ensure deterministic matching by always picking the earliest-dated invoice; also mention that in a real system you'd need to consider partial payments, currency, and concurrency, but for this problem assume exact matches and single-threaded execution.

1. Clarify requirements and edge cases

Ask about input formats, whether invoice IDs are unique, if amounts can be negative or zero, and how to handle multiple invoices with the same amount. Confirm that unmatched payments should be returned separately.

2. Design data structures for efficient lookup

Use a hash map to map invoice IDs to invoices for O(1) ID matching. For amount matching, use another hash map mapping amount to a list of invoices sorted by date (earliest first), so you can efficiently pick the earliest-dated invoice.

3. Implement matching logic

Iterate through each payment: first try to find an invoice by ID; if found, mark it as matched and remove it from the amount map to avoid double matching. If not found, look up the amount in the amount map and pick the earliest-dated invoice; if found, mark it as matched and remove it. If no match, add payment to unmatched list.

4. Handle removal and updates efficiently

When an invoice is matched, remove it from both the ID map and the amount map's list. For the amount map, since lists are sorted, removing the first element is O(n) in worst case, but you can use a deque or maintain a pointer to avoid shifting. Discuss trade-offs.

5. Analyze complexity and test

Time complexity: O(P + I log I) for sorting invoices by amount and date, plus O(P) for matching. Space: O(I) for maps. Walk through examples, including edge cases like no matches, multiple matches, and duplicate amounts.

Key Points to Mention

Use of hash maps for O(1) average-time lookups by invoice ID and amount.
Sorting invoices by date within each amount group to ensure earliest-dated invoice is picked.
Removal of matched invoices from data structures to prevent double matching.
Handling of unmatched payments by collecting them in a separate list.
Time and space complexity analysis: O(P + I log I) time, O(I) space.
Edge cases: duplicate amounts, missing invoice IDs, empty lists, and payments with amounts not present in any invoice.

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