Voleon Group Software Engineer Onsite Coding Questions

## Problem Determine if a string is 'good' by some criterion, or transform it to become good (e.g., removing bad substrings). ## Likely LeetCode equivalent Similar to LC 1544 Make The String Great. ## Tags strings, stack, voleon

## Problem Implement a `SparseMatrix` class for large matrices where most entries are zero. Support addition, multiplication, and transpose. Use a compressed representation (e.g., dictionary of non-zero entries or CSR format). ```python class SparseMatrix: def __init__(self, rows: int, cols: int): ... def set(self, i: int, j: int, val: float) -> None: ... def get(self, i: int, j: int) -> float: ... def add(self, other: 'SparseMatrix') -> 'SparseMatrix': ... def multiply(self, other: 'SparseMatrix') -> 'SparseMatrix': ... def transpose(self) -> 'SparseMatrix': ... ``` **Example:** ``` A = SparseMatrix(3,3); A.set(0,0,1); A.set(2,2,3) B = A.transpose() B.get(0,0) # -> 1 B.get(2,2) # -> 3 C = A.multiply(B) # should give A * A^T ``` ## Follow-ups 1. What is the time complexity of your multiply compared to dense matrix multiplication? 2. When does sparse representation start saving memory vs. a dense array? Give the crossover formula. 3. How would you implement this in CSR (Compressed Sparse Row) format instead of a dict? 4. For a 10^6 x 10^6 matrix with 10^8 non-zero entries, what changes in your approach?

## Problem Design an `OrderMonitor` that tracks state transitions for e-commerce orders. Each order transitions through: `PLACED -> CONFIRMED -> SHIPPED -> DELIVERED` (or `CANCELLED` from any state). The monitor should (1) validate transitions, (2) record history with timestamps, (3) alert if an order has been in `CONFIRMED` state for more than 2 hours without shipping. ```python class OrderMonitor: def transition(self, order_id: str, new_state: str, timestamp: int) -> bool: """Return False if transition is invalid.""" def get_history(self, order_id: str) -> list[dict]: """Return [{state, timestamp}] in order.""" def get_stalled_orders(self, current_time: int) -> list[str]: """Return order_ids stuck in CONFIRMED > 7200 seconds.""" ``` **Example:** ``` transition("O1", "PLACED", 0) -> True transition("O1", "SHIPPED", 10) -> False # skipped CONFIRMED transition("O1", "CONFIRMED", 10) -> True get_stalled_orders(7201) -> ["O1"] ``` ## Follow-ups 1. How do you represent the valid state machine? Adjacency set vs. enum transitions? 2. How would you scale `get_stalled_orders` to millions of active orders without scanning all? 3. What if the same order_id can be reused after cancellation? How does your history model change? 4. How would you expose this as a REST API with webhook callbacks on state changes?

## Problem Build a simplified order matching engine for a single trading pair. Support limit orders (buy/sell at a specific price) and market orders (execute at best available price). Match buy orders against sell orders using price-time priority. Return a list of fills. ```python class Exchange: def place_order(self, order_id: str, side: str, order_type: str, price: float | None, qty: int) -> list[dict]: """ side: 'buy' or 'sell' order_type: 'limit' or 'market' Returns list of fills: [{buy_id, sell_id, price, qty}] """ pass def cancel_order(self, order_id: str) -> bool: ... def get_orderbook(self) -> dict: ... # {bids: [...], asks: [...]} ``` **Example:** ``` place_order("B1", "buy", "limit", 100.0, 10) -> [] # sits in book place_order("S1", "sell", "limit", 99.0, 5) -> [{buy:B1, sell:S1, price:100.0, qty:5}] ``` ## Follow-ups 1. Why does a limit buy match against a sell at 99 when the buy was placed at 100? 2. What data structures back your bid and ask books for O(log n) insert and O(1) best-price lookup? 3. How do you handle partial fills and track remaining quantity? 4. Extend to support stop-loss orders — how do they interact with the matching loop?