Citadel·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Citadel SWE interview with two algorithmic questions back to back. The first was a geometry-flavored interval problem and the second jumped into combinatorics. Both had a twist that punished naive solutions.

Questions Asked (2)

Given n employees with working-time intervals, find the largest team you can form where one designated 'core' employee's interval overlaps with every other member's interval. Your solution needs to run better than O(n²).

Algorithms & Data Structures

Author's notes

I saw the overlap condition and immediately thought brute force: for each employee try them as core and count overlaps.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the intervals by start time, then use a sweep line with a min-heap to track active intervals. For each interval as the core, the maximum team size is the number of intervals that overlap with it, which can be computed by maintaining the count of active intervals and the maximum end time among them.

Pro tip: Clarify that the core employee is part of the team and that the team size includes the core. Also, mention that if multiple cores yield the same maximum size, any is acceptable.

1. Understand the problem

Restate the problem: Given n intervals, find the largest subset where one interval (the core) overlaps with all others. The core is included in the team.

2. Sort intervals

Sort the intervals by start time. This allows efficient processing with a sweep line.

3. Sweep and maintain active intervals

Iterate through sorted intervals, using a min-heap to store end times of active intervals. Remove intervals that end before the current start. The heap size gives the number of intervals overlapping at the current start.

4. Compute max team size for each core

For each interval as core, the team size is the number of intervals that overlap with it. This can be computed by considering the maximum overlap count during the sweep, but ensure the core is included.

5. Return the maximum

Track the maximum team size found and return it. Optionally, return the core interval if needed.

Key Points to Mention

Time complexity: O(n log n) due to sorting and heap operations.
Space complexity: O(n) for the heap.
Handling edge cases: no overlaps, all intervals overlap, duplicate intervals.
The core must overlap with every other member, but other members need not overlap with each other.
Using a sweep line with a heap efficiently finds the maximum overlap count.
Proof of correctness: the maximum overlap count at any point gives the largest set of intervals that all overlap with a common point, which can serve as the core.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Count the number of sequences of length m over n distinct processes such that no two consecutive positions in the sequence have the same process. Return the answer modulo 10^9 + 7.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one I actually liked.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Derive a recurrence relation: let f(m) be the number of valid sequences of length m. For the first position, there are n choices; for each subsequent position, there are n-1 choices (any process except the one used in the previous position). Thus f(m) = n * (n-1)^(m-1). Compute this modulo 10^9+7 using fast modular exponentiation.

Pro tip: Mention that the problem is equivalent to counting proper colorings of a path graph with n colors, and that the formula can be derived by simple multiplication. Also, note that if m=0, the answer is 1 (empty sequence), which is a common edge case.

1. Understand the problem

Clarify that we need sequences of length m over n distinct processes with no two consecutive equal. Confirm that processes are distinct and order matters.

2. Derive the recurrence

Let f(m) be the count. For the first position, n choices. For each next position, n-1 choices (cannot repeat previous). So f(m) = n * (n-1)^(m-1).

3. Handle edge cases

If m=0, return 1 (empty sequence). If n=1 and m>1, return 0 because you cannot avoid repetition. If n=0 and m>0, return 0.

4. Compute modulo efficiently

Use fast modular exponentiation to compute (n-1)^(m-1) mod (10^9+7), then multiply by n mod MOD. Ensure all operations are modulo MOD.

5. Analyze complexity

Time complexity O(log m) for exponentiation, space O(1). This is optimal for large m.

Key Points to Mention

Recurrence relation: f(m) = n * (n-1)^(m-1)
Edge cases: m=0, n=1, n=0
Modular exponentiation to handle large m
Time and space complexity: O(log m) time, O(1) space
Connection to graph coloring (path graph)
Modulo arithmetic: take mod at each step to prevent overflow

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.