Katkat
Back

Find the First Working Version

OpenAIMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to combine custom comparison logic with a binary search approach to identify the first transition point in a monotonic sequence.

Problem Statement

You are working on a machine learning model deployment system. You have a list of software versions represented as strings (e.g., "1.0.0", "1.2.1", "2.0.10"). Versions follow the standard semantic versioning format MAJOR.MINOR.PATCH.

You have access to a function is_broken(version: str) -> bool that returns True if a specific version has a critical bug and False otherwise. You are given a list of versions sorted in chronological order. It is guaranteed that once a version is broken, all subsequent versions in the list are also broken.

Your task is to implement a function find_first_broken(versions: List[str]) -> str that returns the first version string in the list that is broken. If no version is broken, return an empty string.

Constraints

  • 1 <= len(versions) <= 10^5
  • Versions are strings containing non-negative integers separated by dots.
  • The underlying is_broken function is expensive; minimize the number of calls.

Examples

# Example 1
versions = ["1.0.0", "1.0.1", "1.1.0", "1.2.0"]
# is_broken returns [False, False, True, True]
# Output: "1.1.0"

# Example 2
versions = ["1.0.0", "1.0.1"]
# is_broken returns [False, False]
# Output: ""

Edge Cases

  • The list contains only one version.
  • All versions are broken.
  • No versions are broken.

Hints

Hint 1

Since the versions are sorted and the broken status follows a monotonic pattern (all False then all True), consider using binary search to optimize your lookup.

Hint 2

The version strings need to be treated as logical entities; if you rely purely on string comparison, '1.10' might be considered smaller than '1.2'.

Hint 3

You do not actually need to parse the versions into integers for the search itself, as you are given a pre-sorted list and only need to find the index where the predicate changes.

Follow-up questions

  • How would you modify your solution if the input list of versions was not pre-sorted?
  • What is the time complexity of your solution, and how many calls to `is_broken` do you make in the worst case?
  • If the versioning format included pre-release tags like '1.0.0-alpha', how would that change your comparison logic?