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 version under constraints

Quick Overview

This question evaluates parsing and comparison of zero-padded version strings, handling of invalid inputs and duplicates, and design of rate-limited search strategies with complexity analysis, reflecting skills in robust input handling, algorithmic thinking, and system-aware optimization.

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given version strings formatted as {major}.{minor}.{patch}, e.g., "103.003.03". Each version either supports a feature or not. You may call isSupported(version): bool when needed. Part A: Given an arbitrary list of versions, return the smallest (by version order) version that supports the feature. Support is not monotonic across versions (e.g., 103.003.02 may support while 103.003.03 does not). Specify how you parse/compare zero-padded segments, handle duplicates or invalid inputs, and provide time/space complexity. Explain how you would refine assumptions as counterexamples emerge from test cases. Part B: Now the API is rate-limited, so O(N) calls are disallowed. Global monotonicity still does not hold, but you are guaranteed that for any supporting version, in each immediate successor group—(i) same major and minor while patch increases, (ii) same major while minor increases, and (iii) the next major—support eventually appears at some later point. Design an algorithm that makes fewer than linear API calls to find the earliest supporting version: outline computing the latest version per major, binary searching those to find the first supporting major, then binary searching latest-per-minor within that major, and finally binary searching patches. Prove correctness under the given guarantee, analyze the number of API calls, and discuss edge cases (no supporting version, sparse support pockets, very large version spaces).

Quick Answer: This question evaluates parsing and comparison of zero-padded version strings, handling of invalid inputs and duplicates, and design of rate-limited search strategies with complexity analysis, reflecting skills in robust input handling, algorithmic thinking, and system-aware optimization.

Part 1: Earliest Supporting Version in an Arbitrary List

You are given an unsorted list of version strings and another collection that tells you which versions support a feature. A version is formatted as `major.minor.patch`, such as `103.003.03`. Leading zeros are allowed, but version comparison is numeric by segment, so `103.003.03` equals `(103, 3, 3)`. Support is not monotonic: a version may support the feature even if a later version does not. Return the smallest supporting version that appears in the input list. Rules: - Compare versions numerically by `(major, minor, patch)`. - Ignore invalid version strings. - Duplicates are allowed and should not affect the answer. - Return the answer in canonical form with no zero padding, such as `103.3.3`. - If no valid listed version supports the feature, return `None`.

Constraints

0 <= len(versions) <= 200000
0 <= len(supported_versions) <= 200000
A valid version has exactly 3 non-empty numeric segments separated by dots
Leading zeros are allowed and do not affect ordering
Invalid version strings must be ignored

Examples

Input: (["103.003.03", "103.003.02", "102.010.009"], ["103.003.02", "102.010.009"])

Expected Output: "102.10.9"

Explanation: Both listed versions support the feature, and `(102, 10, 9)` is smaller than `(103, 3, 2)`.

Input: (["001.002.003", "1.2.3", "bad", "1.2", "01.002.004"], ["0001.0002.0003", "99.0.0"])

Expected Output: "1.2.3"

Explanation: Invalid entries are ignored. `001.002.003` and `1.2.3` are the same numeric version, which is supported.

Input: (["1.0.0", "2.0.0"], ["3.0.0"])

Expected Output: None

Explanation: No supporting version appears in the given list.

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

Expected Output: None

Explanation: Edge case: empty version list.

Input: (["007.000.009"], ["7.0.9"])

Expected Output: "7.0.9"

Explanation: Single valid version, with zero padding.

Hints

Parse every valid version into a tuple of three integers so numeric comparison becomes easy.
Because support is not monotonic, scanning the list and tracking the minimum supporting version is enough; binary search does not apply.

Part 2: Earliest Supporting Version with Sublinear Support Checks

You are given all existing version strings and a second collection that simulates a rate-limited `isSupported(version)` API. Versions are formatted as `major.minor.patch`, leading zeros are allowed, and comparison is numeric by segment. Global support over the full version order is not monotonic. However, the test data guarantees three monotone search layers: 1. If you take the latest existing version from each major and sort majors, support on those representatives looks like `False, False, ..., True, True, ...`. 2. Inside the first supporting major, if you take the latest existing version from each minor and sort minors, support on those representatives also looks like `False, False, ..., True, True, ...`. 3. Inside the first supporting `(major, minor)`, patches themselves are monotone: `False, False, ..., True, True, ...`. Use this structure to find the earliest supporting version while making fewer than linear support checks: binary search majors, then minors, then patches. Rules: - Ignore invalid version strings. - Duplicates are allowed and should not affect the answer. - Return the answer in canonical `major.minor.patch` form with no zero padding. - Return `None` if no valid supporting version exists.

Constraints

0 <= len(versions) <= 200000
0 <= len(supported_versions) <= 200000
A valid version has exactly 3 non-empty numeric segments separated by dots
Leading zeros are allowed and do not affect ordering
The monotone representative guarantees listed above hold for all valid test cases
Invalid version strings must be ignored

Examples

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"], ["2.0.1", "2.1.1", "3.0.1"])

Expected Output: "2.0.1"

Explanation: The first supporting major is 2, the first supporting minor inside major 2 is 0, and the first supporting patch there is 1.

Input: (["1.0.0", "1.0.1", "1.0.2", "1.1.0", "1.1.1", "2.0.0", "2.0.1"], ["1.0.1", "1.0.2", "1.1.1", "2.0.1"])

Expected Output: "1.0.1"

Explanation: Major 1 already supports the feature. Inside major 1, minor 0 supports before minor 1, and within minor 0 the first supporting patch is 1.

Input: (["1.0.0", "1.0.1", "2.0.0"], [])

Expected Output: None

Explanation: Edge case: no supporting version exists.

Input: (["007.000.009"], ["7.0.9"])

Expected Output: "7.0.9"

Explanation: Edge case: single valid version.

Input: (["bad", "01.002.000", "1.2.1", "1.3.0", "1.3.1", "2.0.0", "2.0.1", "1.2.0", "1.2.1"], ["001.002.001", "1.3.1", "2.0.1"])

Expected Output: "1.2.1"

Explanation: Invalid entries and duplicates are ignored. The earliest supporting version is `1.2.1`.

Hints

Precompute the latest version in each major and the latest version in each minor of a major.
Run three lower-bound style binary searches: one over majors, one over minors in the chosen major, and one over patches in the chosen minor.

Quick Overview