Frontend School

Optimal Payment Plan Selection

DSA
hard

Optimal Payment Plan Selection

Hard
Dynamic Programming
1D DP
Optimization
Financial

Overview

Razorpay processes millions of transactions daily for businesses across India. Optimizing the cost of these transactions is crucial for maintaining profitability and competitive pricing. Different payment processing plans offer varying fixed and percentage-based fees. Furthermore, switching between these plans can incur an administrative cost. As a key engineer, your task is to design an algorithm that determines the optimal sequence of plan selections to minimize the total fees incurred for a series of incoming payment requests.

What you need to do / Task

You are given a sequence of payment amounts and a set of available plans, each with a fixedFee and a percentageFee. You also know a global switchCost that applies whenever you change from one plan to any other for consecutive payments. Your goal is to implement a function that calculates the minimum possible total fees incurred for processing all payments.

  1. Implement the minTotalFees function.
  2. The function should take amounts, plans, and switchCost as input.
  3. It must return the minimum total fees as a number.
  4. Assume that for the first payment, there is no switch cost incurred, as no previous plan was active.

Input & Output

Input

  • amounts: An array of number representing the value of each payment request, in chronological order.
  • plans: An array of objects, where each object represents a processing plan. Each plan object has two properties:
    • fixedFee: A number representing the fixed fee component of the plan.
    • percentageFee: A number representing the percentage fee component (e.g., 2.5 for 2.5%).
  • switchCost: A number representing the cost incurred when switching from any plan to any other different plan for consecutive payments.

Output

  • A number representing the minimum total fees incurred across all payments.

Fee Calculation

For a payment of amount using a plan with fixedFee and percentageFee: Fee = fixedFee + (amount * percentageFee / 100.0)

Clarifications

  • Empty Input: The amounts array will never be empty.
  • Precision: Calculations involving percentage fees should maintain reasonable floating-point precision. The final result should be a single number.
  • Switching: If the same plan is chosen for consecutive payments, no switchCost is incurred. A switchCost is only applied when the chosen plan for payment i is different from the chosen plan for payment i-1. For the very first payment, no switchCost is ever applied.

Examples

1

Example 1

Input:

amounts = [1000, 2000], plans = [{ "fixedFee": 10, "percentageFee": 1 }, { "fixedFee": 5, "percentageFee": 2 }], switchCost = 5

Output:

50

Note:

P0 for both payments: (10 + 10000.01) + (10 + 20000.01) = 20 + 30 = 50. This is the minimum.

2

Example 2

Input:

amounts = [500], plans = [{ "fixedFee": 0, "percentageFee": 3 }, { "fixedFee": 15, "percentageFee": 0 }], switchCost = 100

Output:

15

Note:

Only one payment. Using Plan 0: 0 + 5000.03 = 15. Using Plan 1: 15 + 5000 = 15. Both yield 15.

3

Example 3

Input:

amounts = [100, 100, 100], plans = [{ "fixedFee": 1, "percentageFee": 0 }, { "fixedFee": 0, "percentageFee": 1 }], switchCost = 0

Output:

3

Note:

With zero switch cost, for each payment of 100, Plan 0 (1 + 00.01 = 1) and Plan 1 (0 + 1000.01 = 1) both cost 1. Total = 1*3 = 3.

Constraints

Constraints & assumptions

  • 1 <= amounts.length (N) <= 10^5
  • 1 <= plans.length (K) <= 100
  • 1 <= amounts[i] <= 10^9
  • 0 <= plans[j].fixedFee <= 10^6
  • 0 <= plans[j].percentageFee <= 100 (integer percentage)
  • 0 <= switchCost <= 10^7
  • All input values are non-negative.
  • The minimum total fees can be a large floating-point number.

What interviewers evaluate

  • Problem Understanding & Optimal Approach: Ability to identify the dynamic programming structure and formulate an optimal O(N*K) solution.
  • Correctness: Accurate implementation of the DP transitions, base cases, and fee calculations, handling floating-point precision appropriately.
  • Edge Cases: Correct handling of single payment scenarios, zero switch cost, and zero fees.
  • Code Quality & Readability: Clean, well-structured, and easy-to-understand code with appropriate variable names.

Loading editor...