Find earliest supporting version under constraints

Q: Find earliest supporting version under constraints

This is a Coding & Algorithms interview question from OpenAI for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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

Find earliest supporting version under constraints

Comments (0)