Payment Reconciliation (Transactions Matching & Discrepancy Report)

Payment Reconciliation (Transactions Matching & Discrepancy Report) You are given payment records from two systems (e.g., an internal ledger and an external processor). Each transaction contains at least: transaction_id (may be missing or inconsistent across systems) amount (positive) currency timestamp status (e.g., succeeded/failed/refunded) Implement a reconciliation function that matches transactions across the two systems and reports discrepancies. Output Matched: pairs confirmed to be the same transaction. Only in A: transactions that appear only in system A. Only in B: transactions that appear only in system B. Mismatched: likely same transaction but key fields differ (amount/currency/status, etc.). Matching rules (common interview version) Prefer exact match by transaction_id. If transaction_id is missing/unmatchable, use heuristics: same amount and currency timestamp within a window (e.g., ±5 minutes) pick the closest timestamp candidate; each transaction can be matched at most once Constraints & edge cases Inputs may include duplicates. Partial refunds, duplicate charges, and delayed posting may cause differences. Target time complexity near O(n log n). Example test scenarios Case 1: same id and same fields → matched Case 2: same id but different amount → mismatched Case 3: one extra record on one side → only in A/B Case 4: no id, match via amount+currency+time window Case 5: multiple candidates with same amount/currency → avoid one-to-many matches Example Input A=[{id:1,amount:10,currency:USD,t:100,status:succeeded}] B=[{id:1,amount:10,currency:USD,t:101,status:succeeded}] Output matched=[(1,1)] onlyA=[] onlyB=[] mismatched=[]