Find Check-In Time Gaps | Dataford Interview Questions

Foursquare may receive check-ins represented by time intervals during which a user was active at a venue. Given a list of check-in intervals, return the gaps between covered intervals.

Intervals may overlap or touch. Treat overlapping and touching intervals as one continuous covered range. Return only gaps with positive duration, ordered by start time. The output range begins at the earliest check-in start and ends at the latest check-in end, so time before the first check-in and after the last check-in is ignored.

Formal Specification

Implement find_checkin_gaps(checkins), where checkins is a list of two-element lists [start, end]. start and end are integers representing timestamps, and start <= end. Return a list of two-element lists [gap_start, gap_end] for every uncovered interval between the earliest and latest check-in.

Constraints

0 <= len(checkins) <= 10^5
Each interval contains exactly two integers
0 <= start <= end <= 10^9
Input intervals may be unsorted, overlapping, duplicated, or touching

Function Signature

def find_checkin_gaps(checkins):

Your question is Find Check-In Time Gaps. 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