Amazon·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Amazon SWE coding round with a tricky array search problem where the array length is unknown. The constraint about minimizing get() calls is what makes it interesting, not the search itself.

Questions Asked (1)

You have a sorted integer array of unknown length that can only be accessed via a get(i) method. Find the index of a target value k, minimizing the number of get() calls. Return -1 if not found.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The sorted part makes you think binary search immediately, but the unknown length is the actual problem.

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 binary search within that range. This minimizes get() calls by first doubling the index until get(high) >= k, then binary searching between low and high. Handle edge cases like empty array and target smaller than first element.

Pro tip: Explicitly discuss the trade-off between exponential and binary search, and mention that exponential search is optimal for unbounded arrays because it finds the range in O(log n) get() calls. Also, clarify that you assume get(i) returns a sentinel (e.g., infinity) for out-of-bounds indices, or handle it by catching exceptions.

1. Clarify assumptions and edge cases

Confirm with the interviewer how get(i) behaves for out-of-bounds indices (e.g., returns infinity or throws exception). Discuss edge cases: empty array, target smaller than first element, target larger than all elements.

2. Exponential search to find bounds

Start with low = 0, high = 1. While get(high) < k, set low = high, high = high * 2. This finds a range [low, high] where k might be, using O(log n) get() calls.

3. Binary search within bounds

Perform standard binary search between low and high (inclusive) to find the exact index of k. Use get(mid) to compare and adjust low/high accordingly.

4. Return result and analyze complexity

If found, return the index; else return -1. Analyze time complexity: O(log n) get() calls, and space O(1). Mention that this is optimal for unbounded arrays.

Key Points to Mention

Exponential search (doubling) to find an upper bound where the target could be.
Binary search within the identified range to pinpoint the target index.
Time complexity: O(log n) get() calls, which is optimal for unbounded arrays.
Handling out-of-bounds get() calls: either assume a sentinel value or use exception handling.
Edge cases: empty array, target not present, target at index 0, target larger than all elements.
Comparison with alternative approaches like linear search or pure binary search (which requires known length).

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