Version range queries
A package resolver holds the release history of one library as version strings, already sorted oldest to newest, with no repeats. Every version is exactly three dot separated non-negative integers, so 1.9.0 comes before 1.10.0. Each entry of queries is one constraint written as two versions separated by a single space, a floor then a ceiling, and it asks for the newest release that is at or above the floor and strictly below the ceiling. Return one string per query, in query order: the matching release, or the word none when nothing qualifies. The history and the query list can each hold hundreds of thousands of entries, so walking the history once per query is too slow.
newest_release_in_range(releases: list[str], queries: list[str]) → list[str][["0.9.9","1.0.0","1.2.3","1.9.0","1.10.0","1.10.2","2.0.0","9.9.9","10.0.0","10.2.0"],["1.9.0 2.0.0","1.0.0 1.9.0","3.0.0 9.0.0"]]out["1.10.2","1.2.3","none"][[],["1.0.0 2.0.0"]]out["none"][["0.9.9","1.0.0","1.2.3","1.9.0","1.10.0","1.10.2","2.0.0","9.9.9","10.0.0","10.2.0"],["0.0.0 100.0.0","10.2.0 10.2.1"]]out["10.2.0","10.2.0"]State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
[["0.9.9","1.0.0","1.2.3","1.9.0","1.10.0","1.10.2","2.0.0","9.9.9","10.0.0","10.2.0"],["1.9.0 2.0.0","1.0.0 1.9.0","3.0.0 9.0.0"]]["1.10.2","1.2.3","none"]not run yetsample[[],["1.0.0 2.0.0"]]["none"]not run yetsample[["0.9.9","1.0.0","1.2.3","1.9.0","1.10.0","1.10.2","2.0.0","9.9.9","10.0.0","10.2.0"],["0.0.0 100.0.0","10.2.0 10.2.1"]]["10.2.0","10.2.0"]not run yetsample