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 Onsite 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 Minimum Compatible Version | OpenAI Coding Question

Quick Overview

This question evaluates binary search, monotonic predicates, careful version ordering, and cost-aware optimization of expensive compatibility checks. It is commonly asked in the Coding & Algorithms domain to test reasoning about monotonicity, minimizing API calls, and adapting search strategies when monotonicity holds only within subranges; the level of abstraction combines conceptual understanding of monotone properties with practical application of efficient search techniques.

Find Minimum Compatible Version

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a list of software versions sorted in ascending numeric order and an expensive predicate `is_compatible(version)`. Return the minimum version that satisfies the requirement, or `None` if no version works. The interview usually progresses through three parts: 1. Base version - The predicate is globally monotone: all earlier versions return `False`, and once a version returns `True`, all later versions also return `True`. - Find the first compatible version. 2. Call-budget version - Same monotonicity assumption as Part 1. - The interviewer tracks how many times you call `is_compatible`, so you should minimize API calls. 3. Layered-monotonic version - The global sequence is not necessarily monotone. - Versions are triples `(major, minor, patch)`. - For a fixed `(major, minor)`, compatibility over `patch` is monotone. - At the `major` and `minor` levels, representative checks allow you to binary-search candidate groups. - Use this layered monotonicity to find the minimum compatible version with few predicate calls. The core skills are binary search, careful version ordering, and adapting search strategy when monotonicity only holds within subranges.

Quick Answer: This question evaluates binary search, monotonic predicates, careful version ordering, and cost-aware optimization of expensive compatibility checks. It is commonly asked in the Coding & Algorithms domain to test reasoning about monotonicity, minimizing API calls, and adapting search strategies when monotonicity holds only within subranges; the level of abstraction combines conceptual understanding of monotone properties with practical application of efficient search techniques.

Part 1: First Compatible Version

You are given a sorted list of distinct integer software versions and a boolean list `compatible` of the same length. `compatible[i]` represents the result of an expensive predicate `is_compatible(versions[i])`. The predicate is globally monotone: the values in `compatible` have the form `False, False, ..., False, True, True, ..., True`. Return the smallest version that is compatible, or `None` if no version works.

Constraints

`0 <= len(versions) <= 200000`
`len(versions) == len(compatible)`
`versions` is strictly increasing
`compatible` has the form `False...False, True...True`

Examples

Input: ([100, 101, 102, 103, 104], [False, False, True, True, True])

Expected Output: 102

Explanation: The first compatible entry is at index 2, so the answer is version 102.

Loading coding console...

Part 2: First Compatible Index Under a Call Budget

A version catalog contains versions identified only by indices `0` to `n - 1` in increasing order. Checking whether a version is compatible is expensive. For this coding problem, the results of the expensive API are provided as a boolean list `compatible`, where `compatible[i]` is the result of checking version `i`. The list is monotone: all `False` values come before all `True` values. Return the smallest compatible index, or `-1` if none are compatible. The intended solution should use binary search so the number of checks stays small.

Constraints

`0 <= len(compatible) <= 1000000`
`compatible` is monotone nondecreasing
Your algorithm should run in `O(log n)` time

Examples

Input: ([False, False, True, True, True],)

Expected Output: 2

Explanation: The first compatible index is 2.

Input: ([False, False, False],)

Expected Output: -1

Explanation: There is no `True` value.

Input: ([True, True, True],)

Expected Output: 0

Explanation: If the first element is already compatible, return index 0.

Input: ([False],)

Expected Output: -1

Explanation: Single-element edge case with no compatible version.

Input: ([],)

Expected Output: -1

Explanation: Empty input has no valid index.

Hints

You only need the leftmost `True` position, not the whole boundary.
Using a half-open search range `[lo, hi)` makes the final boundary handling cleaner.

Part 3: Minimum Compatible Semantic Version with Layered Monotonicity

You are given a sorted list of software versions as triples `(major, minor, patch)` and a boolean list `compatible` of the same length. `compatible[i]` is the result of an expensive predicate for `versions[i]`. The full list is not necessarily globally monotone, so one binary search over the entire array may fail. However, the data obeys layered monotonicity: 1. For a fixed `(major, minor)`, compatibility over increasing `patch` is monotone. 2. Inside a fixed `major`, if you inspect only the last patch of each `minor`, those representative results are monotone over increasing `minor`. 3. Across majors, if you inspect only the last version of each `major`, those representative results are monotone over increasing `major`. Versions are sorted lexicographically by `(major, minor, patch)`. Return the lexicographically smallest compatible version, or `None` if no version works.

Constraints

`0 <= len(versions) <= 200000`
`len(versions) == len(compatible)`
`versions` is sorted lexicographically and contains distinct tuples
Patch-level monotonicity holds inside each fixed `(major, minor)` block
Minor-representative monotonicity holds inside each `major`
Major-representative monotonicity holds across majors

Examples

Input: ([(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 1, 1), (3, 0, 0), (3, 0, 1)], [False, True, False, True, False, False, False, True, True, True])

Expected Output: (1, 0, 1)

Explanation: The overall sequence is not globally monotone, but the layered representative checks still lead to major 1, minor 0, patch 1.

Input: ([(1, 0, 0), (1, 0, 1), (2, 0, 0), (2, 0, 1), (2, 1, 0), (2, 1, 1), (3, 0, 0), (3, 0, 1)], [False, False, False, True, True, True, True, True])

Expected Output: (2, 0, 1)

Explanation: Major 1 has no compatible version, so the minimum compatible version is found in major 2.

Input: ([(1, 0, 0), (1, 0, 1), (2, 0, 0)], [False, False, False])

Expected Output: None

Explanation: No version is compatible in any group.

Input: ([(4, 2, 9)], [True])

Expected Output: (4, 2, 9)

Explanation: Single-version edge case.

Input: ([], [])

Expected Output: None

Explanation: Empty input has no answer.

Hints

The last patch of a minor tells you whether that minor contains any compatible patch at all.
Do three searches: first find the earliest compatible major, then the earliest compatible minor inside it, then the earliest compatible patch inside that minor.