Compute max team size with a core interval

Quick Overview

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.

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

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).

Overview: 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.

Part 1: Maximum Team Size With a Core Employee

You are given two equal-length arrays startTime and endTime. Employee i works during the inclusive interval [startTime[i], endTime[i]]. A team is valid if you can choose one employee as the core employee and that core employee's interval intersects every other chosen team member's interval. Two intervals [a, b] and [c, d] intersect if max(a, c) <= min(b, d). Return the maximum possible size of a valid team. If there are no employees, return 0.

Constraints

0 <= n <= 2 * 10^5
len(startTime) == len(endTime) == n
0 <= startTime[i] <= endTime[i] <= 10^9
Your algorithm should be better than O(n^2)

Examples

Input: ([2, 5, 6, 8], [5, 6, 10, 9])

Expected Output:

Explanation: Choosing employee 2 with interval [5, 6] gives a team of size 3: [2,5], [5,6], and [6,10].

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

Expected Output:

Explanation: The middle interval [2,3] intersects both neighbors because endpoint touching counts as overlap.

Hints

For a fixed core interval [s, e], another interval overlaps it exactly when its start is <= e and its end is >= s.
Sort all start times and all end times separately. Then use binary search to count how many intervals can overlap each employee's interval.

Part 2: Count Valid Process Allocations With No Equal Adjacent Slots

You must assign processes to time slots. There are n distinct processes labeled 1 through n, and you need an allocation sequence of length m. A sequence is valid if no process appears in two consecutive time slots. In other words, for every t > 1, assignment[t] != assignment[t - 1]. Return the number of valid sequences modulo 1000000007. If m = 0, the empty sequence counts as one valid allocation.

Constraints

0 <= n <= 10^9
0 <= m <= 10^18
The answer must be returned modulo 10^9 + 7
The solution should handle very large m efficiently

Examples

Input: (3, 2)

Expected Output:

Explanation: Choose any of 3 processes for the first slot, then 2 different processes for the second slot: 3 * 2 = 6.

Input: (2, 4)

Expected Output:

Explanation: Only two alternating sequences are possible: [1,2,1,2] and [2,1,2,1].

Approach

This counts length-m sequences over n distinct processes where no two adjacent slots hold the same process — a standard chromatic-style counting argument. Counting by position. Build the sequence left to right: - The first slot can be any of the n processes. - Every later slot can be anything except whatever sat in the immediately previous slot, giving n - 1 choices each. Multiplying the independent per-slot choices gives the closed form: Edge cases (handled explicitly): - m == 0 → returns 1: the empty sequence is the single valid allocation. - n == 0 with m >= 1 → returns 0: no process exists to fill a slot. - n == 1, m == 1 → 1 * pow(0, 0) = 1 (one slot, one way). - n == 1, m > 1 → 1 * pow(0, m-1) = 0: the lone process would have to repeat. Why it stays fast. Constraints allow m up to 10^18, so the power can't be looped. The code uses Python's built-in pow((n-1) % MOD, m - 1, MOD), which does fast modular exponentiation by squaring in O(log m) multiplications, each taken mod 10^9 + 7. The bases are reduced mod MOD first (n % MOD, (n-1) % MOD) so the arithmetic stays within machine-friendly ranges before the final % MOD. The result is the formula above, evaluated entirely under the modulus.

Time complexity: O(log m)

Space complexity: O(1)

Hints

How many choices do you have for the first slot? How many choices remain for each later slot?
Once you derive the formula, use fast modular exponentiation instead of multiplying in a loop.

Approach

Key reframing. A non-core interval [c, d] intersects the core [s, e] exactly when max(s, c) <= min(e, d), which simplifies to two independent conditions: c <= e (it starts no later than the core ends) and d >= s (it ends no earlier than the core starts). So for a fixed core, the answer is "how many intervals satisfy both start <= e and end >= s."

Counting with sorted arrays + binary search. Sort all start times into starts and all end times into ends once (O(n log n)). For each candidate core [s, e]:

bisect_right(starts, e) → number of intervals with start <= e.
bisect_left(ends, s) → number of intervals with end < s (i.e. those that fail the end >= s test).

The intervals that intersect the core are exactly start <= e minus those that also have end < s. This subtraction is valid because the two excluded groups (start > e and end < s) are disjoint — an interval can't have start > e >= s > end since start <= end. So overlaps = bisect_right(starts, e) - bisect_left(ends, s) is precise inclusion–exclusion.

Why it's correct. Every valid team is pinned by some core employee, and trying each employee as the core covers all teams; the maximum over cores is the answer. The core always counts itself (start <= e and end >= s both hold), so the result is >= 1 whenever n >= 1. Empty input short-circuits to 0.

This beats the required O(n^2) brute force: instead of comparing every pair, each core is answered in O(log n) via two binary searches.

Time complexity:

O(n log n)

Space complexity:

O(n)