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.

Compute max team size with a core interval

Company: Citadel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

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

Quick Answer: 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

  1. For a fixed core interval [s, e], another interval overlaps it exactly when its start is <= e and its end is >= s.
  2. 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].

Hints

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

Loading coding console...