Practice/OpenAI/Dependency Version Check

Dependency Version Check

CodingMust

Problem

You are building a system to find the earliest version of a software dependency that supports a specific feature. You have access to an API isSupported(version) -> bool that checks if a version supports the feature. The problem progressively adds constraints: version parsing, non-monotonic support patterns, and API rate limiting.

This is a multi-part problem -- ask the interviewer how many parts there are to manage your time.

Core Insight

Version strings like "103.003.02" must be parsed into numeric tuples for correct comparison (lexicographic string sorting gives wrong results). The optimization insight is that support patterns are monotonic at the group level (major/minor boundaries), enabling hierarchical binary search even when individual versions can regress.

Part 1: Find Earliest Supporting Version

Given a list of version strings and an isSupported() function, find the earliest version that supports the feature.

Requirements

• Parse version format major.minor.patch (e.g., "103.003.02" -> (103, 3, 2))
• Handle leading zeros: "003" should parse as 3
• Sort versions by parsed tuple (not lexicographic order)
• Return the first version where isSupported() returns True

Example

` versions = ["1.0.0", "1.0.1", "1.0.2", "2.0.0"]

isSupported: 1.0.0->False, 1.0.1->False, 1.0.2->True, 2.0.0->True

Expected: "1.0.2"

`

Approach

Sort versions by parsed tuple, then linear scan for first True. Time: O(N log N) for sort + O(N) for scan.

Part 2: Handle Non-Monotonic Support

After analyzing test data, you discover support is not monotonic -- a version can support a feature while the next version does not (regressions).

Example

` versions = ["1.0.0", "1.0.1", "1.0.2", "1.0.3"]

1.0.0->False, 1.0.1->True, 1.0.2->False, 1.0.3->True

Expected: "1.0.1" (earliest, despite regression at 1.0.2)

`

Updated Approach

Since support can regress, you must check every version. Sort by parsed tuple, scan all, track the earliest True. Binary search won't work here because the predicate isn't monotonic.

Discovery Process

In a real interview, you'd discover this by printing the support pattern:

def analyze_pattern(versions, is_supported): sorted_v = sorted(versions, key=parse_version) for v in sorted_v: print(f"{v}: {is_supported(v)}")

Discuss with the interviewer: Can support regress within patch versions? Within minor? What patterns exist across major versions?

Part 3: Optimized Search with Rate Limiting

The interviewer reveals: isSupported() is rate-limited. You need sub-linear API calls.

Key Observation

After analyzing test data, you discover: the latest version in each major/minor group reliably indicates support for that group. This means you can binary search at the group level.

Hierarchical Binary Search Strategy

1. Group versions by major version, find the latest in each group
2. Binary search on major groups: check the latest version in each major to find the first major with support
3. Binary search on minor groups within the found major
4. Binary search on patch versions within the found minor

Example Walkthrough

` Versions across 3 majors, support starts at 2.1.0:

Step 1: Latest per major -> [1.6.1, 2.1.1, 3.0.1] Step 2: Binary search -> check 2.1.1 (True), check 1.6.1 (False) -> major=2 Step 3: Latest per minor in major 2 -> [2.0.2, 2.1.1] Binary search -> check 2.1.1 (True), check 2.0.2 (False) -> minor=1 Step 4: Versions in 2.1 -> [2.1.0, 2.1.1] Binary search -> check 2.1.0 (True) -> answer: "2.1.0" Total: 5 API calls (vs 12 for linear) `

Complexity

• API calls: O(log M + log Mi + log P) where M = distinct majors, Mi = distinct minors, P = distinct patches
• Best case: O(log N) total calls vs O(N) for linear

Edge Cases

• All versions in a single major group (degrades to 2D search)
• Sparse version numbers with large gaps
• Single version that supports the feature
• All versions unsupported