Find earliest supporting version under constraints
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.
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).