Quick Overview

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.

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. ```

Overview: 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

  1. Test zero allowed days with equal and unequal initial and target holdings.
  2. Include a target farther from the start than the day limit and cases that begin at zero holdings.
  3. Check both exact-length parity effects and the maximum holding/day boundaries.

Loading coding console...

Show the approach

Approach

For each exact sequence length, track how many legal sequences end at every reachable holding. A buy moves a count to holding+1, while a sell moves it to holding-1 only above zero. Add the target state's count after each length, plus the empty sequence at length zero when applicable, to obtain the at-most-m total. Counts can be saturated at the promised exact-answer ceiling so irrelevant states cannot overflow fixed-width languages.

Time complexity:
O(m * (k + m)) because only holdings reachable within m days are tracked.
Space complexity:
O(k + m) auxiliary space.