Amazon·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Amazon SWE interview with a pretty tricky binary search variant. The problem had enough wrinkles to keep me on my toes and I left unsure whether I'd handled all the edge cases cleanly.

Questions Asked (1)

You have a sorted, increasing array of unknown length. The only access you have is a get(i) call that returns the value at index i, or a sentinel like infinity if i is out of bounds. Given a target value, find its index or return -1. Optimize for time, handle the case where you don't know the upper bound, and return the first occurrence if there are duplicates.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The unknown length part is what got me initially.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use exponential search to find a range where the target might exist, then apply binary search within that range. For duplicates, modify the binary search to find the first occurrence by continuing to search left when the target is found.

Pro tip: Exponential search is optimal for unbounded arrays, but be prepared to discuss its time complexity (O(log n)) and why it's better than linear scan or binary search with a fixed upper bound. Also, mention edge cases like empty array or target not present.

1. Clarify assumptions and edge cases

Confirm that the array is sorted in increasing order, may contain duplicates, and that get(i) returns infinity for out-of-bounds indices. Discuss handling of empty array and target not found.

2. Find bounds using exponential search

Start with index 1 and double it until get(index) >= target or infinity is returned. This gives a range [index/2, index] where the target may exist.

3. Perform binary search within bounds

Apply binary search on the identified range to find the target. If the target is not found, return -1.

4. Adapt for first occurrence

When the target is found, continue searching leftwards to find the first occurrence. This can be done by adjusting the binary search to not stop at the first match.

5. Analyze complexity and trade-offs

Explain that exponential search takes O(log n) time and O(1) space. Discuss why this is optimal for unbounded arrays and compare with alternatives like linear scan.

Key Points to Mention

Exponential search to find bounds in O(log n) time
Binary search for exact index, modified for first occurrence
Handling of out-of-bounds via sentinel infinity
Time complexity: O(log n) for exponential + binary search
Space complexity: O(1) iterative approach
Edge cases: empty array, target not present, duplicates

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