Count nonnegative buy/sell sequences
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You must perform exactly 2n unit trades starting with 0 shares and ending with 0 shares. Each trade is either a buy (+1 share) or a sell (−1 share), and your running position may never be negative at any point. Given n, how many distinct buy/sell sequences satisfy these constraints? Return the count for the given n and describe an efficient approach.
Quick Answer: This question evaluates combinatorial reasoning and algorithmic analysis by asking for the count of constrained buy/sell sequences, testing competence in counting under constraints and reasoning about sequence invariants.
You must perform exactly 2n unit trades. You start with 0 shares, each buy increases your position by 1, and each sell decreases it by 1. After all 2n trades, you must end back at 0 shares, and your running position may never become negative at any point.
Return the number of distinct buy/sell sequences that satisfy these rules for a given n.
An efficient solution should avoid generating all possible sequences, since there are exponentially many of them. This counting problem is equivalent to counting valid parentheses strings with n pairs.
Constraints
- 0 <= n <= 1000
- You must return the exact count, not modulo any value
- The empty sequence for n = 0 counts as one valid sequence
Examples
Input: (0,)
Expected Output: 1
Explanation: With 0 trades, the only valid sequence is the empty sequence.
Input: (1,)
Expected Output: 1
Explanation: The only valid sequence is buy, then sell.
Hints
- Try viewing a buy as '(' and a sell as ')'. What well-known counting problem does that become?
- Instead of generating sequences, use the recurrence for Catalan numbers to compute the answer in O(n) time.