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