Calculate Tax from Progressive Brackets
Company: Gusto
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Calculate Tax from Progressive Brackets
### Problem
Implement `calculateProgressiveTax(income, upperBounds, ratesBps) -> tax`.
`income` is a nonnegative integer number of minor currency units. `ratesBps` contains one marginal rate per tax bracket in basis points, where `10,000` basis points means `100%`. `upperBounds` contains the exclusive upper income boundary of every bracket except the final open-ended bracket.
If `ratesBps.length == m`, then `upperBounds.length == m - 1` and the brackets are:
- bracket `0`: `[0, upperBounds[0])` when `m > 1`;
- bracket `i`: `[upperBounds[i - 1], upperBounds[i])` for each interior bracket;
- bracket `m - 1`: `[upperBounds[m - 2], infinity)` when `m > 1`;
- when `m == 1`, the single rate applies to all income.
Only the income slice inside a bracket is taxed at that bracket's rate. Compute the full tax numerator as the sum of `slice * rateBps` across brackets, then return `floor(totalNumerator / 10,000)`. Round down once after summing all brackets; do not round each bracket separately.
### Function Contract
- `income` is a JSON integer.
- `upperBounds` and `ratesBps` are JSON arrays of integers.
- Return one JSON integer `tax` in minor currency units.
- Do not mutate either input array.
### Constraints
- `0 <= income <= 100,000,000,000`.
- `1 <= ratesBps.length <= 200,000`.
- `upperBounds.length + 1 == ratesBps.length`.
- Every boundary is in `[1, 100,000,000,000]`, and boundaries are strictly increasing.
- Every rate is in `[0, 10,000]` basis points.
- The largest possible numerator is `1,000,000,000,000,000`, which is exact in signed 64-bit arithmetic and in JavaScript's safe-integer range.
- Target `O(m)` time and `O(1)` auxiliary space, where `m` is the number of rates.
### Examples
```text
income = 50000
upperBounds = [10000, 40000]
ratesBps = [1000, 2000, 3000]
tax = 10000
```
The three taxable slices are `10000`, `30000`, and `10000` at `10%`, `20%`, and `30%` respectively.
```text
income = 40000
upperBounds = [10000, 40000]
ratesBps = [1000, 2000, 3000]
tax = 7000
```
An exclusive boundary of `40000` means no income reaches the final bracket here.
```text
income = 9999
upperBounds = [10000]
ratesBps = [750, 2500]
tax = 749
```
The exact numerator is `7,499,250`; rounding occurs once after division by `10,000`.
```text
income = 0
upperBounds = []
ratesBps = [10000]
tax = 0
```
```hint Track the previous boundary
For each rate, intersect its bracket interval with `[0, income)` and add only that slice to the numerator.
```
### Discussion Requirements
1. Explain why applying the highest reached rate to all income is not a marginal-bracket calculation.
2. Show how exclusive boundaries avoid double-counting income at an exact cutoff.
3. Explain why rounding once can differ from rounding each bracket independently.
4. State how the scan can stop after the bracket containing `income`.
Quick Answer: Implement progressive tax calculation with exclusive upper bracket boundaries, integer minor units, and basis-point rates. Focus on marginal slices, one-time rounding, boundary correctness, large inputs, and an efficient linear scan.
## Calculate Tax from Progressive Brackets
Implement `calculateProgressiveTax(income, upperBounds, ratesBps) -> tax`.
`income` is a nonnegative integer number of minor currency units. `ratesBps` holds one marginal rate per tax bracket in basis points, where `10,000` basis points means `100%`. `upperBounds` holds the **exclusive** upper income boundary of every bracket except the final open-ended one.
If `ratesBps.length == m`, then `upperBounds.length == m - 1` and the brackets are:
- bracket `0`: `[0, upperBounds[0])` when `m > 1`;
- bracket `i`: `[upperBounds[i - 1], upperBounds[i])` for each interior bracket;
- bracket `m - 1`: `[upperBounds[m - 2], infinity)` when `m > 1`;
- when `m == 1`, the single rate applies to all income.
Only the income slice that falls inside a bracket is taxed at that bracket's rate. Compute the full tax numerator as the sum of `slice * rateBps` across every bracket, then return `floor(totalNumerator / 10,000)`. Round down exactly **once**, after summing all brackets; do not round each bracket separately.
### Function contract
- `income` is an integer.
- `upperBounds` and `ratesBps` are integer arrays.
- Return one integer `tax` in minor currency units.
- Do not mutate either input array.
### Examples
```text
income = 50000
upperBounds = [10000, 40000]
ratesBps = [1000, 2000, 3000]
tax = 10000
```
The three taxable slices are `10000`, `30000` and `10000`, taxed at `10%`, `20%` and `30%`, so the numerator is `10,000,000 + 60,000,000 + 30,000,000 = 100,000,000` and the tax is `10000`.
```text
income = 40000
upperBounds = [10000, 40000]
ratesBps = [1000, 2000, 3000]
tax = 7000
```
Because `40000` is an **exclusive** boundary, no income reaches the final bracket: the numerator is `10,000,000 + 60,000,000 = 70,000,000`.
```text
income = 9999
upperBounds = [10000]
ratesBps = [750, 2500]
tax = 749
```
The exact numerator is `9999 * 750 = 7,499,250`, and the single trailing floor gives `749`.
```text
income = 0
upperBounds = []
ratesBps = [10000]
tax = 0
```
### Output semantics
The answer is a single integer, so there is no ordering or tie-breaking ambiguity. Two correct implementations must return the identical value for every input in the domain below.
Constraints
- 0 <= income <= 100,000,000,000
- 1 <= ratesBps.length <= 200,000
- upperBounds.length + 1 == ratesBps.length
- 1 <= upperBounds[i] <= 100,000,000,000, and upperBounds is strictly increasing
- 0 <= ratesBps[i] <= 10,000 basis points
- The largest possible numerator is 1,000,000,000,000,000, which is exact in signed 64-bit arithmetic and inside JavaScript's safe-integer range; Java must accumulate in long and C++ in long long, because the numerator exceeds 2^31 - 1
- Target O(m) time and O(1) auxiliary space, where m = ratesBps.length
Examples
Input: (50000, [10000, 40000], [1000, 2000, 3000])
Expected Output: 10000
Explanation: Prompt example 1: slices 10000/30000/10000 taxed at 10%/20%/30% give numerator 100,000,000.
Input: (40000, [10000, 40000], [1000, 2000, 3000])
Expected Output: 7000
Explanation: Prompt example 2: income lands exactly on the exclusive boundary 40000, so the final open-ended bracket receives no slice.
Hints
- Carry the previous boundary as you scan: it is the inclusive lower edge of the bracket you are about to charge.
- Intersect each bracket interval with [0, income) and add only that overlap, so a bracket entirely above income contributes nothing and the scan can stop there.
- Keep one running numerator in a 64-bit accumulator and divide by 10,000 only after the loop ends.