Keep the latest version of each amended fill

Question

Your fills feed sends an event (fillid, payload) whenever a fill is booked, and re-sends the same fillid with an updated payload each time the fill is amended (price correction, quantity change). Downstream you want the final version of every fill, and you want them ordered by where each fill's last amendment appeared. Return one entry per id carrying its last payload, ordered by the position of that last occurrence. Aim for O(1) per event.

Accepted Answer

"Keep the first occurrence" is a set; "keep the last occurrence, in last-occurrence order" is a dictionary with a move-to-end trick. In Python a plain dict remembers insertion order, so if you delete an id before re-inserting it, the id jumps to the back with its newest payload. Tracing the example: after (1,"a") and (2,"b") the dict is {1:"a", 2:"b"}. (1,"c") deletes id 1 then re-adds it, giving {2:"b", 1:"c"}. (3,"d") appends 3. (2,"e") moves 2 to the back with payload "e", giving {1:"c", 3:"d", 2:"e"}, exactly the target. Delete plus insert on a dict are both O(1) expected, so the pass is …

Keep the latest version of each amended fill

Your answer

More Coding questions