How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Citadel.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Citadel during technical interviews.

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.

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.

Loading coding console...

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.

Input: ([1, 3, 5], [1, 3, 5])

Expected Output:

Explanation: All intervals are disjoint single points, so no employee overlaps any other.

Input: ([7], [7])

Expected Output:

Explanation: With one employee, that employee forms a valid team alone.

Input: ([], [])

Expected Output:

Explanation: There are no employees, so no team can be formed.

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

Input: (5, 1)

Expected Output:

Explanation: With one slot, any of the 5 processes can be chosen.

Input: (1, 3)

Expected Output:

Explanation: With only one process available, it is impossible to fill 3 slots without repeating consecutively.

Input: (4, 0)

Expected Output:

Explanation: There is exactly one empty allocation.

Solution

def solution(n, m):
    MOD = 10**9 + 7

    if m == 0:
        return 1
    if n == 0:
        return 0

    return (n % MOD) * pow((n - 1) % MOD, m - 1, MOD) % MOD

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.