Efficient Dataset Sorting or Search | Dataford Interview Questions

Criteo's observability workflows may receive event records in arbitrary timestamp order. Implement a function that sorts the records by timestamp and efficiently returns every event whose timestamp falls within an inclusive range.

Formal Specification

Each event is represented as a two-element list [timestamp, event_id], where timestamp is an integer and event_id is a string. Given a list of events, start_time, and end_time, return a two-element list:

All events sorted in ascending timestamp order. Events with equal timestamps must retain their original relative order.
The sorted events whose timestamps satisfy start_time <= timestamp <= end_time, in sorted order.

You may sort the input list in place. The range result may be empty.

Constraints

0 <= events.length <= 10^5
0 <= events[i][0] <= 10^9
0 <= start_time <= end_time <= 10^9
Event identifiers are non-empty strings
Equal timestamps must preserve input order

Function Signature

def find_events_in_time_range(events, start_time, end_time):

Your question is Efficient Dataset Sorting or Search. 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