Find Minimum Compatible Version

Problem Statement

In a distributed machine learning pipeline, worker nodes must determine the earliest compatible model runtime version from a candidate list versions. Compatibility is verified using an external API function is_compatible(version) -> bool, which is computationally expensive (e.g., spins up an isolated sandbox container).

Each version string follows standard semantic versioning format: "MAJOR.MINOR.PATCH", where each component is a non-negative integer. A version A is strictly less than B if its (MAJOR, MINOR, PATCH) tuple is lexicographically smaller.

Compatibility obeys the following branch-monotonicity property:

• Within the same MAJOR version branch, compatibility is monotonic: if version v is compatible, all versions v' >= v sharing that same MAJOR version are also compatible.
• Across different MAJOR versions, compatibility is independent; a breaking API change in a higher major version may break compatibility, or a rewrite may restore it.

Write a function find_minimum_compatible_version(versions, is_compatible) that returns the lexicographically earliest compatible version string. If no version is compatible, return None.

Your solution should minimize the total number of invocations of is_compatible.

Function Interface

from typing import Callable, List, Optional

def find_minimum_compatible_version(
    versions: List[str], 
    is_compatible: Callable[[str], bool]
) -> Optional[str]:
    pass

Constraints

• 1 <= len(versions) <= 10^5
• Each version string matches the regex ^[0-9]+\.[0-9]+\.[0-9]+$.
• All strings in versions are unique.
• is_compatible is deterministic and costly; minimize calls.

Examples

Example 1

versions = ["1.0.0", "1.1.0", "1.2.0", "2.0.0", "2.1.0"]
# is_compatible returns True for "1.2.0", "2.0.0", and "2.1.0"
find_minimum_compatible_version(versions, is_compatible)
# Output: "1.2.0"

Explanation: Checking major version 1's highest candidate "1.2.0" confirms compatibility exists in branch 1. Binary search identifies "1.2.0" as the minimum within branch 1. Because all branch 1 versions are strictly smaller than any branch 2 version, "1.2.0" is guaranteed to be the global minimum, and branch 2 never needs to be evaluated.

Example 2

versions = ["1.0.0", "1.0.5", "2.0.0", "2.1.0"]
# is_compatible returns True only for "2.1.0"
find_minimum_compatible_version(versions, is_compatible)
# Output: "2.1.0"

Explanation: Checking "1.0.5" returns False, eliminating all of major version 1 with a single check. We then search branch 2 and locate "2.1.0".