Calculate Transaction Fees

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.

Calculate Transaction 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

Hints

1. A dictionary keyed by (payment_type, payment_status) lets you find the fee rate for each transaction in constant average time.
2. You only need one pass over the transactions: compute each fee with integer division and keep a running total.

Approach

Approach: hash-map lookup of fee rules

The fee for a transaction depends only on its (payment_type, payment_status) pair, so the core idea is to make rule lookup O(1) by indexing the rules in a dictionary, then doing a single pass over the transactions.

Step 1 — build the rule index. We iterate over fee_rules and store each rate_bps keyed by the tuple (payment_type, payment_status):

The constraints guarantee each pair is unique, so no overwrites or tie-breaking are needed. Using a tuple as the key lets a single dictionary capture the two-dimensional rule space.

Step 2 — process transactions in order. We loop over transactions, unpacking and discarding transaction_id (it doesn't affect the fee). For each one we look up its rate with rule_map.get(key, 0) — the default 0 cleanly handles the "no matching rule" case, so an unmatched transaction contributes a fee of 0.

Step 3 — apply the fee formula. The fee is (amount_cents * rate_bps) // 10000. Python's // is floor division, which exactly matches the required floor(amount_cents * rate_bps / 10000); using integer arithmetic avoids any float rounding error. Each fee is appended to fees (preserving original input order) and accumulated into total_fee.

Why it's correct. Lookups reproduce the exact rule for each pair; the default handles missing rules; integer floor division matches the spec; results are appended in iteration order, so fees[i] corresponds to transactions[i], and total_fee is the sum of those fees.

• Time complexity: O(r + t), where r = len(fee_rules) and t = len(transactions). Building the dictionary is O(r); the single transaction pass does O(1) hash lookups, so it is O(t).
• Space complexity: O(r + t): O(r) for the rule dictionary plus O(t) for the returned fees list. Auxiliary space excluding the output is O(r).