OpenAI Machine Learning Engineer Interview Experience — A Rate-Limited Dependency Version Search Problem

First question: the topic was dependency version check.

Part 1: they give you a list of dependency versions, for example [103.003.02, 103.003.03, 203.003.02]. Each version may or may not support the current feature, and you need to find the earliest version that supports it.

Part 2: they gave a bunch of corner test cases, and some of the cases actually expose more requirements — your earlier assumptions might no longer hold, and you have to print things out yourself to see why. For example, in the first case, 103.003.02 might support the feature, but the very next version, 103.003.03, doesn't. You need to look at the test data, come up with a new hypothesis, and confirm it with the interviewer.

Each test case can add a new requirement, and again you only find out by looking at the data.

Part 2 (harder version, hidden behind a spoiler tag):

The difficulty ramps up here. Some background first: versions are shown in {major}.{minor}.{patch} format — for example in 103.003.03, the major is 103, the minor is 003, and the patch is 03. Version support isn't fully backward compatible: if some version supports the feature, later versions don't necessarily all support it, but there is guaranteed to exist some later version that does.

You need to call a given API to check whether a version is supported, and because the API is rate-limited, brute-force linear-complexity calls aren't allowed. The only requirement is that the number of API calls be better than linear — everything else is unconstrained.

So what do you do? You need to print out test cases, look for patterns in the data, and work out (and demonstrate) the following conclusion: for a version that is supported, its immediate "next group" of versions is guaranteed to become supported at some point. Here "next group" means the three immediate follow-on categories. For example, if the currently supported version is 1.10.17 = True:

Same major.minor:
1.10.19 True
1.10.18 False
1.10.17 True

Same major:
1.11.1 True
1.11.0 False
1.10.17 True

Next major:
2.5.1 True
2.4.2 False
2.4.1 False
...
2.0 False
1.10.18 True
1.10.17 True

Once you've established that conclusion, you need to find the latest version under each major version — for example {3.9.9, 2.9.9, 1.9.9}, where {X.9.9} represents the latest version among all {X.?.?}. Then binary-search that new array, calling the given API to check support, to find the major version number where support first appears.

Once you've found the major version, use the same approach to find the minor version.
Same approach again for the patch version.

That gets you the solution, with API calls better than linear.