Earliest release that supports a feature

Every probe of is_supported is a rate-limited remote call, so the real cost
is the number of probes, not CPU time. The list is already sorted, so the
question is how much structure the "supported" predicate has.

Brute force. Walk the list from the oldest version and return the first
one the checker accepts. That is correct for any predicate but costs up to
n probes, which the interviewer will rule out once the list has hundreds of
thousands of entries.

Part 1: support never turns off. If a version has the feature and every
later version does too, the predicate over the list looks like
F F ... F T T ... T. That is "first bad version": binary search for the
first T in O(log n) probes. Keep the half-open invariant: the answer is
always in [lo, hi), hi = n means "not found yet", and every probe halves
the range.

Part 2: support can flicker. The harder version of this question drops
global monotonicity. A later minor or patch release can lose the feature and a
still later one can bring it back, so a plain binary search over the whole
list can land on a F to the right of the true answer and miss it. What
still holds is monotonicity level by level:

• Across majors: once some major has a supporting release, every later major
  has one too.
• Within the first supporting major, the same holds across its minors.
• Within the first supporting minor, support is monotone across patches.
• If a bucket (a major, or a major.minor) has any supporting release, its
  newest release supports the feature.

The last rule is what makes the search work. "The newest release of bucket
k is supported" is a monotone predicate over buckets, so it can be binary
searched with one probe per step. The search runs in three stages:

1. Group the list into majors (contiguous runs, since the list is sorted).
   Binary search the majors by probing each one's newest release.
2. Inside the winning major, group by minor and binary search the same way.
3. Inside the winning minor, binary search the patches directly.

Compare versions as integer tuples, never as strings. "10.0.0" < "9.0.0" is
true as strings, and zero-padded parts like "003" must group with "3".

from typing import Callable, Optional, Sequence


class VersionChecker:
    """Black-box API. Each call to is_supported costs one (rate-limited) probe."""

    def __init__(self, supported: set[str]) -> None:
        self._supported = supported
        self.calls = 0

    def is_supported(self, version: str) -> bool:
        self.calls += 1
        return version in self._supported


def parse(version: str) -> tuple[int, int, int]:
    major, minor, patch = (int(part) for part in version.split("."))
    return major, minor, patch


def first_true(n: int, pred: Callable[[int], bool]) -> int:
    """Smallest i in [0, n) with pred(i) true, assuming pred is monotone
    (False...False True...True). Returns n if pred is never true."""
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def first_supported_monotone(versions: Sequence[str], checker: VersionChecker) -> Optional[str]:
    """Part 1: support never turns off once it turns on."""
    i = first_true(len(versions), lambda k: checker.is_supported(versions[k]))
    return versions[i] if i < len(versions) else None


def group_ranges(versions: Sequence[str], start: int, end: int,
                 key: Callable[[str], tuple[int, ...]]) -> list[tuple[int, int]]:
    """Split versions[start:end] (sorted) into [lo, hi) runs that share key()."""
    runs: list[tuple[int, int]] = []
    lo = start
    for i in range(start + 1, end + 1):
        if i == end or key(versions[i]) != key(versions[lo]):
            runs.append((lo, i))
            lo = i
    return runs


def first_supported(versions: Sequence[str], checker: VersionChecker) -> Optional[str]:
    """Part 2: support is monotone only level by level.
    - majors: once some major has support, every later major has some;
    - minors: the same inside the first supporting major;
    - patches: monotone inside the first supporting minor;
    - a bucket with any support has support at its newest version."""
    if not versions:
        return None

    def search(runs: list[tuple[int, int]]) -> Optional[tuple[int, int]]:
        # Probe each bucket's newest version; that predicate is monotone over buckets.
        i = first_true(len(runs), lambda k: checker.is_supported(versions[runs[k][1] - 1]))
        return runs[i] if i < len(runs) else None

    majors = group_ranges(versions, 0, len(versions), lambda v: parse(v)[:1])
    major = search(majors)
    if major is None:
        return None
    minors = group_ranges(versions, major[0], major[1], lambda v: parse(v)[:2])
    minor = search(minors)
    assert minor is not None  # the major's newest version is supported
    lo, hi = minor
    i = first_true(hi - lo, lambda k: checker.is_supported(versions[lo + k]))
    return versions[lo + i]

