How should I practice Portfolio Tickers with Constant-Time Random Pick?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Citadel phone screen problems in FastPrep.

Is Portfolio Tickers with Constant-Time Random Pick associated with Citadel?

FastPrep tags this as a Citadel phone screen coding practice problem when the problem catalog has that company and stage context.

Portfolio Tickers with Constant-Time Random Pick

Citadel● MediumFULLTIMEPHONE SCREEN

Problem statement

Source note: In a Citadel technical phone screen, the coding question was a portfolio of ticker symbols with three methods, add a ticker, remove a ticker and pick one at random, each required to run in constant time. Two follow-ups asked how to pick at random when each ticker has a weight, and how to pick at random when the symbols arrive as a stream. The report gives no signature, examples or limits.

Practice choices: the operation-list format; each pick carries a number r that stands in for the random draw; tickers sit in numbered slots, a new ticker goes to the last slot, and a removal moves the last ticker into the freed slot; a pick returns slot r mod size; adding a ticker that is already there and removing one that is absent do nothing; the two follow-ups are discussed in the editorial but not judged; and the size limits are ours. All three examples are ours.

The judged task matches the report at about 70%.

Build a portfolio of stock ticker symbols that supports three operations, each in constant time on average: add a ticker, remove a ticker, and pick a random ticker.

To make the random pick testable, the portfolio keeps its tickers in numbered slots 0, 1, ..., size - 1, and every pick comes with a number r that stands in for the random draw. Process the rows of operations in order:

["add", ticker]: if ticker is not in the portfolio, put it in a new slot at the end (slot size). If it is already there, do nothing.
["remove", ticker]: if ticker is in slot j, move the ticker from the last slot into slot j and then delete the last slot. If ticker was itself in the last slot, just delete that slot. If ticker is not in the portfolio, do nothing.
["pick", r]: return the ticker in slot r mod size.

Return the answers of all "pick" rows, in order.

If r is chosen uniformly from 0 to size - 1, every ticker is equally likely to be picked. The slot rules are exactly what a constant-time design does, so they also fix which ticker each r selects.

Follow-ups to discuss (not judged):

Each ticker has a positive weight, and a pick should return a ticker with probability proportional to its weight. How do you support add, remove and pick?
The tickers arrive as a stream that is too long to store, and you must return one ticker chosen uniformly from everything seen so far. How do you do it in constant memory?

Function

runPortfolio(operations: String[][]) → String[]

Examples

Example 1

operations = [["add","AAPL"],["add","MSFT"],["add","GOOG"],["pick","4"],["remove","AAPL"],["pick","0"],["pick","1"],["add","NVDA"],["pick","5"]]return = ["MSFT","GOOG","MSFT","NVDA"]

After three adds the slots are [AAPL, MSFT, GOOG]. 4 mod 3 = 1, so the first pick returns "MSFT".
Removing AAPL from slot 0 moves the last ticker, GOOG, into slot 0. The slots are now [GOOG, MSFT], so picks 0 and 1 return "GOOG" and "MSFT".
Adding NVDA gives [GOOG, MSFT, NVDA], and 5 mod 3 = 2 returns "NVDA".

Example 2

operations = [["add","TSLA"],["add","TSLA"],["remove","AMZN"],["pick","1"],["add","AMZN"],["remove","TSLA"],["pick","7"]]return = ["TSLA","AMZN"]

The second add of TSLA does nothing because it is already in the portfolio, and removing AMZN does nothing because it is not there yet. So the first pick sees one slot, and 1 mod 1 = 0 returns "TSLA". After AMZN is added and TSLA is removed, only AMZN is left.

Example 3

operations = [["add","A"],["add","B"],["add","C"],["remove","C"],["add","D"],["pick","2"],["remove","A"],["pick","0"],["pick","3"]]return = ["D","D","B"]

Removing C, which is in the last slot, just drops that slot. D then takes slot 2, so pick 2 returns "D". Removing A moves D into slot 0, giving [D, B]; pick 0 returns "D" and 3 mod 2 = 1 returns "B".

Constraints

1 <= operations.length <= 2000
Each row has exactly 2 entries. The first is "add", "remove" or "pick".
For "add" and "remove", the ticker has 1 to 5 uppercase English letters.
For "pick", r is a decimal integer with no leading zeros and 0 <= r <= 10^9.
Every "pick" happens while the portfolio holds at least one ticker.