Katkat
Back

Compute max team size with a core interval

CitadelSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates algorithmic problem-solving around interval overlap and time-complexity optimization, measuring the ability to determine the maximum team size given a core interval while reasoning about interval intersections and scalability; it is commonly asked to assess correctness and subquadratic runtime thinking, categorized under Coding & Algorithms and emphasizing practical algorithmic implementation. The follow-up evaluates combinatorics and counting under adjacency constraints with modular arithmetic and efficient handling of large parameters, commonly posed to test recurrence reasoning and scalable counting approaches, falling under combinatorics/dynamic programming and emphasizing conceptual understanding linked to practical algorithmic efficiency.

You are given n employees’ working-time intervals, where employee i works during the inclusive interval [startTime[i], endTime[i]].

You want to form a team such that:

  • The team contains at least one “core employee”.
  • The chosen core employee’s interval intersects (overlaps) with every other team member’s interval.
  • Intervals [a,b] and [c,d] are considered intersecting if they share at least one time point, i.e., max(a,c) ≤ min(b,d).

Return the maximum possible team size.

Example

  • Input:
  • startTime = [2, 5, 6, 8]
  • endTime = [5, 6, 10, 9]
  • Output: 3

Requirements

  • Your solution must be more efficient than O(n²) (assume time limits will fail quadratic solutions).

Follow-up (second question)

Grace Hopper’s scheduling rule: you must assign processes to time slots so that no process occupies two consecutive time slots.

Given:

  • n_processes = n (number of distinct processes, labeled 1..n)
  • n_intervals = m (number of time slots)

Count the number of valid allocations (sequences) of length m over n processes such that:

  • For all t > 1, assignment[t] != assignment[t-1]

Return the count modulo (10^9 + 7).

Example

If n = 3, m = 2, valid sequences include (1,2), (1,3), (2,1), etc., but not (1,1).

Requirements

  • Handle large n, m efficiently (assume you may need near O(log m) or O(m) time, depending on constraints).