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.

Thread-Safe Stock Inventory: Buy and Sell Without Overselling

Company: Optiver

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Thread-Safe Stock Inventory: Buy and Sell Without Overselling You are implementing the inventory-management core of a small brokerage service. The service tracks the number of shares of a single stock that are currently available, and it exposes two operations that will be called concurrently from many threads. Implement a class `StockInventory` with the following interface: - `StockInventory(initial)` — construct the inventory with `initial` shares available. - `buy(quantity)` — acquire `quantity` additional shares and add them to the available inventory. A buy always succeeds. Returns the number of shares available immediately after this purchase is applied. - `sell(quantity)` — attempt to sell `quantity` shares out of the available inventory. The sale is all-or-nothing: if at least `quantity` shares are available at the moment the sale is applied, deduct exactly `quantity` shares and return `true`; otherwise leave the inventory unchanged and return `false`. Partial fills are not allowed. ### Correctness requirements Your implementation must remain correct when an arbitrary number of threads call `buy` and `sell` simultaneously on the same `StockInventory` object: 1. **No overselling.** The available share count must never become negative at any point in time. Two concurrent `sell` calls must never both succeed if the inventory can only cover one of them. 2. **No lost updates.** Every `buy` and every successful `sell` must be reflected exactly once in the inventory. After all threads finish, the final count must equal `initial + (sum of all bought quantities) - (sum of all successfully sold quantities)`. 3. **Atomic check-then-act.** The availability check inside `sell` and the corresponding deduction must happen atomically with respect to all other `buy` and `sell` calls — no other operation may interleave between the check and the update. You may use the standard synchronization primitives provided by your language's library (mutexes/locks, atomic operations, condition variables, etc.). Keep the critical sections as small as correctness allows. ### Example Single-threaded illustration of the required semantics: ```text inv = StockInventory(100) inv.sell(30) -> true (70 shares remain) inv.sell(80) -> false (only 70 available; inventory unchanged at 70) inv.buy(50) -> 120 (70 + 50) inv.sell(120) -> true (0 shares remain) inv.sell(1) -> false (inventory unchanged at 0) ``` Under concurrency, any interleaving of the calls is acceptable as long as every individual operation is atomic, the no-overselling invariant holds, and the final count is consistent with the set of operations that succeeded. ### Constraints - `0 <= initial <= 10^9` - `1 <= quantity <= 10^9` for every `buy` and `sell` call - Up to `10^5` total operations, issued from up to `64` concurrent threads - Each operation should complete in amortized $O(1)$ time outside of contention for the synchronization primitive

Quick Answer: This question evaluates understanding of concurrent programming, synchronization primitives, atomicity, and correctness of shared mutable state by requiring implementation of a thread-safe inventory that prevents overselling and preserves updates.

Implement a class `StockInventory` that tracks the number of shares of a single stock available and is safe to call concurrently from many threads. - `StockInventory(initial)` — construct the inventory with `initial` shares available. - `buy(quantity)` — add `quantity` shares to the available inventory (a buy always succeeds) and return the number of shares available immediately after the purchase. - `sell(quantity)` — all-or-nothing sale: if at least `quantity` shares are available at the moment the sale is applied, deduct exactly `quantity` and return `true`; otherwise leave the inventory unchanged and return `false`. Partial fills are not allowed. **Correctness requirements (must hold under arbitrary concurrent `buy`/`sell` calls on the same object):** 1. No overselling — the available count must never go negative; two concurrent `sell` calls must not both succeed if only one can be covered. 2. No lost updates — the final count must equal `initial + sum(bought) - sum(successfully sold)`. 3. Atomic check-then-act — inside `sell`, the availability check and the deduction must happen atomically with respect to every other `buy`/`sell`. Use a mutex/lock (or atomics/CAS) and keep the critical section as small as correctness allows. --- **How this console grades your work.** Concurrency itself is non-deterministic, so you implement your class and a small driver that replays a recorded sequence of calls. Write a function `solution(operations, arguments)` where `operations[i]` is one of `"StockInventory"`, `"buy"`, or `"sell"`, and `arguments[i]` is the argument list for that call. Return the list of results: `None`/`null` for the constructor, the post-buy count for `buy`, and `true`/`false` for `sell`. The lock in your class is what makes the design correct; the driver just exercises its semantics. **Example** ```text inv = StockInventory(100) inv.sell(30) -> true (70 remain) inv.sell(80) -> false (only 70 available; unchanged) inv.buy(50) -> 120 (70 + 50) inv.sell(120) -> true (0 remain) inv.sell(1) -> false (unchanged at 0) ``` Driver form: `solution(['StockInventory','sell','sell','buy','sell','sell'], [[100],[30],[80],[50],[120],[1]])` returns `[None, True, False, 120, True, False]`.

Constraints

0 <= initial <= 10^9
1 <= quantity <= 10^9 for every buy and sell call
Up to 10^5 total operations, from up to 64 concurrent threads
Each operation is amortized O(1) outside of contention for the lock
operations[i] is one of "StockInventory", "buy", "sell"; the first operation is always the constructor

Examples

Input: (['StockInventory', 'sell', 'sell', 'buy', 'sell', 'sell'], [[100], [30], [80], [50], [120], [1]])

Expected Output: [None, True, False, 120, True, False]

Explanation: The spec example. sell(30) succeeds (70 left); sell(80) fails and leaves 70; buy(50) returns 120; sell(120) drains to 0; sell(1) fails.

Input: (['StockInventory', 'sell', 'buy', 'sell'], [[0], [1], [5], [5]])

Expected Output: [None, False, 5, True]

Explanation: Starting empty, sell(1) fails; buy(5) returns 5; sell(5) exactly drains the inventory and succeeds.

Input: (['StockInventory'], [[10]])

Expected Output: [None]

Explanation: Construct-only edge case: the constructor returns nothing (None); no buy/sell issued.

Input: (['StockInventory', 'buy', 'sell', 'sell'], [[1000000000], [1000000000], [2000000000], [1]])

Expected Output: [None, 2000000000, True, False]

Explanation: Boundary values: initial 10^9, buy 10^9 -> 2*10^9; sell(2*10^9) exactly clears it; the final sell(1) fails.

Input: (['StockInventory', 'sell', 'sell', 'sell'], [[5], [5], [1], [5]])

Expected Output: [None, True, False, False]

Explanation: First sell(5) drains all 5 shares; the remaining sells (1 and 5) both fail because inventory is 0 — demonstrating the no-overselling invariant.

Hints

A single integer counter plus one mutex is enough: guard both buy and sell with the same lock so no other operation can interleave between the availability check and the update.
The sell must be all-or-nothing: check `available >= quantity` and do the subtraction inside the same critical section. Never release the lock between the check and the deduction, or two concurrent sells could both pass the check and oversell.
buy simply adds to the counter and returns the new value under the lock. Keep the critical section to just the read-modify-write so throughput stays high.
An alternative to a mutex is a lock-free compare-and-swap loop on an atomic counter (retry until the CAS succeeds), which also enforces atomic check-then-act.

Quick Overview

This question evaluates understanding of concurrent programming, synchronization primitives, atomicity, and correctness of shared mutable state by requiring implementation of a thread-safe inventory that prevents overselling and preserves updates.