Rubrik·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Rubrik SWE interview with a graph problem that looks deceptively clean on the surface. The core challenge is building an interval overlap graph and finding its largest connected component efficiently, and they want O(n log n) so brute force is off the table.

Questions Asked (1)

Given n people each with a work interval [start, end], define a graph where two people are connected if their intervals overlap. Find the size of the largest connected component in this graph. Solution should run in O(n log n).

Algorithms & Data Structures

Author's notes

My first instinct was union-find, which is right, but the part I fumbled was figuring out how to avoid the O(n^2) edge enumeration.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort intervals by start time, then sweep through them while maintaining the maximum end time seen so far. When the next interval's start exceeds the current max end, a new component begins; otherwise, it connects to the current component. Track the size of each component and return the maximum.

Pro tip: Clarify that intervals touching at endpoints (e.g., [1,2] and [2,3]) are considered overlapping, as this edge case can change the component structure. Also, mention that the sweep line approach naturally handles this if you use 'start <= max_end' for overlap.

1. Sort intervals

Sort all intervals by their start time in ascending order. This is the key to achieving O(n log n) time complexity.

2. Initialize sweep variables

Set current component size to 0, max component size to 0, and max_end to -infinity. These will track the current component and the overall maximum.

3. Sweep through intervals

For each interval in sorted order, if its start <= max_end, it overlaps with the current component, so increment the component size and update max_end. Otherwise, finalize the previous component, update the global maximum, and start a new component with size 1 and max_end = end.

4. Finalize and return

After the loop, update the global maximum with the last component's size and return it.

Key Points to Mention

Sorting by start time enables a linear sweep to merge overlapping intervals.
The sweep line maintains the maximum end time of the current connected component.
Overlap condition: next interval's start <= current max_end.
Time complexity: O(n log n) due to sorting; space complexity: O(1) extra if sorting in place.
Edge cases: intervals that just touch (e.g., [1,2] and [2,3]) are considered overlapping.
The algorithm effectively finds the largest set of intervals that form a connected chain via overlaps.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.