← Stripe Interview Insights

Stripe·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
Jun 2026Remote

Summary

Stripe SWE interview with a meaty coding problem around payment matching logic. The problem looked like a straightforward lookup at first but the follow-up discussion on data structures and edge cases is where things got interesting.

Questions Asked (3)

Q1

Given a list of payments and a list of invoices, implement a matching algorithm with three priority levels: first match by invoice ID, then by exact amount (earliest date wins), then by amount within a tolerance range (again earliest date wins). Return matched pairs and any leftovers on both sides.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The id-based match felt easy and I got through it quickly, but I tripped on the forgiveness range part.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements and edge cases, then outline a multi-pass algorithm that processes matches in priority order while tracking used items. For each pass, use appropriate data structures (hash map for ID matching, sorted lists for amount matching) to efficiently find matches, and finally return matched pairs and leftovers.

Pro tip: Emphasize that the algorithm should be deterministic and stable, and discuss how to handle ties in the tolerance range (e.g., by earliest date, then by smallest difference). Also, mention that you would write unit tests for each priority level and edge cases.

1. Clarify requirements and edge cases

Ask questions to confirm details: Are IDs unique? Can amounts be negative? What is the tolerance range? Should matches be one-to-one? How to handle ties in tolerance? This ensures you understand the problem fully.

2. Design data structures and preprocessing

Choose structures to efficiently find matches: a hash map from invoice ID to invoice for ID matching, and sorted lists (by amount, then date) for amount matching. Mark items as matched to avoid reuse.

3. Implement priority passes

First pass: match by invoice ID using the hash map. Second pass: match remaining by exact amount, iterating through sorted amounts and picking earliest date. Third pass: match by amount within tolerance, again using sorted amounts and earliest date, ensuring no item is matched twice.

4. Collect and return results

After all passes, gather matched pairs and any unmatched payments and invoices. Return them in a clear structure, ensuring all items are accounted for.

5. Analyze complexity and trade-offs

Discuss time and space complexity of your approach (e.g., O(n log n) due to sorting) and consider alternative strategies (e.g., greedy vs. optimal matching) and their implications.

Key Points to Mention

  • Priority order: ID match > exact amount > tolerance range, with earliest date as tiebreaker.
  • Use of hash maps for O(1) ID lookups and sorted lists for efficient amount matching.
  • Handling of edge cases: multiple matches, no matches, ties in tolerance, negative amounts, empty lists.
  • Determinism and stability: ensure consistent results by defining clear tie-breaking rules.
  • Complexity analysis: time and space complexity of the algorithm and potential optimizations.
  • Testing strategy: unit tests for each priority level and edge cases to ensure correctness.

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

Q2

What data structure would you use to efficiently find invoices whose amount falls within a given range, and how does it handle deletions as invoices get matched?

Algorithms & Data StructuresSystem Design
Author's notes

Talked about a sorted list with binary search to find the range boundaries, which covers the lookup.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: the data structure must support efficient range queries (find invoices with amount in [min, max]) and frequent deletions as invoices are matched. Then propose a balanced binary search tree (e.g., red-black tree) or a skip list, explaining how both operations achieve O(log n) time. Finally, discuss how deletions are handled by removing the node and rebalancing, and mention any trade-offs or alternatives like B-trees for disk-based storage.

Pro tip: Mention that in a real system like Stripe, you'd likely use a database index (e.g., B-tree) rather than an in-memory structure, and discuss how deletions might be soft deletes or handled via tombstones to maintain consistency.

1. Clarify requirements

Confirm that the primary operations are range queries and deletions, and ask about expected data size, concurrency, and persistence needs.

2. Choose a data structure

Select a balanced BST (e.g., red-black tree) or skip list for O(log n) range queries and deletions, and justify why it fits the requirements.

3. Explain range query algorithm

Describe how to traverse the tree to find all nodes within the range, using in-order traversal or pruning subtrees outside the range.

4. Explain deletion handling

Detail the deletion process: locate the node, remove it, and rebalance the tree to maintain O(log n) performance.

5. Discuss trade-offs and alternatives

Compare with other structures (e.g., hash tables, sorted arrays) and mention real-world considerations like database indexes or concurrent access.

Key Points to Mention

  • Balanced BST (e.g., red-black tree) provides O(log n) for insert, delete, and range queries.
  • Range query can be done in O(log n + k) where k is the number of results, using in-order traversal with pruning.
  • Deletion requires rebalancing to maintain tree height, ensuring logarithmic time.
  • Skip lists are a simpler alternative with similar performance and easier concurrent implementation.
  • In practice, a database B-tree index is often used for disk-based storage and range queries.
  • Consider soft deletes or tombstones if the system requires auditability or eventual consistency.

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

Q3

If two invoices are eligible under the forgiveness rule and have the same date, how do you break the tie, and does the order in which you process payments matter for the final result?

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

Yeah this one tripped me up a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the tie-breaking rule by defining a deterministic secondary key (e.g., invoice ID) and explain that the final result should be independent of processing order if the rule is consistent. Discuss whether the problem requires a stable sort or a greedy algorithm, and analyze if order affects the outcome due to constraints like limited funds or priority rules.

Pro tip: Mention that in financial systems, determinism and auditability are critical, so tie-breaking should be explicitly defined and documented. Also, consider edge cases like multiple invoices with the same date and amount to show thoroughness.

1. Clarify the problem and constraints

Ask clarifying questions about the forgiveness rule, such as whether there's a limit on total forgiveness or if invoices have different amounts. Confirm if the tie-breaking should be based on a specific field or if any deterministic rule is acceptable.

2. Define a deterministic tie-breaking rule

Propose a secondary key like invoice ID, amount, or creation timestamp to break ties consistently. Explain that this ensures reproducibility and avoids ambiguity in processing.

3. Analyze order dependency

Determine if the final result (e.g., which invoices are forgiven) depends on processing order. If the rule is a simple eligibility check without resource constraints, order doesn't matter; if there's a budget constraint, order can affect which invoices are selected.

4. Discuss algorithmic implications

Explain that if order matters, you might need to sort invoices by the tie-breaking key and then apply a greedy algorithm. If order doesn't matter, you can process in any order, but still apply the tie-breaking rule for consistency.

5. Conclude with best practices

Summarize that the tie-breaking rule should be deterministic and documented, and that order independence is desirable but may not hold under constraints. Emphasize testing edge cases to ensure correctness.

Key Points to Mention

  • Deterministic tie-breaking (e.g., by invoice ID) ensures consistent results.
  • Order independence holds if there are no resource constraints (e.g., unlimited forgiveness).
  • If there's a limited budget, order can affect which invoices are forgiven, so a priority rule is needed.
  • Stable sorting can preserve original order for ties, but a secondary key is still needed for full determinism.
  • Financial systems require auditability, so the tie-breaking rule must be explicit and reproducible.
  • Consider edge cases: multiple invoices with same date and amount, or partial forgiveness scenarios.

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