Citadel·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Citadel software engineer interview with a binary search problem. Clean algorithmic question, nothing too wild, but the O(log n) constraint is the whole point so you better not miss it.

Questions Asked (1)

Given a sorted array of integers and a target value K, return the index range [first, last] representing the first and last positions where K appears. If K isn't in the array, return [-1, -1]. Your solution must run in O(log n).

Algorithms & Data Structures

Author's notes

The O(log n) requirement is basically screaming 'binary search' at you, but the tricky part is you need two separate searches: one to find the leftmost occurrence and one for the rightmost.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use two separate binary searches: one to find the leftmost occurrence of K and another to find the rightmost occurrence. Modify the standard binary search to continue searching even after finding K, moving left for the first occurrence and right for the last. This ensures O(log n) time and handles duplicates correctly.

Pro tip: Mention that you can avoid code duplication by writing a helper function that takes a boolean flag to decide whether to find the first or last occurrence. This shows clean code practices and awareness of maintainability.

1. Clarify and confirm requirements

Restate the problem to ensure understanding: sorted array, target K, return [first, last] indices or [-1, -1], O(log n) required. Ask about edge cases like empty array or K not present.

2. Design binary search for first occurrence

Perform binary search; when arr[mid] == K, record mid as a potential answer and move the right pointer to mid-1 to search for an earlier occurrence. Continue until left > right.

3. Design binary search for last occurrence

Similarly, when arr[mid] == K, record mid and move the left pointer to mid+1 to search for a later occurrence. Continue until left > right.

4. Handle absence of K

If either search fails to find K, return [-1, -1]. Otherwise, return the two recorded indices.

5. Analyze complexity and test

State that each binary search is O(log n), so overall O(log n) time and O(1) space. Walk through examples including duplicates and edge cases.

Key Points to Mention

Time complexity: O(log n) because two binary searches, each O(log n).
Space complexity: O(1) iterative implementation.
Handling duplicates: modified binary search continues after finding K.
Edge cases: empty array, K smaller than all elements, K larger than all elements, single element array.
Avoiding integer overflow in mid calculation: use left + (right - left) / 2.
Code reusability: helper function with a flag to find first or last occurrence.

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