PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/Rubrik

Find largest connected group of overlapping intervals

Last updated: May 13, 2026

Quick Overview

This question evaluates understanding of interval overlap modeling, graph connectivity, and algorithmic efficiency by requiring mapping time intervals to an undirected communication graph and identifying its largest connected component.

  • hard
  • Rubrik
  • Coding & Algorithms
  • Software Engineer

Find largest connected group of overlapping intervals

Company: Rubrik

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are given `n` people, where person `i` works during an inclusive time interval `[start_i, end_i]`. Define a communication graph: - Each person is a node. - Two people have an (undirected) edge if their work intervals **overlap**, i.e.: \[ \max(start_a, start_b) \le \min(end_a, end_b) \] A **work group** is any set of people whose induced subgraph is **connected** (it does not need to be a clique; connectivity through a chain is enough). For example, if A overlaps B and B overlaps C, then `{A,B,C}` is a valid group even if A does not overlap C. Task: Return the maximum possible size of such a work group (i.e., the size of the largest connected component in this overlap graph). Constraints (typical interview setting): - `n` up to `2e5`. - Times are integers; `start_i <= end_i`. - Your solution should be around `O(n log n)`.

Quick Answer: This question evaluates understanding of interval overlap modeling, graph connectivity, and algorithmic efficiency by requiring mapping time intervals to an undirected communication graph and identifying its largest connected component.

Related Interview Questions

  • Validate BFS order queries on a tree - Rubrik (hard)
Rubrik logo
Rubrik
Feb 12, 2026, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
4
0

You are given n people, where person i works during an inclusive time interval [start_i, end_i].

Define a communication graph:

  • Each person is a node.
  • Two people have an (undirected) edge if their work intervals overlap , i.e.:

max⁡(starta,startb)≤min⁡(enda,endb)\max(start_a, start_b) \le \min(end_a, end_b)max(starta​,startb​)≤min(enda​,endb​)

A work group is any set of people whose induced subgraph is connected (it does not need to be a clique; connectivity through a chain is enough). For example, if A overlaps B and B overlaps C, then {A,B,C} is a valid group even if A does not overlap C.

Task: Return the maximum possible size of such a work group (i.e., the size of the largest connected component in this overlap graph).

Constraints (typical interview setting):

  • n up to 2e5 .
  • Times are integers; start_i <= end_i .
  • Your solution should be around O(n log n) .

Submit Your Answer

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Rubrik•More Software Engineer•Rubrik Software Engineer•Rubrik Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.