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 the First Working Version | OpenAI Coding Question

Find the First Working Version

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a sorted list of dependency version strings and an API `works(version)` that returns whether that version is usable in your system. A version may appear as: - `major` - `major.minor` - `major.minor.patch` Treat any missing component as `0`, so: - `12` means `12.0.0` - `12.3` means `12.3.0` Assume the versions are sorted by normalized `(major, minor, patch)` order, and the predicate is monotonic: once a version works, every later version also works. Implement a function that returns the earliest working version, or `None` if no version works. The interviewer may first accept a linear scan, but large test cases require a more efficient approach. As a follow-up, explain how you would handle the same task if versions are conceptually grouped by major, minor, and patch rather than already flattened into one list.

Quick Answer: This question evaluates understanding of search algorithms, version normalization, and monotonic predicates, along with competency in parsing and ordering semantic version components.

Part 1: Earliest Working Version in a Flat Sorted List

You are given a sorted list of version strings, `versions`, and a version string `works_from`. Imagine an API `works(version)` such that every version earlier than `works_from` returns `False`, and every version equal to or later than `works_from` returns `True`. Version strings may have 1, 2, or 3 numeric components: `major`, `major.minor`, or `major.minor.patch`. Missing components count as `0`, so `12 == 12.0 == 12.0.0` and `7.3 == 7.3.0`. The list is already sorted by this normalized `(major, minor, patch)` order. Return the earliest element from `versions` that works, or `None` if no listed version works. Your solution should be efficient for large inputs.

Constraints

0 <= len(versions) <= 200000
Each version string has 1 to 3 dot-separated non-negative integers
Each numeric component is in the range [0, 10^9]
Missing minor or patch components are treated as 0 for comparison
The input list is sorted by normalized `(major, minor, patch)` order

Examples

Input: (['1', '1.2', '1.2.5', '2'], '1.2')

Expected Output: '1.2'

Explanation: `1.2` is the first version in the sorted list that is at least `1.2.0`.

Input: (['1', '1.0.1', '1.1', '2'], '1.0.2')

Expected Output: '1.1'

Explanation: `1.0.1` is too early, and `1.1` is the first normalized version greater than or equal to `1.0.2`.

Input: (['12', '12.0.1', '12.3'], '12.0.0')

Expected Output: '12'

Explanation: `12` normalizes to `12.0.0`, so it already works and is the earliest answer.

Input: ([], '1')

Expected Output: None

Explanation: An empty list has no working version.

Input: (['0.9', '1', '1.5'], '2')

Expected Output: None

Explanation: All listed versions are earlier than `2.0.0`.

Hints

Convert each version string into a fixed-length 3-integer tuple before comparing.
Because the predicate changes from `False` to `True` only once, think about binary search instead of scanning the whole list.

Part 2: Earliest Working Version in a Grouped Version Catalog

Now the versions are not given as one flat list. Instead, they are grouped as `catalog = [(major, minors), ...]`, where each `minors` is a sorted list of `(minor, patches)`, and each `patches` is a sorted list of existing patch numbers for that `(major, minor)` pair. Each listed triple `(major, minor, patch)` is an existing version. You are also given `works_from`, the first version value for which an imaginary API `works(version)` would return `True`. Missing components in `works_from` count as `0`. Return the earliest existing version in the catalog that works, formatted as a normalized string `major.minor.patch`, or `None` if no existing version works. Do not flatten the entire catalog into one long list first.

Constraints

0 <= len(catalog) <= 100000
Major groups are sorted by unique major number
Within each major group, minor groups are sorted by unique minor number and are non-empty
Within each `(major, minor)` group, patches are sorted, unique, and non-empty
All major, minor, and patch values are integers in the range [0, 10^9]
The `works_from` string has 1 to 3 dot-separated numeric components; missing components count as 0

Examples

Input: ([(1, [(0, [0, 2]), (2, [1])]), (2, [(0, [0]), (1, [0, 3])])], '1.2.0')

Expected Output: '1.2.1'

Explanation: In major `1` and minor `2`, the first patch at least `0` is `1`.

Input: ([(1, [(0, [0, 5]), (2, [0])]), (2, [(0, [0])])], '1.0.6')

Expected Output: '1.2.0'

Explanation: There is no patch in `1.0.*` that is at least `6`, so the answer moves to the next available minor in the same major.

Input: ([(1, [(0, [0, 1]), (1, [0])]), (3, [(0, [0])])], '2')

Expected Output: '3.0.0'

Explanation: `2` means `2.0.0`, and the first existing version at or after that is `3.0.0`.

Input: ([], '1.0.0')

Expected Output: None

Explanation: An empty catalog contains no versions.

Input: ([(1, [(0, [0])]), (2, [(1, [5])])], '3')

Expected Output: None

Explanation: The target `3.0.0` is later than every existing version in the catalog.

Hints

Think of the search as finding the first existing `(major, minor, patch)` that is lexicographically at least the target tuple.
You can binary search at one level, then continue inside the matching group instead of materializing every full version.

Quick Overview

This question evaluates understanding of search algorithms, version normalization, and monotonic predicates, along with competency in parsing and ordering semantic version components.