Practice/Capital One/Build a Payment Management System

Build a Payment Management System

CodingMust

Problem

Design and implement a transaction refund processing system that generates refunds from a list of payments to meet a target refund amount. The system must follow specific rules for payment type priority and selection criteria.

When processing refunds, payment methods have a strict priority order: credit payments are processed first, followed by credit_card payments, and finally paypal payments. Within each payment type, only the payment with the most recent timestamp can be used for refunds.

The system must account for any existing refunds already issued against payments, reducing the available refundable amount accordingly. If the total available funds across all eligible payments cannot meet the target refund amount, the function should return an empty list.

Requirements

1. Process payment types in priority order: credit → credit_card → paypal
2. For each payment type, select only the payment with the latest timestamp
3. Account for existing refunds when calculating available refund amounts
4. Generate refunds to exactly meet the target amount, drawing from multiple payment types if needed
5. Return an empty list if the target amount cannot be fully satisfied
6. Each refund should specify the payment_id and refund_amount
7. Multiple refunds can be issued against the same payment (cumulative with existing refunds)

Constraints

• 1 ≤ payments.length ≤ 1000
• 0 ≤ existing_refunds.length ≤ 5000
• 1 ≤ target_amount ≤ 1,000,000
• 1 ≤ payment.amount ≤ 100,000
• 1 ≤ payment.timestamp ≤ 10^9
• Payment types are limited to: "credit", "credit_card", "paypal"
• All payment IDs are unique
• Time complexity should be O(n log n) or better where n is the number of payments
• Space complexity should be O(n) or better

Examples

Example 1:

` Input: payments = [ {"id": "pay1", "type": "credit", "amount": 100, "timestamp": 1000}, {"id": "pay2", "type": "credit", "amount": 200, "timestamp": 2000} ] existing_refunds = [] target_amount = 150

Output: [{"payment_id": "pay2", "refund_amount": 150}]

Explanation: Between the two credit payments, pay2 has the more recent timestamp (2000 > 1000). Since pay2 has 200 available and we need 150, we can fully satisfy the target with a single refund from pay2. `

Example 2:

` Input: payments = [ {"id": "pay1", "type": "paypal", "amount": 150, "timestamp": 3000}, {"id": "pay2", "type": "credit", "amount": 100, "timestamp": 2000}, {"id": "pay3", "type": "credit_card", "amount": 80, "timestamp": 1500} ] existing_refunds = [] target_amount = 120

Output: [ {"payment_id": "pay2", "refund_amount": 100}, {"payment_id": "pay3", "refund_amount": 20} ]

Explanation: Following priority order, we first use the latest credit payment (pay2) which provides 100. We still need 20 more, so we move to the next priority (credit_card) and use pay3 for the remaining 20. PayPal is not needed. `

Example 3:

` Input: payments = [ {"id": "pay1", "type": "credit", "amount": 200, "timestamp": 1000}, {"id": "pay2", "type": "credit_card", "amount": 150, "timestamp": 2000} ] existing_refunds = [{"payment_id": "pay1", "refund_amount": 50}] target_amount = 100

Output: [{"payment_id": "pay1", "refund_amount": 100}]

Explanation: pay1 originally had 200, but 50 has already been refunded. This leaves 150 available, which is sufficient for the 100 target. Since credit has higher priority than credit_card, we use pay1. `