Count Bounded Buy-and-Sell Sequences
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Count Bounded Buy-and-Sell Sequences
You start with k shares. On each transaction day, you either buy one share or sell one share, but holdings may never become negative. Count all distinct transaction sequences of length at most m that end with exactly n shares. The empty sequence counts only when k equals n.
## Function Contract
Implement `count_transaction_sequences(n, k, m) -> int`.
## Constraints
- 0 <= n, k <= 200.
- 0 <= m <= 200.
- Every sequence prefix must leave holdings nonnegative.
- The answer is guaranteed to be at most 2^53 - 1.
## Examples
```text
n = 2, k = 1, m = 3
output = 4
```
```text
n = 0, k = 0, m = 0
output = 1
```
```hint Check the shortest cases
Include zero allowed days, an already-satisfied target, and a target farther from the initial holding than the available transaction count.
```
```hint Respect the lower boundary
Exercise a sequence that would try to sell when the current holding is zero, and confirm that it is excluded.
```
Quick Answer: You start with k shares. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Start with `k` shares. On each transaction day, either buy one share or sell one share, but no prefix may make holdings negative. Count all distinct transaction sequences of length at most `m` that end with exactly `n` shares. The empty sequence counts exactly when `k == n`.
Constraints
- 0 <= n, k <= 200 and 0 <= m <= 200.
- Every transaction changes holdings by exactly one, and every sequence prefix must keep holdings nonnegative.
- All sequence lengths from zero through m qualify, and the exact answer is at most 2^53 - 1.
Examples
Input: (2, 1, 3)
Expected Output: 4
Explanation: One length-one and three valid length-three sequences end at two shares.
Input: (0, 0, 0)
Expected Output: 1
Explanation: The empty sequence is counted when initial and target holdings agree.
Hints
- Test zero allowed days with equal and unequal initial and target holdings.
- Include a target farther from the start than the day limit and cases that begin at zero holdings.
- Check both exact-length parity effects and the maximum holding/day boundaries.