~/problems / Binary search / Binary search

Earliest supported version and install order

medium 4 levels ~50 min OpenAI

Level 1 Parse versions, find the earliest supported one

Versions look like "major.minor.patch", e.g. "2.10.0" or "103.003.02" (leading zeros allowed). They must be compared numerically: "1.10.0" is newer than "1.9.0", and "1.02.0" equals (1, 2, 0).

  • parse_version(version) -> tuple[int, int, int].
  • earliest_supported(versions, is_supported) -> str | None: versions is a list of version strings in any order (no two parse to the same tuple). is_supported(version) is a slow API that says whether a feature works in that version; support can switch on and off arbitrarily between versions. Return the numerically smallest version for which is_supported is True, exactly as it was written in the input, or None if there is none. Call is_supported at most once per version.
versions = ["1.10.0", "1.9.0", "1.2.3", "2.0.0"]
supported = {"1.10.0", "2.0.0"}
earliest_supported(versions, lambda v: v in supported)   # "1.10.0"
parse_version("103.003.02")                                # (103, 3, 2)

The classic bug is sorting or comparing the raw strings: lexicographically "1.10.0" < "1.9.0".

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Level 4 unlocks when level 3 passes.

Topic: Binary search. lo/hi invariants, lower vs upper bound, rotated arrays, bisect.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc