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

What role is this question designed for?

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

Merge overlapping intervals | OpenAI Coding Question

Merge overlapping intervals

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question LeetCode 56. Merge Intervals – Given a collection of intervals, merge all overlapping intervals into one and return an array of the non-overlapping intervals that cover all the intervals in the input. https://leetcode.com/problems/merge-intervals/description/

Quick Answer: This question evaluates algorithmic problem-solving skills focused on interval manipulation, sorting and merging logic, and time/space complexity analysis within the Coding & Algorithms domain, emphasizing practical application.

Given a list of intervals where each interval is represented as [start, end], merge all overlapping intervals and return a new list of non-overlapping intervals that together cover all the intervals in the input. Two intervals overlap if the start of one interval is less than or equal to the end of the other. Intervals that just touch at an endpoint, such as [1,4] and [4,5], should also be merged. Return the merged intervals sorted by their start values.

Constraints

0 <= len(intervals) <= 10000
intervals[i].length == 2
-10000 <= start <= end <= 10000

Examples

Input: [[1,3],[2,6],[8,10],[15,18]]

Expected Output: [[1,6],[8,10],[15,18]]

Explanation: [1,3] and [2,6] overlap, so they merge into [1,6]. The other intervals do not overlap.

Input: [[1,4],[4,5]]

Expected Output: [[1,5]]

Explanation: The intervals touch at 4, so they are considered overlapping and merge into [1,5].

Input: []

Expected Output: []

Explanation: An empty input has no intervals to merge.

Input: [[5,7]]

Expected Output: [[5,7]]

Explanation: A single interval is already fully merged.

Input: [[-5,-3],[-4,1],[2,2],[2,3]]

Expected Output: [[-5,1],[2,3]]

Explanation: The first two intervals overlap and merge into [-5,1]. The intervals [2,2] and [2,3] also overlap and merge into [2,3].

Input: [[6,8],[1,9],[2,4],[4,7]]

Expected Output: [[1,9]]

Explanation: After sorting, every interval overlaps with the growing merged range, resulting in one interval [1,9].

Solution

def solution(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0][:]]

    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])

    return merged

Time complexity: O(n log n). Space complexity: O(n).

Hints

Sorting the intervals by their start value makes it easier to detect overlaps in one pass.
Keep track of the current merged interval and extend its end when the next interval overlaps.

Quick Overview

This question evaluates algorithmic problem-solving skills focused on interval manipulation, sorting and merging logic, and time/space complexity analysis within the Coding & Algorithms domain, emphasizing practical application.