OpenAI·Machine Learning Engineer·Technical Phone Screen
- You have a list of version strings in the format {major}.{minor}.{patch} with zero-padded segments. Given an arbitrary list of these versions and an isSupported(version) API call, return the smallest version (by version ordering) that supports a feature. Support is not monotonic. How do you parse and compare versions, handle duplicates or invalid inputs, and what is the time and space complexity?
- Now the isSupported API is rate-limited so you can't make O(N) calls. Support is still not globally monotonic, but you're guaranteed that for any supporting version, support will eventually reappear in the next patch group, the next minor group, and the next major group. Design a sub-linear algorithm to find the earliest supporting version. Walk through correctness, call count, and edge cases like no supporting version at all or very sparse support.
“My first instinct was just sort and scan, which is correct but I fumbled explaining the comparison logic for zero-padded segments out loud.”