first_true is the one binary search; every stage reuses it with a different
predicate. Grouping is a single linear pass over strings, which costs no probes.

Let n be the number of versions, M the number of majors, m the number of
minors in the chosen major and p the number of patches in the chosen minor.

• Brute force: up to n probes, O(n) time.
• Part 1 (first_supported_monotone): O(log n) probes and time, O(1) extra space.
• Part 2 (first_supported): O(log M + log m + log p) probes, which is at
  most about 3 log n. Time is O(n) for the grouping pass (parsing is
  local work, no probes) and O(M) extra space for the major runs. If the
  versions arrive pre-grouped, or you binary search the boundaries of runs
  too, local time also drops to O(log n).

Using vs = ["1.0.0", "1.0.5", "1.2.0", "2.0.0", "2.0.3", "2.1.0", "2.1.1", "2.1.4", "3.0.0"]:

• Part 1, supported from "2.1.0" onward: returns "2.1.0" in at most 4 probes.
• Part 1, nothing supported: returns None.
• Part 2, supported {"2.0.3", "2.1.1", "2.1.4", "3.0.0"} (2.1.0 loses the
  feature, 2.1.1 gets it back): returns "2.0.3". A plain binary search
  over the list could probe 2.1.0, see False and wrongly move right.
• Part 2, supported {"2.1.4", "3.0.0"}: returns "2.1.4" (only the newest
  patch of a minor).
• Part 2, supported {"3.0.0"}: returns "3.0.0" (last element).
• Empty list: None. Single version ["0.0.1"] that is supported: "0.0.1".
• Zero padding: ["9.009.1", "10.000.01", "10.000.02", "10.001.00"] with
  {"10.000.02", "10.001.00"} supported returns "10.000.02"; 9.x sorts
  before 10.x numerically.
• Scale: 20,000 versions (50 majors x 20 minors x 20 patches), answer
  "31.7.12": found in 16 probes.

• Probes are expensive and can run in parallel. Turn binary search into
  k-ary search: probe k-1 evenly spaced points at once, keep the bracket
  that contains the first True. Rounds drop to log_k n, total probes rise
  slightly. Ask whether the budget is calls or wall-clock latency.
• Cache probe results. The newest release of the chosen major is also the
  newest release of its last minor, so a small dict memo avoids repeating
  that probe. Worth it when each call is rate limited.
• Versions are not sorted, or have more parts (1.2.3.4, -rc1
  suffixes). Parse into a comparable key first (pre-releases sort before the
  release), sort once, and generalise the three stages to a loop over the
  key's levels: group by the first d parts, binary search, recurse.
• The checker is flaky (random false negatives). Retry a False a few
  times before trusting it, or verify the final answer and its predecessor.
  Discuss the probe-count cost of each choice.
• The "newest release represents its bucket" rule does not hold. Then no
  sub-linear algorithm is correct in the worst case: an adversary can hide
  the only supporting release anywhere. Say so, and fall back to a linear
  scan with batching.

Mid-level (L4)

• Spots the sorted list plus monotone predicate and writes a bug-free binary
  search for the first True, including "none supported" and empty input.
• Compares versions numerically, not as strings.
• Walks through a small example to show the loop terminates.

Senior (L5)

• Asks whether support can turn off again before coding, and explains why a
  global binary search breaks on the flickering version.
• Uses the "newest release represents the bucket" rule to search majors,
  minors and patches in O(log n) probes total, with one reusable helper.
• Counts probes in the analysis and tests with a probe counter.

Staff (L6+)

• Frames the cost model (probes vs. latency vs. local CPU) and proposes
  parallel k-ary probing, memoisation and retries for a flaky checker.
• Generalises to arbitrary-depth version keys and pre-release tags.
• States exactly which assumptions the sub-linear bound depends on, and what
  breaks (and what to do) when they fail.