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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Microsoft during technical interviews.

Implement lower_bound on unknown-size sorted array

Company: Microsoft

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Given a non-decreasing integer array A of unknown length, accessible only via API get(i) that returns +∞ for i ≥ n, implement lower_bound(target): the smallest index i with A[i] ≥ target, or −1 if none exists. Use exponential search to bracket n and then binary search to find the answer with overall O(log n) time. Handle duplicates, empty array, all values < target, and all values ≥ target. Prove correctness, give a tight upper bound on the number of get calls, and explain how your approach changes if A may be rotated once (with or without duplicates).

Quick Answer: This question evaluates ability to design efficient search algorithms for unknown-length non-decreasing arrays accessed via a limited get(i) API, emphasizing correctness proof and tight query/time complexity bounds.

You are given a non-decreasing (sorted ascending, duplicates allowed) integer array `A`. Implement `lowerBound(A, target)` that returns the smallest index `i` such that `A[i] >= target`. If no such index exists, return `-1`. The intended algorithm models an array of *unknown* length accessed only through an API `get(i)` that returns `A[i]` for valid indices and `+infinity` for `i >= n`. You should bracket the answer with **exponential search** (double an upper bound until the value at that index is `>= target`, which also triggers when the index passes the end of the array) and then **binary search** within the bracket for the first index whose value is `>= target`. Both the running time and the number of `get` probes must be `O(log n)`. Handle these cases: duplicate values, an empty array, every value strictly less than `target` (answer `-1`), and every value already `>= target` (answer `0`). Example: `A = [2, 3, 5, 7, 9]`, `target = 6` -> the first element `>= 6` is `7` at index `3`, so return `3`.

Constraints

0 <= n = len(A) <= 10^6
A is sorted in non-decreasing order (duplicates allowed)
-10^9 <= A[i], target <= 10^9
Must run in O(log n) time and use O(log n) get-style probes
Return -1 when no index satisfies A[i] >= target (including the empty array)

Examples

Input: ([2, 3, 5, 7, 9], 6)

Expected Output: 3

Explanation: First element >= 6 is 7 at index 3. Exponential search brackets (2,4], binary search lands on index 3.

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

Expected Output: 1

Explanation: Duplicates: the smallest index with value >= 2 is index 1 (the first 2), not index 2 or 3.

Input: ([], 4)

Expected Output: -1

Explanation: Empty array: get(0) returns +infinity, so there is no satisfying index; return -1.

Input: ([5], 5)

Expected Output: 0

Explanation: All values >= target: the first element already satisfies A[0] >= target, so return 0.

Input: ([5], 10)

Expected Output: -1

Explanation: Single element strictly less than target: no index satisfies the predicate, return -1.

Input: ([1, 2, 3], 10)

Expected Output: -1

Explanation: All values < target: exponential search runs past the end (get returns +infinity), binary search converges to index n, return -1.

Input: ([4, 5, 6], 1)

Expected Output: 0

Explanation: All values >= target: the guard returns 0 immediately since A[0]=4 >= 1.

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

Expected Output: 1

Explanation: Negatives: first value >= -4 is -3 at index 1.

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

Expected Output: 0

Explanation: All equal to target: the smallest qualifying index is 0.

Input: ([2, 4, 6, 8, 10, 12, 14, 16], 13)

Expected Output: 6

Explanation: Power-of-two length boundary: first value >= 13 is 14 at index 6.

Hints

Frame it as a monotone predicate f(i) = (A[i] >= target), treating A[i] = +infinity for i >= n. f is False for i < i* and True for i >= i*, so you are searching for the first True index.
Phase 1 (exponential search): start hi = 1 and double it until get(hi) >= target. Because out-of-range indices return +infinity, this loop always terminates with f(lo)=False and f(hi)=True, even when the answer is past the end of the array.
Phase 2 (binary search): with the invariant f(lo)=False and f(hi)=True, halve the interval until lo+1 == hi; then hi is the first True index. Cache the value at hi so that if it is +infinity (index passed the end) you can return -1 without an extra probe.

Quick Overview

This question evaluates ability to design efficient search algorithms for unknown-length non-decreasing arrays accessed via a limited get(i) API, emphasizing correctness proof and tight query/time complexity bounds.