How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

Find earliest common meeting slot | Citadel Coding Question

Find earliest common meeting slot

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given K participants' calendars, each a list of busy intervals [start, end) within a working window [workStart, workEnd], and a meeting duration d minutes, return the earliest interval [t, t + d) that is within every participant's working window and does not overlap any busy interval. Times are integers in minutes from 00:00. Busy intervals are non-overlapping and sorted within each calendar. If no slot exists, return an empty list. Design an algorithm, state its time and space complexity, and describe how you would handle unsorted or overlapping inputs and large K efficiently.

Quick Answer: This question evaluates proficiency with interval manipulation, timeline merging, and algorithmic reasoning for scheduling constraints, measuring competency in handling sorted interval lists, edge-case sanitization, and complexity analysis.

You are given K participants. calendars[i] is a list of busy half-open intervals [start, end) in minutes from 00:00, and work_windows[i] = [workStart, workEnd] represents that participant's available working window, interpreted as [workStart, workEnd). Given an integer d, return the earliest half-open interval [t, t + d) that lies inside every participant's working window and does not overlap any busy interval from any participant. Return the answer as [t, t + d]. If no such slot exists, return []. For the core problem, calendars are intended to be sorted and non-overlapping. As a follow-up, explain how you would normalize unsorted or overlapping calendars first, and how to stay efficient when K is large.

Constraints

1 <= len(calendars) == len(work_windows) <= 100000
0 <= total number of busy intervals across all calendars <= 200000
0 <= start < end <= 1440
0 <= workStart < workEnd <= 1440
1 <= d <= 1440

Examples

Input: ([[[540, 570], [630, 660]], [[555, 585], [615, 645]], [[600, 615]]], [[480, 720], [540, 690], [510, 660]], 15)

Expected Output: [585, 600]

Explanation: The common working window is [540, 660). After merging busy times across all three calendars, the first free gap of length 15 is [585, 600).

Input: ([[[540, 600], [620, 660]], [[530, 610]], [[600, 650]]], [[540, 660], [540, 660], [540, 660]], 10)

Expected Output: []

Explanation: All busy intervals merge to cover the entire common working window [540, 660), so no 10-minute slot exists.

Input: ([[[100, 130], [90, 110], [150, 160]], [[80, 95], [125, 140]]], [[80, 170], [70, 170]], 10)

Expected Output: [140, 150]

Explanation: Normalize the first calendar to [90, 130) and [150, 160). After merging both participants' busy times, the first 10-minute gap is [140, 150).

Input: ([[], []], [[480, 540], [500, 560]], 20)

Expected Output: [500, 520]

Explanation: The common working window is [500, 540) and nobody is busy, so the earliest 20-minute slot starts at 500.

Input: ([[], []], [[100, 120], [130, 150]], 5)

Expected Output: []

Explanation: The participants' working windows do not overlap, so there is no common time to meet.

Input: ([[[10, 20], [20, 30]], [[0, 15], [35, 40]]], [[0, 50], [0, 50]], 5)

Expected Output: [30, 35]

Explanation: Adjacent busy intervals [10, 20) and [20, 30) leave no free gap at 20. After merging all busy time, the first 5-minute gap is [30, 35).

Hints

Any valid meeting must lie inside the intersection of all participants' working windows.
After clipping busy intervals to that common window, treat each calendar as a sorted stream and merge the K streams with a min-heap instead of flattening everything when K is large.

Quick Overview

This question evaluates proficiency with interval manipulation, timeline merging, and algorithmic reasoning for scheduling constraints, measuring competency in handling sorted interval lists, edge-case sanitization, and complexity analysis.