PreviousNext
AI-assisted engineering/Reviewing AI code

Fix the drop count in an event log merger

Review the AI's codeHard40 min

Your task

Your analytics pipeline merges event logs from many phones. Some phone clocks are wrong, so timestamps arrive out of order. Before it builds sessions, the pipeline drops the fewest events it can so that the rest are in timestamp order, and it reports how many it dropped.

An assistant wrote fewest_drops(timestamps). It is in the editor. It has a bug. Find it and fix it.

Input and output:

  • timestamps: the events' timestamps in milliseconds, in arrival order. Each is a whole number from 0 to 10,000,000,000,000.
  • Return the smallest number of events to drop so that the events left, still in arrival order, have timestamps that never go down.

Rules the tests check:

  • Equal timestamps are in order, so several events from the same millisecond can all stay.
  • An empty list needs no drops.
  • There are at most 200,000 events.

Then, in a sentence or two: how would you catch this kind of bug in review?

Examples

fewest_drops(timestamps: list[int]) -> int
Example 1
Inputfewest_drops([1761480000000, 1761480000005, 1761480000003, 1761480000009, 1761480000012])
Output1
Example 2
Inputfewest_drops([1761480000010, 1761480000020, 1761480000015, 1761480000030, 1761480000025, 1761480000040, 1761480000038, 1761480000050])
Output3
Example 3
Inputfewest_drops([1761480000001, 1761480000002, 1761480000003])
Output0