def cumulative_prices(feeds: list[list[tuple[int, int]]]) -> list[tuple[int, int]]:
You are given K data feeds. Each feed is a list of events sorted by timestamp, and each event is (timestamp, price_delta). Merge all the feeds in timestamp order and, after each event, output the cumulative price: it starts at 0 and each event adds its delta.
feeds = [
[(1, 5), (4, -2)], # feed 0
[(2, 3), (4, 1)], # feed 1
[(3, -1)], # feed 2
]
cumulative_prices(feeds)
-> [(1, 5), (2, 8), (3, 7), (4, 5), (4, 6)]
# at t=4, feed 0's event comes before feed 1's
Rules from the most detailed report (clarify them with your interviewer, who asked about edge cases in detail):
Variants reported
shared_ptr.Reported rule: the lower feed index goes first, and within one feed the original order is kept. Put the feed index (and position) into the heap entry so the heap enforces it.
Reported: the price is a plain running sum and can go negative; empty feeds are skipped when the heap is built.
Standard explanation — no candidate report records what the interviewer accepted here.
A min-heap holding one head per list: O(k) extra space and O(n log k) time.
Standard explanation — no candidate report records what the interviewer accepted here.
O(N log K) for the heap-based merge; walk through the heap loop and how the wrapper classes are accessed.
Six reports mention this question, most of them Citadel phone screens, and the variant differs by interviewer.
The most detailed is a September 2026 Citadel SWE intern technical round, with a Citadel Securities interviewer. K feeds, each sorted by timestamp, with (timestamp, price delta) events; merge them and output the absolute price after each event, starting from 0. The candidate writes that the interviewer probed edge cases and that they have to be asked about very clearly: ties broken by feed index and then original order, negative deltas allowed, empty feeds skipped. The approach given: a min-heap of at most K entries of (timestamp, feed_index, delta, event_pointer), O(N log K) time and O(K) space.
An earlier phone screen (July 2025) had the same shape: merge sorted [{timestamp, price change}] arrays into [{timestamp, current price}]. A January 2026 phone screen describes a LeetCode 23 variant in which same-timestamp entries are merged first and then the whole array.
Others got the classic merge. One first-round interview (fall 2025) asked for merge k lists without divide-and-conquer merging and in O(k) space instead of O(n). One phone screen was a plain C++ merge of K sorted arrays. Another (November 2025, C++) combined object-oriented design with the algorithm: an abstract class to implement, a wrapper class holding the arrays, type aliases, and every array and object wrapped in shared_ptr. That candidate spent a long time on the scaffolding, the interviewer helped them through it, the algorithm itself went smoothly, and they were asked for the time complexity and to explain the core code. They moved on to the next round. Replies to one report add that Citadel generally lets you choose the language.
You are given K data feeds. Each feed is a list of events sorted by timestamp, and each event is (timestamp, price_delta). Merge all the feeds in timestamp order and, after each event, output the cumulative price: it starts at 0 and each event adds its delta.
feeds = [
[(1, 5), (4, -2)], # feed 0
[(2, 3), (4, 1)], # feed 1
[(3, -1)], # feed 2
]
cumulative_prices(feeds)
-> [(1, 5), (2, 8), (3, 7), (4, 5), (4, 6)]
# at t=4, feed 0's event comes before feed 1's
Rules from the most detailed report (clarify them with your interviewer, who asked about edge cases in detail):
Variants reported
shared_ptr.How do you handle events with the same timestamp in different feeds?
What if a price delta is negative, or a feed is empty?
Merge the lists without divide-and-conquer merging, in O(k) space instead of O(n).
What is the time complexity, and can you explain your core code?
| Approach | Notes |
|---|---|
| Divide-and-conquer pairwise merge | Ruled out in one report, which asked for O(k) space instead of O(n); with array inputs the intermediate merged arrays take O(n) space. |
Common mistakes: Spending a long time reading the provided C++ abstract class and shared_ptr template code before starting the algorithm; Unfamiliarity with shared_ptr usage in C++, which cost time in the object-oriented variant
Interviewer hints: In the C++ object-oriented variant, the interviewer patiently helped the candidate understand the shared_ptr code structure; In the price-feed variant, the interviewer probed edge cases in detail; the candidate advises asking about them very clearly
What passers do: In the C++ object-oriented variant, the candidate worked through the template code with the interviewer's help, wrote the algorithm smoothly, and moved on to the next round
Edge cases probed: Events with the same timestamp across feeds (tie rule: feed index, then original order); Negative price deltas; Empty feeds
Send them this page. It is free to read, no account needed.
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 62 Citadel questions, refreshed monthly from new candidate reports.