Aggregate partial fills per order in arrival order

Question

Your feed reports partial fills, so one order_id can appear several times, each with the quantity filled that time. You want one row per order carrying its total filled quantity, listed in the order each id was first seen.

events = [(1,100), (2,50), (1,200), (3,75), (2,25)]
-> [(1,300), (2,75), (3,75)]

Return total quantity per id in first-seen order. Aim for $O(1)$ per event.

Accepted Answer

This is dedup with a running sum instead of "drop the copy". Use a dictionary keyed by id: the first time you meet an id it is inserted (fixing its position), and every later copy just adds to its total. A plain Python dict preserves first-insertion order, so no extra bookkeeping is needed for ordering. Tracing the example: 1 enters as 100; 2 enters as 50; the second 1 bumps its total to 300; 3 enters as 75; the second 2 bumps it to 75. Because ids 1, 2, 3 were first seen in that order, the output keeps that order: [(1,300), (2,75), (3,75)]. Time O(n) for one pass, space O(u) in unique ids. g…

Aggregate partial fills per order in arrival order

Your answer

More Coding questions