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.
Overview: 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.
Community answers
Answer by Maximus
#include
#include
#include
#include
using namespace std;
class Solution {
public:
pair, long long> solution(vector>& fee_rules, vector>& transactions) {
map,int> typeAndStatusFee;
for(auto x : fee_rules){
auto [paymentType,PaymentStatus,fee] = x;
typeAndStatusFee[{paymentType,PaymentStatus}] = fee;
}
vector transactionFees;
for(auto x : transactions){
auto [transactionId,paymentType,PaymentStatus,amount] = x;
if(!typeAndStatusFee.count({paymentType,PaymentStatus})){
transactionFees.push_back(0);
continue;
}
long long transactionFee = typeAndStatusFee[{paymentType,PaymentStatus}];
long long fee = (1LLamounttransactionFee)/10000;
transactionFees.push_back(fee);
}
long long sum = accumulate(transactionFees.begin(),transactionFees.end(),0LL);
return {transactionFees,sum};
}
};
Answer by prasadkirpekar96
def solution(fee_rules, transactions):
fee_map = {}
for kind, status, rate in fee_rules:
fee_map[(kind, status)] = rate
res = []
total = 0
for tid, kind, status, amount in transactions:
fee_key = (kind, status)
if fee_key in fee_map:
bps = fee_map[fee_key]
else:
bps = 0
fee = (bps * amount) // 10000
total += fee
res.append(fee)
return (res, total)
Answer by anupamaixb04
#include
#include
#include
#include
#include
using namespace std;
class Solution {
public:
pair, long long> solution(vector>& fee_rules, vector>& transactions) {
map mpp;
for(int i=0;i(fee_rules[i]);
string b=get<1>(fee_rules[i]);
int c=get<2>(fee_rules[i]);
string temp=a+"#"+b;
mpp[temp]=c;
}
long long total=0;
vector a;
for(int i=0;i(transactions[i]);
string b=get<2>(transactions[i]);
int x=get<3>(transactions[i]);
string temp=ai+"#"+b;
if(mpp.find(temp)==mpp.end()){
a.push_back(0);
continue;
}
int y=mpp[temp];
long long bi=1LLxy;
bi=floor(bi/10000);
a.push_back(bi);
total+=bi;
}
return {a,total};
}
};
Answer by ronsk0311
#include
#include
#include
#include
using namespace std;
class Solution {
public:
pair, long long> solution(vector>& fee_rules, vector>& transactions) {
map , long long> mp;
for(int i=0;i(fee_rules[i]), get<1>(fee_rules[i])}]=get<2>(fee_rules[i]);
}
vector ans;
for(int i=0;i(transactions[i]);
string status=get<2>(transactions[i]);
long long amt=get<3>(transactions[i]);
long long k=amt*mp[{type, status}]/10000;
ans.push_back(k);
}
long long l=accumulate(ans.begin(), ans.end(), 0);
pair , long long> fina={ans, l};
return fina;
}
};