Constant-Time Ticker Portfolio With Uniform, Weighted and Streaming Random Picks

Design and implement a portfolio of stock ticker symbols (strings such as `AAPL`) that supports three operations, each in constant time: - `add(ticker)`: put a ticker into the portfolio; - `remove(ticker)`: take a ticker out of the portfolio; - `random_pick()`: return one ticker currently in the portfolio, with every held ticker equally likely. The interviewer then extends the problem twice: first each ticker carries a weight and picks must follow the weights, then the symbols arrive as a stream and you must pick one at random from it. ### Clarifying Questions - Is the portfolio a set, so that adding a ticker it already holds does nothing, or can a ticker be held twice? - What should `remove` of a ticker that is not held, and `random_pick` on an empty portfolio, do: return a status, return `None`, or raise? - Is expected constant time (hash-table average) acceptable, or is worst-case constant time required? - Is the portfolio used from a single thread, or must it be safe for concurrent callers? ### Part 1 — Constant-time add, remove and uniform pick Implement the class so that all three operations run in constant time and `random_pick` returns each held ticker with probability 1/n, where n is the number of tickers held. ```hint What a hash set cannot do A hash set already gives constant-time add and remove. Ask what it lacks for a constant-time uniform pick, and which other structure has exactly that property. ``` ```hint Deleting without a hole If the tickers live in an array, think about how to remove one from the middle without shifting everything after it. ``` #### What This Part Should Cover - The pair of structures that together give all three bounds, and the invariant linking them - Constant-time deletion from the middle, including the case where the removed ticker is the last element - Why the pick is exactly uniform, and the duplicate, missing-ticker and empty-portfolio cases ### Part 2 — Weighted random pick Each ticker now has a positive weight given when it is added. `random_pick` must return ticker t with probability w(t) divided by the total weight of the tickers held. Explain what this costs for add, remove and pick, and whether all three can still be constant time. ```hint Weights as segments Lay the weights end to end on a line and draw one uniform number along its length. Ask how to find the segment it lands in quickly, and what has to change when a segment is inserted or removed. ``` #### Clarifying Questions for this Part - Are weights integers or real numbers, and is there a known bound on the largest weight or on the ratio between the largest and the smallest? - Can a ticker's weight change after it is added? - Which happens far more often: picks, or changes to the portfolio? #### What This Part Should Cover - A correct proportional-sampling method and an argument for its correctness - The cost of each operation for the chosen structure, and an alternative suited to a different mix of picks and updates - When near-constant time is achievable (for example with bounded weights), and at what price - Zero weights, real-valued weights and rounding ### Part 3 — Random pick from a stream Ticker symbols now arrive one at a time on a stream of unknown length that is too long to store. At any moment you must be able to return one symbol chosen uniformly at random from everything seen so far, using constant memory. ```hint Decide on arrival Keep a single candidate. Ask with what probability the i-th arrival should replace it so that, after n arrivals, each of them is the candidate with the same probability. ``` #### Clarifying Questions for this Part - Is "uniform" over stream positions, so that a symbol that arrived three times is three times as likely, or over distinct symbols? - Is one sample enough, or are k samples needed? #### What This Part Should Cover - The replacement rule and a proof that every arrival ends up chosen with probability 1/n - Constant memory and per-item cost, with an answer available at every moment - The distinct-symbol variant and the extension to k samples ### What a Strong Answer Covers - Working code for Part 1 with the index bookkeeping right in every removal case - Honest complexity claims: expected versus worst-case constant time, and what weights really cost - A probability argument for each part, not only code - Edge cases across the parts: duplicates, absent tickers, an empty portfolio, zero or real-valued weights, and a seeded random source for tests ### Follow-up Questions - Using the Part 1 structure, how would you return k distinct tickers uniformly at random in O(k) time? - In the stream, each symbol arrives with a weight. How do you sample one symbol in proportion to its weight in a single pass? - How would you make the Part 1 class safe for many concurrent readers and writers? - How would you test that `random_pick` is actually uniform?