You are building a small payment processor for a multi-currency wallet. ## Inputs 1. **Wallet balances**: a map `balances[currency] -> integer` representing the available amount in the *smallest unit* (e.g., cents). 2. **Payment method fees**: a map `methodFeeBps[method] -> integer` (fee in basis points). The **payment method fee** is: \[ fee = \left\lceil amount \times \frac{methodFeeBps}{10000} \right\rceil \] Total cost to the wallet is `amount + fee`. 3. **FX rates** (added in Part 2): a map `fx[from][to] -> (num, den)` meaning: \[ 1\ \text{unit of } from = \frac{num}{den}\ \text{units of } to \] All amounts are integer in smallest units; conversions must use **ceil** when needed. 4. **Conversion fee** (added in Part 2): `conversionFeeBps` (basis points) charged on the **source currency** amount you convert. If you convert `x` units of `from`, the fee is: \[ convFee = \left\lceil x \times \frac{conversionFeeBps}{10000} \right\rceil \] and the wallet is debited `x + convFee` from the source currency. 5. **Payments**: a list of payment requests. Each payment has: - `id` - `amount` (integer smallest units) - `currency` - `method` Payments must be processed **in order**, and balances update after each payment. --- ## Part 1 (no FX) For each payment, determine whether it **succeeds** using only the wallet balance in the same currency. - If `balances[currency] >= amount + methodFee`, mark **SUCCESS** and subtract the total from that currency. - Otherwise mark **FAIL** and do not change balances. Return the per-payment result list. --- ## Part 2 (with FX + conversion fee) Now allow paying a charge in currency `C` by using the balance in `C` and, if needed, converting funds from other currencies. Rules/assumptions: - You may convert from any other currency `S != C` directly to `C` using `fx[S][C]`. - You may perform multiple conversions for a single payment (from multiple source currencies). - Do **not** use multi-hop conversions (only direct `S -> C`). - If a payment can be funded, it must be applied and balances updated; otherwise it fails with no balance changes. - Use integer arithmetic and apply **ceil rounding** for (a) method fees, (b) conversion fees, and (c) FX conversion when computing how much source currency is required. Task: determine **SUCCESS/FAIL** for each payment and update balances accordingly. Implementation note (to remove ambiguity): when a payment needs extra funds beyond `balances[C]`, your algorithm may choose any deterministic conversion order (e.g., iterate currencies in sorted order) as long as it never overspends a balance and correctly determines feasibility. --- ## What to implement Write a function (language-agnostic) like: - `processPayments(balances, methodFeeBps, payments, fx, conversionFeeBps) -> (results, finalBalances)` where `results[i]` is `"SUCCESS"` or `"FAIL"`. ## Constraints (typical interview scale) - Number of payments up to `1e5` - Number of currencies up to `50` - All amounts fit in 64-bit signed integers