Alert Using Same Key-Card Three or More Times in a One Hour Period - Video Solutions

Problem Overview: Given employee names and key-card usage times, detect employees who used their card three or more times within any one-hour window. Return the employee names that trigger the alert, sorted lexicographically.

Approach 1: Sliding Window with Minute Conversion (O(n log n) time, O(n) space)

Group all access times by employee using a hash table. Convert each HH:MM timestamp into total minutes (hour * 60 + minute) so time comparisons become simple integer differences. For every employee, sort their access times using sorting. Then scan the sorted list with a small sliding window: if times[i] - times[i-2] <= 60, three accesses occurred within one hour and the employee triggers an alert. This works because the sorted order ensures the smallest possible window for any three consecutive entries. The approach is efficient and easy to reason about during interviews.

Approach 2: Heap-Based Tracking (O(n log n) time, O(n) space)

Maintain a min-heap of timestamps per employee. As each access event is processed, convert the time to minutes and push it into that employee's heap. Continuously remove entries older than 60 minutes compared with the current time. If the heap size reaches three, the employee has used their card three times within the one-hour window and should be flagged. The heap structure keeps timestamps ordered automatically while discarding outdated entries efficiently. This approach is useful in streaming scenarios where events arrive chronologically rather than being processed in batches.

Recommended for interviews: The sliding window with minute conversion is the expected solution. It demonstrates good use of grouping, sorting, and window scanning. A brute-force comparison of every triplet would be inefficient, but the sorted sliding window reduces the check to constant work per element. Interviewers usually look for the insight that only three consecutive timestamps need to be compared after sorting.