Highest safe floor with a monotonic check

A building has floors 1 to n, and a call can_operate(floor) tells you whether an elevator can safely serve that floor. Some floor T splits them: every floor up to T is safe and every floor above it is not. Find T with O(log n) calls.

Interface

Unless you agree on a different interface with the interviewer, assume:

• highest_safe_floor(n: int, can_operate: Callable[[int], bool]) -> int — 0 when no floor is safe (including n = 0).

Example

n = 10, safe floors 1..6   ->  6    # 4 calls: 5 yes, 8 no, 6 yes, 7 no
n = 10, no floor safe      ->  0
n = 10, every floor safe   ->  10
n = 1,  floor 1 safe       ->  1

Constraints

• 0 <= n <= 2 * 10^5 (or far larger: the cost is the number of calls).
• The answer is monotonic: safe floors never sit above unsafe ones.

Clarifying questions

• Can every floor be safe, or none?
• Is can_operate expensive, so the number of calls is what matters?
• Is n known up front, or could the building be unbounded?

What a strong answer covers

• Binary search for the last True: keep lo as a floor known safe (starting at 0) and hi as the highest floor not yet ruled out; test mid = (lo + hi + 1) // 2 so the loop always shrinks.
• The loop invariant stated out loud, and why the upward rounding prevents an infinite loop.
• About ceil(log2(n + 1)) calls, O(1) space.
• Tests: n = 0, n = 1, all safe, none safe, T at either end.

Follow-ups

• n is unknown: grow the range by doubling, then binary search.
• Each unsafe test breaks a probe and you have only two (the egg-drop problem): what is the fewest tests in the worst case?
• Return the first unsafe floor instead.