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).

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.

How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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

Q: Implement lower_bound on unknown-size sorted array

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Microsoft.

Q: What role is this question designed for?

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

Lower Bound in Unknown-Length Nondecreasing Array via API

Setup

You are given a non-decreasing integer array A of unknown length n. You cannot access A directly; instead, you have an API:

get(i): returns A[i] for 0 ≤ i < n; returns +∞ for all i ≥ n.

We define lower_bound(target) as the smallest index i such that A[i] ≥ target. If no such i exists, return −1.

Task

Implement lower_bound(target) with the following constraints and deliverables:

Algorithm
- Use exponential search to bracket the answer, then binary search to find the exact index.
- Overall time must be O(log n) and the number of get calls should also be O(log n).
Edge cases to handle
- Duplicates in A.
- Empty array (n = 0).
- All values in A < target.
- All values in A ≥ target.
Analysis
- Prove correctness (why the algorithm returns the smallest index with A[i] ≥ target or −1 correctly).
- Give a tight upper bound on the number of get calls (as a function of n and, where natural, of the answer index).
Variant
- Explain how your approach changes if A is non-decreasing but may be rotated once (e.g., [4,5,6,1,2,3]), both without and with duplicates.

Setup

You are given a non-decreasing integer array A of unknown length n. You cannot access A directly; instead, you have an API:

get(i): returns A[i] for 0 ≤ i < n; returns +∞ for all i ≥ n.

We define lower_bound(target) as the smallest index i such that A[i] ≥ target. If no such i exists, return −1.

Task

Implement lower_bound(target) with the following constraints and deliverables:

Algorithm

Use exponential search to bracket the answer, then binary search to find the exact index.
Overall time must be O(log n) and the number of get calls should also be O(log n).

Edge cases to handle

Duplicates in A.
Empty array (n = 0).
All values in A < target.
All values in A ≥ target.

Analysis

Prove correctness (why the algorithm returns the smallest index with A[i] ≥ target or −1 correctly).
Give a tight upper bound on the number of get calls (as a function of n and, where natural, of the answer index).

Variant

Explain how your approach changes if A is non-decreasing but may be rotated once (e.g., [4,5,6,1,2,3]), both without and with duplicates.

Implement lower_bound on unknown-size sorted array

Quick Overview

Lower Bound in Unknown-Length Nondecreasing Array via API

Setup

Task

Solution

Comments (0)

Implement lower_bound on unknown-size sorted array

Quick Overview

Lower Bound in Unknown-Length Nondecreasing Array via API

Setup

Task

Solution

Comments (0)