Find earliest supporting dependency version

Q: Find earliest supporting dependency version

This question evaluates a candidate's ability to design efficient search algorithms and reason about algorithmic complexity under constraints such as non-monotonic predicate behavior and a rate-limited black-box API.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

Q: What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at OpenAI during technical interviews.

Question

##### Question

Given a list of dependency versions (e.g. [103.003.02, 103.003.03, 203.003.02]) and a black-box API isSupported(v), design an algorithm to find the earliest (lowest) version that supports a target feature.
2) Versions follow {major}.{minor}.{patch}. Support is not monotonic: a higher version may drop support, but it is guaranteed that some later version will support again. The API is rate-limited, so total calls must be sub-linear to the number of versions. Devise a strategy—e.g., group by latest patch per major, binary-search majors, then minors, then patches—to minimize API usage while reliably returning the earliest supporting version.

PracHub · Accepted Answer

def solution(versions, supported_versions):
    if not versions:
        return None

supported = set(supported_versions)

major_order = []
    major_map = {}

for v in versions:
        major_str, minor_str, _ = v.split('.')
        major = int(major_str)
        minor = int(minor_str)

if major not in major_map:
            major_order.append(major)
            major_map[major] = {'latest': v, 'minor_order': [], 'minors': {}}

major_info = major_map[major]
        major_info['latest'] = v

if minor not in major_info['minors']:
            major_info['minor_order'].append(minor)
            major_info['minors'][minor] = {'latest': v, 'versions': []}

minor_info = major_info['minors'][minor]
        minor_info['latest'] = v
        minor_info['versions'].append(v)

def first_true(items, predicate):
        lo, hi = 0, len(items) - 1
        answer = None
        while lo <= hi:
            mid = (lo + hi) // 2
            item = items[mid]
            if predicate(item):
                answer = item
                hi = mid - 1
            else:
                lo = mid + 1
        return answer

first_major = first_true(major_order, lambda major: major_map[major]['latest'] in supported)
    if first_major is None:
        return None

major_info = major_map[first_major]
    first_minor = first_true(major_info['minor_order'], lambda minor: major_info['minors'][minor]['latest'] in supported)
    if first_minor is None:
        return None

patch_versions = major_info['minors'][first_minor]['versions']
    lo, hi = 0, len(patch_versions) - 1
    answer = None

while lo <= hi:
        mid = (lo + hi) // 2
        version = patch_versions[mid]
        if version in supported:
            answer = version
            hi = mid - 1
        else:
            lo = mid + 1

return answer

Quick Overview

Examples

Solution

Hints

Quick Overview