Citadel Intern Software Engineer Interview Experience — Merging K Timestamped Price Feeds into a Running Price in Technical Round 3

Citadel SWE intern technical interview. The interviewer was from Citadel Securities.

Problem description:

You are given K data streams (feeds), and each feed is already sorted by timestamp in ascending order. Each event has two fields: a timestamp and a price delta. Requirement: merge the events from all the feeds in time order, and after processing each event, output the current cumulative absolute price (the price starts at 0).

Edge cases:

The interviewer was testing edge cases, so you need to ask about the edge cases very clearly:

Same timestamp: If events in different feeds have the same timestamp, then to keep the result fully deterministic, introduce a tie-breaker rule: order by feed ID (feed index) ascending first; if there is a tie within the same feed, process the events in the order they appear in the original sequence.

Negative deltas: Price deltas are allowed to be negative. The absolute price is a running sum, so just accumulate it directly (i.e. absolute_price += delta), and it can go negative.

Empty feeds: When initializing the min-heap, skip empty feeds directly, so no null pointer or invalid tuple ends up in the heap.

Data structure and algorithm design (Python approach):

Core data structure:

Use Python's priority queue heapq to maintain a min-heap of size at most K. The tuples stored in the heap have the structure (timestamp, feed_index, delta, event_pointer). Putting feed_index into the tuple natively solves the comparison conflict for identical timestamps, with no need to override the comparison operators.

Algorithm logic:

Initialization: go through the K feeds, and if a feed is non-empty, push its first event (feed[0].timestamp, i, feed[0].delta, 0) onto the min-heap. At the same time, initialize a global variable current_price = 0.

Merge-and-track loop: each time, pop (heappop) the smallest event off the top of the heap. Add that event's delta to current_price (current_price += delta). Append the current_price you just computed to the result list. Check whether the feed at that event's feed_index still has more events: if it does, push its next event onto the heap (heappush).

Termination: when the heap is empty, all the feeds have been merged, and you return the sequence of absolute prices.

Complexity analysis:

Time complexity: O(N log K), where N is the total number of events across all feeds and K is the number of feeds. Each heap pop and push is O(log K).

Space complexity: O(K). At any moment the min-heap holds at most K elements (one current unprocessed head element per feed).