Citadel·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Citadel SWE interview with two algorithm-heavy problems, both requiring you to think carefully about string structure and cost optimization under constraints. The problems were harder than I expected and I left unsure how clean my solutions actually were.

Questions Asked (2)

Given a lowercase string and an integer k, find the minimum number of character changes needed to make the string both a palindrome and periodic with period k (i.e., every character equals the one k positions ahead of it).

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one took me a while to untangle.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph where each position i is connected to i+k (periodicity) and i to n-1-i (palindrome), then find connected components. For each component, count character frequencies and change all characters to the most frequent one; sum these changes across all components. This yields the minimum changes because each component must be uniform.

Pro tip: Mention that the graph is a union of cycles and paths, and that the answer is independent of the order of operations. Also, note that the time complexity is O(n) since each character is visited once.

1. Understand the constraints

Clarify that the string must be a palindrome (s[i] = s[n-1-i]) and periodic with period k (s[i] = s[i+k] for all valid i).

2. Model as a graph

Create a graph with n nodes (one per character). Add edges between i and i+k (if i+k < n) and between i and n-1-i (if i < n-1-i).

3. Find connected components

Use union-find or DFS to group indices into connected components. Each component must have all characters equal to satisfy both conditions.

4. Compute minimum changes per component

For each component, count the frequency of each character. The minimum changes for that component is the component size minus the maximum frequency.

5. Sum and return

Sum the minimum changes over all components to get the total minimum number of character changes.

Key Points to Mention

Graph representation: nodes as indices, edges for palindrome and periodicity constraints.
Connected components: each component must be uniform in the final string.
Frequency counting: choose the most frequent character to minimize changes.
Time complexity: O(n) using union-find or DFS, since each index is processed once.
Space complexity: O(n) for the graph or union-find structure.
Edge cases: k >= n (periodicity constraint trivial), n=1, etc.

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

Given n images each active over a date range with an associated filter cost, and a fixed discount price you can apply on any day to replace that day's total cost, find the minimum total processing cost across all days modulo 1,000,000,007.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The modulo at the end threw me off more than it should have.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as minimizing the sum of daily costs after optionally applying a discount on any single day. Use a sweep line over days to compute the total cost per day, then evaluate the savings from applying the discount on each day to find the maximum savings, which gives the minimum total cost.

Pro tip: Clarify the discount mechanics early: whether it replaces the day's total cost with a fixed price (so savings = max(0, total_cost - discount_price)) and whether it can be applied to any day, including days with zero cost. This ensures you handle edge cases correctly and avoid off-by-one errors in date ranges.

1. Clarify problem constraints and discount semantics

Confirm that the discount replaces the day's total cost with a fixed price, that it can be applied to at most one day, and that date ranges are inclusive. Ask about input size to determine if an O(n log n) or O(n) solution is needed.

2. Compute daily total costs using sweep line

Create events for the start and end of each image's active period. Sweep through days in chronological order, maintaining the sum of filter costs for active images, and record the total cost for each day.

3. Calculate baseline total cost and potential savings

Sum all daily costs to get the baseline total. For each day, compute the savings if the discount is applied: max(0, daily_cost - discount_price). Track the maximum savings across all days.

4. Determine minimum total cost and apply modulo

Subtract the maximum savings from the baseline total to get the minimum total processing cost. Apply modulo 1,000,000,007 to the result, ensuring to handle negative values correctly if any.

Key Points to Mention

Sweep line or event-based approach to efficiently compute daily costs without iterating over every day if the date range is large.
Handling inclusive date ranges correctly (e.g., start day included, end day included).
The discount is applied to at most one day, and savings are max(0, daily_cost - discount_price).
Modulo arithmetic: apply modulo after computing the final result, and ensure intermediate sums don't overflow (use 64-bit integers).
Time complexity: O(n log n) due to sorting events, or O(n) if dates are bounded and can be processed with a difference array.
Edge cases: days with zero cost, discount price higher than daily cost, and large date ranges requiring coordinate compression.

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