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 Nextdoor.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Nextdoor during technical interviews.

Merge overlapping weekly time intervals | Nextdoor Coding Question

Merge overlapping weekly time intervals

Company: Nextdoor

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of time intervals representing meetings. Each interval is a pair of strings in the format: - `"<Day> <H>:<MM>"` (24-hour time) - `<Day>` is one of `Mon, Tue, Wed, Thu, Fri, Sat, Sun` - Examples: `"Mon 9:00"`, `"Mon 13:00"`, `"Tue 09:30"` Example input: ```text [["Mon 9:00", "Mon 13:00"], ["Mon 11:00", "Mon 16:00"]] ``` Two intervals overlap if they occur on the same day and their time ranges intersect (endpoints may be treated as overlapping, i.e., `[9:00, 13:00]` overlaps `[13:00, 14:00]`). Task: 1. Parse the strings into comparable time values. 2. Merge all overlapping intervals (per day) and return the merged list. Output requirements: - Return intervals in the same string format. - Sort output by day-of-week (Mon→Sun), then by start time. Clarify/assume: - All intervals start < end. - Intervals may span different days, but each individual interval’s start and end are on the same day. - Input size can be large enough that an efficient solution is expected (better than \(O(n^2)\)).

Quick Answer: This question evaluates the ability to parse weekday and 24-hour time strings, reason about interval overlap, and apply efficient merging and sorting techniques for time-based intervals.

You are given a list of time intervals representing meetings. Each interval is a pair of strings in the format `"<Day> <H>:<MM>"` (24-hour time), where `<Day>` is one of `Mon, Tue, Wed, Thu, Fri, Sat, Sun` (e.g. `"Mon 9:00"`, `"Mon 13:00"`, `"Tue 09:30"`). Two intervals overlap if they occur on the same day and their time ranges intersect. Endpoints are treated as overlapping, i.e. `[9:00, 13:00]` overlaps `[13:00, 14:00]`. Parse the strings into comparable time values, merge all overlapping intervals (per day), and return the merged list. Output requirements: - Return intervals in the same string format `"<Day> <H>:<MM>"`, with the hour unpadded and the minute zero-padded to two digits (e.g. `"Mon 9:00"`, `"Tue 9:30"`). - Sort the output by day-of-week (Mon -> Sun), then by start time. Assumptions: - Every interval has start < end. - Each individual interval's start and end are on the same day. - The input can be large, so an efficient (better than O(n^2)) solution is expected.

Constraints

0 <= number of intervals <= 10^5
Each interval is a pair of strings in the format "<Day> <H>:<MM>" (24-hour).
<Day> is one of Mon, Tue, Wed, Thu, Fri, Sat, Sun.
For every interval, start < end and both endpoints are on the same day.
Touching endpoints count as overlapping (e.g. [9:00,13:00] overlaps [13:00,14:00]).

Examples

Input: ([['Mon 9:00', 'Mon 13:00'], ['Mon 11:00', 'Mon 16:00']],)

Expected Output: [['Mon 9:00', 'Mon 16:00']]

Explanation: The two Monday intervals overlap (11:00 falls inside [9:00,13:00]), so they merge into one spanning [9:00,16:00].

Input: ([['Mon 9:00', 'Mon 13:00'], ['Mon 13:00', 'Mon 14:00']],)

Expected Output: [['Mon 9:00', 'Mon 14:00']]

Explanation: Touching endpoints are treated as overlapping, so [9:00,13:00] and [13:00,14:00] merge into [9:00,14:00].

Input: ([['Mon 9:00', 'Mon 10:00'], ['Mon 11:00', 'Mon 12:00']],)

Expected Output: [['Mon 9:00', 'Mon 10:00'], ['Mon 11:00', 'Mon 12:00']]

Explanation: There is a gap between 10:00 and 11:00, so the intervals do not overlap and both are kept.

Input: ([['Tue 09:30', 'Tue 10:30'], ['Mon 09:00', 'Mon 17:00'], ['Tue 10:00', 'Tue 11:00']],)

Expected Output: [['Mon 9:00', 'Mon 17:00'], ['Tue 9:30', 'Tue 11:00']]

Explanation: Intervals are grouped per day and sorted Mon before Tue. The two Tuesday intervals overlap (10:00 < 10:30) and merge into [9:30,11:00]; note the output strips the input zero-padding on the hour.

Input: ([],)

Expected Output: []

Explanation: Empty input yields an empty result.

Input: ([['Wed 8:00', 'Wed 9:00']],)

Expected Output: [['Wed 8:00', 'Wed 9:00']]

Explanation: A single interval is returned unchanged.

Input: ([['Sun 20:00', 'Sun 22:00'], ['Mon 9:00', 'Mon 13:00'], ['Mon 11:00', 'Mon 16:00'], ['Mon 16:00', 'Mon 18:00']],)

Expected Output: [['Mon 9:00', 'Mon 18:00'], ['Sun 20:00', 'Sun 22:00']]

Explanation: The three Monday intervals chain-merge ([9:00,13:00] overlaps [11:00,16:00], which touches [16:00,18:00]) into [9:00,18:00]. Sunday sorts last, after Monday.

Hints

Convert each timestamp to an absolute comparable value: day index (Mon=0 .. Sun=6) plus minutes-since-midnight (h*60+m). This lets you sort and compare intervals numerically.
Sort all intervals by (day, start). After sorting, a simple linear sweep merges overlaps: keep extending the current merged interval while the next interval is on the same day and its start is <= the current end (use <= so touching endpoints merge).
When formatting back to strings, the hour is unpadded but the minute must be zero-padded to two digits, e.g. 9*60+5 -> "9:05". Sorting first guarantees the Mon->Sun, then start-time output order.

Quick Overview

This question evaluates the ability to parse weekday and 24-hour time strings, reason about interval overlap, and apply efficient merging and sorting techniques for time-based intervals.