Calculate Transaction Fees
Company: Stripe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are building a payment processor. Each transaction has an amount in cents, a payment type, and a payment status. The platform charges a percentage fee, and the fee rate is determined by the combination of `payment_type` and `payment_status`.
Implement a function that takes:
- a fee table mapping `(payment_type, payment_status)` to a rate in basis points
- a list of transactions in input order
For each transaction, compute its processing fee and also return the total fee across all transactions.
Rules:
- `fee = floor(amount_cents * rate_bps / 10000)`
- if a transaction has no matching fee rule, its fee is `0`
- preserve the input order for the per-transaction fee output
Example:
`fee_rules = [
("card", "paid", 290),
("card", "refunded", 100),
("bank_transfer", "paid", 80),
("wallet", "paid", 150)
]`
`transactions = [
("tx1", "card", "paid", 10000),
("tx2", "card", "refunded", 10000),
("tx3", "bank_transfer", "paid", 25000),
("tx4", "wallet", "failed", 5000)
]`
Expected per-transaction fees: `[290, 100, 200, 0]`
Expected total fee: `590`
Discuss the time and space complexity of your solution.
Quick Answer: This question evaluates data-structure and numerical computation skills, including mapping composite keys to fee rates, integer fixed-point arithmetic for fee calculation, and aggregation of per-transaction and total fees.
You are building a payment processor. Each fee rule maps a pair of values, `payment_type` and `payment_status`, to a fee rate in basis points. Each transaction contains a transaction ID, payment type, payment status, and amount in cents. For every transaction, compute its processing fee using the matching fee rule and return both the list of per-transaction fees in the original input order and the total fee across all transactions.
Use the formula: `fee = floor(amount_cents * rate_bps / 10000)`.
If a transaction has no matching fee rule, its fee is `0`. The `transaction_id` is included for completeness but does not affect the fee calculation.
Constraints
- 0 <= len(fee_rules), len(transactions) <= 100000
- 0 <= amount_cents <= 10^9
- 0 <= rate_bps <= 10000
- Each `(payment_type, payment_status)` pair in `fee_rules` is unique
Examples
Input: ([("card", "paid", 290), ("card", "refunded", 100), ("bank_transfer", "paid", 80), ("wallet", "paid", 150)], [("tx1", "card", "paid", 10000), ("tx2", "card", "refunded", 10000), ("tx3", "bank_transfer", "paid", 25000), ("tx4", "wallet", "failed", 5000)])
Expected Output: ([290, 100, 200, 0], 590)
Explanation: The matching fees are 10000*290//10000 = 290, 10000*100//10000 = 100, 25000*80//10000 = 200, and no rule for `(wallet, failed)` so 0. Total = 590.
Input: ([("card", "paid", 290)], [])
Expected Output: ([], 0)
Explanation: There are no transactions, so the per-transaction fee list is empty and the total fee is 0.
Hints
- A dictionary keyed by `(payment_type, payment_status)` lets you find the fee rate for each transaction in constant average time.
- You only need one pass over the transactions: compute each fee with integer division and keep a running total.