How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Optiver during technical interviews.

Count nonnegative buy/sell sequences | Optiver Coding Question

Quick Overview

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.

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.

Input: (2,)

Expected Output: 2

Explanation: The valid sequences are buy-buy-sell-sell and buy-sell-buy-sell.

Input: (3,)

Expected Output: 5

Explanation: There are 5 valid sequences, which is the 3rd Catalan number.

Input: (4,)

Expected Output: 14

Explanation: There are 14 valid sequences for 4 buys and 4 sells.

Input: (8,)

Expected Output: 1430

Explanation: This is the 8th Catalan number.

Solution

def solution(n):
    if n < 0:
        raise ValueError("n must be nonnegative")

    catalan = 1
    for k in range(n):
        catalan = catalan * 2 * (2 * k + 1) // (k + 2)
    return catalan

Time complexity: O(n). Space complexity: O(1).

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.

Last updated: Jun 6, 2026

Loading coding console...