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.

Compute intersections for each segment | MathWorks Coding Question

Quick Overview

This question evaluates algorithmic problem-solving, interval reasoning, and complexity-analysis skills by requiring an efficient method to count how many other segments intersect each interval while accounting for edge cases like equal endpoints and duplicate segments.

Compute intersections for each segment

Company: MathWorks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given n segments on a number line. Segment i is [startsAt[i], endsAt[i]] (inclusive), with 1 ≤ n ≤ 1e5 and 1 ≤ startsAt[i] ≤ endsAt[i] ≤ 1e9. For each segment i (0 ≤ i < n), determine how many other segments intersect it. Two segments intersect if they share at least one common point. Return an integer array counts of length n where counts[i] is the number of intersections for segment i. Design an algorithm faster than O(n^ 2) (aim for O(n log n)), explain its time and space complexity, and implement a function countIntersections(int[] startsAt, int[] endsAt). Clarify how you handle equal endpoints and duplicate segments. Example: startsAt = [1, 3], endsAt = [4, 5] → counts = [1, 1] because [1,4] intersects [3,5] at points 3 and 4.

Quick Answer: This question evaluates algorithmic problem-solving, interval reasoning, and complexity-analysis skills by requiring an efficient method to count how many other segments intersect each interval while accounting for edge cases like equal endpoints and duplicate segments.

You are given n segments on a number line. Segment i is the closed interval [startsAt[i], endsAt[i]] (inclusive endpoints), with 1 <= n <= 1e5 and 1 <= startsAt[i] <= endsAt[i] <= 1e9. For each segment i (0 <= i < n), determine how many OTHER segments intersect it. Two segments intersect if they share at least one common point on the number line (touching at a single shared endpoint counts as an intersection, since the intervals are closed). A segment never counts itself. Return an integer array `counts` of length n, where counts[i] is the number of other segments that intersect segment i. Aim for an O(n log n) algorithm rather than the brute-force O(n^2) pairwise scan. Example: startsAt = [1, 3], endsAt = [4, 5] -> counts = [1, 1], because segment [1,4] and segment [3,5] share the points 3 and 4.

Constraints

1 <= n <= 1e5
1 <= startsAt[i] <= endsAt[i] <= 1e9
Segments are closed (inclusive) intervals; touching at one shared endpoint counts as an intersection
A segment does not intersect itself; counts[i] is over the other n-1 segments
Identity is by index, not value: duplicate/identical segments each intersect the others

Examples

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

Expected Output: [1, 1]

Explanation: Segments [1,4] and [3,5] share points 3 and 4, so each intersects exactly one other segment.

Input: ([5], [10])

Expected Output: [0]

Explanation: A single segment has no other segments to intersect.

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

Expected Output: [0, 0]

Explanation: [1,2] and [10,20] are disjoint (2 < 10), so neither intersects the other.

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

Expected Output: [1, 1]

Explanation: [1,3] and [3,5] touch at the shared endpoint 3; closed intervals make this an intersection.

Input: ([2, 2, 2], [2, 2, 2])

Expected Output: [2, 2, 2]

Explanation: Three identical degenerate single-point segments [2,2]; each intersects the other two (identity is by index).

Input: ([1, 2, 3, 4], [10, 9, 8, 7])

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

Explanation: Segments [1,10], [2,9], [3,8], [4,7] are fully nested, so every pair intersects; each counts the other 3.

Input: ([1, 5, 10], [3, 7, 12])

Expected Output: [0, 0, 0]

Explanation: [1,3], [5,7], [10,12] are pairwise disjoint, so no segment intersects any other.

Input: ([1, 2, 100, 50], [10, 3, 200, 60])

Expected Output: [1, 1, 0, 0]

Explanation: [1,10] and [2,3] overlap (count 1 each); [100,200] and [50,60] are isolated from everything (count 0).

Hints

Counting intersections directly is awkward because the overlap condition couples both endpoints. Count the segments that do NOT intersect segment i and subtract from n-1. Two segments fail to intersect iff one lies entirely to the left of the other.
A segment j misses segment i in exactly one of two disjoint ways: j ends strictly before i begins (endsAt[j] < startsAt[i]), or j begins strictly after i ends (startsAt[j] > endsAt[i]). These two groups cannot overlap, so count each independently and add them.
'How many endsAt[j] < startsAt[i]?' and 'how many startsAt[j] > endsAt[i]?' are order-statistic queries. Sort all start values and all end values once, then answer every query with a binary search (lower_bound / upper_bound). Segment i is never in its own left or right group, so query over all n values and rely on the -1 to remove self.
Use STRICT inequalities (< and >) so segments that merely touch at a shared endpoint stay counted as intersecting, matching the inclusive-interval semantics.

Quick Overview