Applied intuition·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Applied Intuition SWE interview had at least one coding round focused on binary search variants. Pretty standard algorithmic stuff but they threw in a small twist on the classic problem which caught me slightly off guard.

Questions Asked (1)

Given a sorted array of integers that may contain duplicates and a target value, return the first and last index where the target appears. Return [-1, -1] if not found. Walk through both a linear scan solution and a binary search solution.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the brute force since it's easier to explain and they seemed fine with that as a warmup.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then present the linear scan solution with O(n) time, followed by the binary search solution with O(log n) time. Emphasize the trade-offs and why binary search is preferred for large sorted arrays.

Pro tip: Mention that you can use two binary searches (one for first occurrence, one for last) or a modified binary search that finds the range. Also, note that the problem is essentially finding the lower and upper bounds of the target.

1. Clarify the problem and edge cases

Ask if the array can be empty, if the target is guaranteed to be in the array, and if the array is sorted in ascending order. Confirm that duplicates are allowed.

2. Linear scan solution

Iterate through the array, record the first and last index where the target is found. If not found, return [-1, -1]. Time complexity O(n), space O(1).

3. Binary search solution

Use binary search to find the first occurrence (leftmost) and last occurrence (rightmost) of the target. For first occurrence, when target is found, continue searching left; for last, continue searching right.

4. Compare trade-offs

Discuss that linear scan is simple but O(n), while binary search is O(log n) and better for large arrays. Mention that binary search requires the array to be sorted.

5. Test with examples

Walk through an example like [1,2,2,2,3] with target 2 to show both approaches yield [1,3]. Also test edge cases like target not present or array of size 1.

Key Points to Mention

Time complexity: O(n) for linear scan, O(log n) for binary search
Space complexity: O(1) for both
Binary search can be implemented with two separate searches or a single modified search
Handling duplicates: need to find the leftmost and rightmost indices
Edge cases: empty array, target not found, single element array
Importance of sorted array for binary search

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