Optimize Duplicate Event Detection | Dataford Interview Questions

In Providence telemetry processing, an existing implementation checks every pair of event IDs to find the first duplicate, which is too slow for large inputs. Write an optimized algorithm that returns the index of the first event whose value has appeared earlier in the list.

Formal Specification

Implement a function first_duplicate_event(events) where:

Input: events, a list of integers representing event IDs in arrival order
Output: the index of the first duplicate event occurrence, or -1 if no duplicate exists

A duplicate is any value that has already appeared earlier. “First duplicate” means the duplicate occurrence with the smallest index.

Constraints

1 <= len(events) <= 10^5
-10^9 <= events[i] <= 10^9
Input contains integers only
Return the index of the earliest duplicate occurrence, or -1 if none exists

Function Signature

def first_duplicate_event(events):

Your question is Optimize Duplicate Event Detection. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem