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 Take-home Project rounds at MathWorks.

What role is this question designed for?

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

Count interval intersections | MathWorks Coding Question

Count interval intersections

Company: MathWorks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

##### Question For a list of n segments, where each segment i has start[i] and end[i], compute for every segment the count of other segments that intersect it (share at least one common point). Return an array counts where counts[i] is the number of intersections for segment i. Constraints: 1 ≤ n ≤ 10^5, 1 ≤ start[i] ≤ end[i] ≤ 10^9.

Quick Answer: This question evaluates understanding of interval relationships, efficient counting under large constraints, and algorithmic complexity analysis for overlapping ranges.

For a list of `n` segments where segment `i` spans `[start[i], end[i]]`, compute for every segment the number of OTHER segments that intersect it (share at least one common point, i.e. they overlap or merely touch at an endpoint). Return an array `counts` where `counts[i]` is the intersection count for segment `i`. Two segments `[a, b]` and `[c, d]` intersect iff `a <= d` and `c <= b`. Example: `start = [1, 2, 5]`, `end = [3, 4, 6]` -> `[1, 1, 0]`. Segment 0 `[1,3]` overlaps segment 1 `[2,4]`; segment 1 also overlaps segment 0; segment 2 `[5,6]` overlaps neither. Constraints: `1 <= n <= 10^5`, `1 <= start[i] <= end[i] <= 10^9`. An O(n^2) pairwise check is too slow for the upper bound; aim for O(n log n).

Constraints

1 <= n <= 10^5
1 <= start[i] <= end[i] <= 10^9
Two segments intersect if they share at least one point, including touching at a single endpoint.
A segment is not counted as intersecting itself.

Examples

Input: ([1, 2, 5], [3, 4, 6])

Expected Output: [1, 1, 0]

Explanation: [1,3] and [2,4] overlap (each other); [5,6] is disjoint from both.

Input: ([1], [5])

Expected Output: [0]

Explanation: Single segment has no others to intersect.

Input: ([1, 1, 1], [10, 10, 10])

Expected Output: [2, 2, 2]

Explanation: Three identical segments each intersect the other two.

Input: ([1, 4, 7], [2, 5, 8])

Expected Output: [0, 0, 0]

Explanation: Disjoint segments [1,2], [4,5], [7,8] never touch (gaps between them).

Input: ([1, 2, 3, 4], [4, 3, 5, 6])

Expected Output: [3, 2, 3, 2]

Explanation: Segments [1,4],[2,3],[3,5],[4,6]. [1,4] meets all three (touches [4,6] at 4); [2,3] misses [4,6]; [3,5] meets all; [4,6] misses [2,3].

Input: ([5, 1], [6, 10])

Expected Output: [1, 1]

Explanation: [5,6] lies inside [1,10], so they intersect.

Input: ([1, 3], [3, 5])

Expected Output: [1, 1]

Explanation: [1,3] and [3,5] touch at the single point 3, which counts as an intersection.

Hints

Counting intersecting pairs directly is hard; count the complement instead. For segment i, every other segment either intersects it, lies entirely to its left (its end < start[i]), or lies entirely to its right (its start > end[i]).
So counts[i] = (n - 1) - (# segments with end < start[i]) - (# segments with start > end[i]).
Sort all ends and all starts once. Use binary search (bisect) to count how many ends are < start[i] and how many starts are > end[i] in O(log n) per query, giving O(n log n) overall.
Watch the boundary: touching counts as intersecting, so use strict '<' for the left group (end < start[i]) and strict '>' for the right group (start > end[i]); equality keeps the segment in the intersecting set.

Quick Overview

This question evaluates understanding of interval relationships, efficient counting under large constraints, and algorithmic complexity analysis for overlapping ranges.