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.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Find earliest supporting dependency version

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### 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.

Quick Answer: 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.

You are given a sorted list of distinct dependency versions in the form "major.minor.patch" and a simulated black-box API isSupported(v). Your task is to return the earliest version that supports a target feature. Global support is not monotonic at the full version level: for example, one version may support the feature, a later version from a new major or minor may not, and an even later version may support again. To make sub-linear API usage possible, the data obeys these guarantees: (1) there is a first major that contains any supporting version, and every later major also contains at least one supporting version; (2) inside that first supporting major, there is a first minor that contains any supporting version, and every later minor in that major also contains at least one supporting version; (3) inside that first supporting major/minor pair, support is monotonic by patch among the listed versions. Also, if a major or minor contains any supporting version, its latest listed version is guaranteed to be supporting. For this coding task, supported_versions simulates the API: version v supports the feature if and only if v is present in supported_versions. Return the earliest supporting version, or None if no version supports the feature.

Constraints

0 <= len(versions) <= 200000
versions is sorted in ascending semantic-version order, all versions are distinct, and supported_versions is a subset of versions
The support pattern obeys the hierarchical guarantees described above: a first supporting major exists if support exists at all; within it, a first supporting minor exists; within it, a first supporting patch exists; and the latest listed version of any supporting major or minor is also supporting

Examples

Input: (["103.003.01", "103.003.02", "103.004.01", "104.000.01", "104.001.01", "104.001.02", "105.000.01"], ["103.004.01", "104.001.02", "105.000.01"])

Expected Output: "103.004.01"

Explanation: Major 103 is the first major whose latest version supports the feature. Inside it, minor 004 is the first supporting minor, and its only listed patch is the answer.

Input: (["101.000.01", "101.001.01", "102.000.01", "102.000.02", "102.001.01", "103.000.01"], ["102.000.02", "102.001.01", "103.000.01"])

Expected Output: "102.000.02"

Explanation: No version in major 101 supports the feature. In major 102, the first supporting minor is 000, and within that minor the first supporting patch is 02.

Input: (["200.000.01"], ["200.000.01"])

Expected Output: "200.000.01"

Explanation: The only version is supported, so it is also the earliest supporting version.

Input: (["300.000.01", "300.000.02"], [])

Expected Output: None

Explanation: No version supports the feature, so the correct return value is None.

Input: ([], [])

Expected Output: None

Explanation: An empty version list contains no supporting version.

Solution

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

Time complexity: O(n) preprocessing + O(log M + log m + log p) support checks, where M is the number of majors, m the number of minors in the chosen major, and p the number of patches in the chosen minor. Space complexity: O(n).

Hints

You do not need to probe every version. The latest version inside a major tells you whether that major contains any supporting version.
After finding the first supporting major, repeat the same idea for minors, then binary search patches inside the chosen minor.

Quick Overview

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.