Conflating Quote Queue That Keeps Only the Latest Price per Symbol

A market data feed pushes quotes for stock symbols; each quote carries a symbol and that symbol's latest ask price as an integer. Quotes can arrive faster than the consumer processes them. Implement a "smart queue" between the feed and the consumer that: - hands symbols to the consumer in the order in which their updates arrived; - keeps only the most recent price for each symbol, so the consumer never processes a price that a newer quote has already replaced. For example, if quotes arrive as `A=10, B=20, A=11` and the consumer then pops until the queue is empty, it receives `A` exactly once, at `11`, and `B` exactly once, at `20`. Whether `A` comes out before or after `B` is a policy to settle with the interviewer. ### Clarifying Questions - When a symbol that is already waiting receives a new price, does it keep its place in line or move to the back? - Does the feed run on a different thread from the consumer? - What should a pop return when nothing is waiting? - Does a quote carry only the ask price, or other fields that must stay together with it? ### Part 1 — Core queue Implement `push(symbol, ask)` and `pop()`. `pop` returns the next waiting symbol together with its latest ask price, or nothing if no symbol is waiting. Both operations should run in constant time, and memory should not grow with the number of quotes received. ```hint Two questions per push Every push has to answer two things quickly: is this symbol already waiting, and where in line does it belong? Pick a structure for each question and keep them consistent on pop. ``` #### What This Part Should Cover - Conflation semantics: at most one waiting entry per symbol, and the newest price always wins. - Arrival order preserved under the chosen policy, with constant-time push and pop. - Correct clean-up on pop, so that a later quote for the same symbol enters the line again. ### Part 2 — Enum symbols, negative prices and efficiency The interviewer then pushes on the representation: - The set of tradable symbols is fixed and known in advance, so use an enum instead of strings. What changes in your data structures, and what becomes faster? - What if prices can be negative integers? Make the queue handle them correctly, using variant types rather than any special price value. - Make the queue as efficient as you can. ```hint Let the type say absent If every integer can be a real price, no integer is free to mean "nothing waiting". Consider how the type of a slot can carry that information instead. ``` #### What This Part Should Cover - How enum symbols change the containers: indexing instead of hashing, and preallocated fixed-size storage. - A representation of "no pending price" that cannot collide with any legal price. - Memory layout, allocation behavior and per-operation cost of the final design. ### What a Strong Answer Covers - Correct semantics under the clarified ordering policy, including repeated updates to one symbol. - Constant-time operations and memory bounded by the number of symbols, not the number of quotes. - Type-driven design: enums instead of strings, and types rather than sentinel values to express absence. - Awareness of where standard containers allocate and how to keep allocation off the hot path. ### Follow-up Questions - If you keep the line of symbols in a `std::list`, what does each push allocate, and how would you avoid allocating on the hot path? - How would you make the queue safe with the feed on one thread and the consumer on another? - Under the move-to-back policy, what can happen to a symbol that is quoted continuously, and does the same risk exist if symbols keep their place? - How would you carry several kinds of market data message (for example quotes and trades) through one queue without string type tags?