How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Search target in unknown-length sorted array

Quick Overview

This question evaluates algorithm design and implementation skills for search algorithms on array-like interfaces with unknown length, focusing on bounds discovery, handling out-of-bounds sentinels, duplicate elements, and rigorous time and space complexity analysis.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You have read-only access to a sorted, increasing array-like interface of unknown length that supports get(i), which returns a valid integer for in-bounds i and a sentinel (e.g., +∞ or None) when i is out of bounds. Given a target value k, design an algorithm to find the index of k if it exists, otherwise return −1. Optimize time complexity, describe the approach to discover an upper bound, and handle duplicates by returning the first occurrence. Analyze time and space complexity.

Quick Answer: This question evaluates algorithm design and implementation skills for search algorithms on array-like interfaces with unknown length, focusing on bounds discovery, handling out-of-bounds sentinels, duplicate elements, and rigorous time and space complexity analysis.

You are given read-only access to a sorted, strictly-or-non-strictly increasing array-like interface of UNKNOWN length. The only operation available is get(i): it returns the integer at index i for in-bounds i, and a sentinel (here modeled as None / out-of-bounds) for any i beyond the array. Given a target value k, return the index of k if it exists, otherwise return -1. Optimize time complexity (you may not call len()): first discover an upper bound on the valid index range using exponential (galloping) search — start at index 1 and double until get(index) is out of bounds OR get(index) >= k — then binary search within that window. Handle duplicates by returning the FIRST (smallest) index whose value equals k. For this executable console the interface is provided concretely: solution(arr, k) receives the backing list arr and the target k, but the algorithm must behave as if it can only probe via get(i) (no len() short-circuit on the search itself). Return the first index of k, or -1 if k is not present.

Constraints

The array is sorted in non-decreasing order.
Length is unknown; only get(i) may be used to probe (out-of-bounds returns a sentinel).
Values and the target k fit in a 32-bit signed integer.
0 <= conceptual length <= 10^9 (algorithm must not depend on knowing it).
Duplicates may exist; return the smallest index whose value equals k.
Return -1 if k is not present.

Examples

Input: ([1, 2, 3, 5, 8, 13, 21], 13)

Expected Output: 5

Explanation: 13 sits at index 5; exponential search overshoots past it, binary search pins the exact index.

Input: ([1, 2, 3, 5, 8, 13, 21], 4)

Expected Output: -1

Explanation: 4 is absent; binary search lands on the first value >= 4 (which is 5), and since 5 != 4 it returns -1.

Input: ([2, 4, 4, 4, 7, 9], 4)

Expected Output: 1

Explanation: Duplicates of 4 at indices 1,2,3; the leftmost binary search returns the smallest index, 1.

Input: ([10, 20, 30], 10)

Expected Output: 0

Explanation: Target is the first element; returns index 0.

Input: ([10, 20, 30], 30)

Expected Output: 2

Explanation: Target is the last element; exponential search runs out of bounds at index 4, binary search finds index 2.

Input: ([10, 20, 30], 40)

Expected Output: -1

Explanation: Target exceeds every element; all in-bounds values are < 40, so the first value >= 40 is out of bounds — return -1.

Input: ([10, 20, 30], 5)

Expected Output: -1

Explanation: Target is below the minimum; first value >= 5 is 10 at index 0, but 10 != 5 so return -1.

Input: ([], 7)

Expected Output: -1

Explanation: Empty array — every probe is out of bounds; return -1.

Input: ([42], 42)

Expected Output: 0

Explanation: Single-element array containing the target; returns index 0.

Input: ([-5, -3, -3, 0, 2], -3)

Expected Output: 1

Explanation: Negatives with duplicate -3 at indices 1,2; leftmost match is index 1.

Input: ([1, 1, 1, 1, 1], 1)

Expected Output: 0

Explanation: All elements equal the target; the first occurrence is index 0.

Input: ([5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], 19)

Expected Output: 14

Explanation: Longer array forcing several doubling steps in exponential search before the window is binary-searched to index 14.

Hints

You cannot call len(). To bound the search space, start at index 1 and keep doubling (1, 2, 4, 8, ...) until get(index) is out of bounds OR get(index) >= k. The previous index is a safe lower bound.
Out-of-bounds probes should behave like +infinity: they are 'greater than or equal to' any target, so binary search pushes them to the right side.
To return the FIRST occurrence among duplicates, run a 'leftmost' binary search: when value >= k, record the index and keep searching the LEFT half (right = mid - 1).
After binary search lands on the first index with value >= k, verify that value actually equals k — if it's strictly greater (or out of bounds), k is absent, so return -1.

Quick Overview