Cache key normalization
An edge cache turns each request URL into a cache key. A URL is a path, then optionally a question mark and a query string of name=value pairs joined by ampersands. Names are unique within a URL, values may be empty, and no path, name or value contains an ampersand, a question mark or an equals sign. Two requests share a cache entry when their paths match exactly and, after discarding every parameter whose name appears in ignored_params, the remaining name=value pairs match as a set, so the order the parameters were written in is irrelevant. Given the requests in arrival order and the list of parameter names to discard, return a list where position i holds the index of the earliest request that shares request i's cache entry. A request that opens a new entry reports its own index.
cache_entry_owner(urls: list[str], ignored_params: list[str]) → list[int][["/img/logo.png?w=200&fmt=webp","/img/logo.png?fmt=webp&w=200","/img/logo.png?w=400&fmt=webp"],[]]out[0,0,2][["/a?sid=1&v=2","/a?v=2&sid=9","/a?v=2"],["sid"]]out[0,0,0][["/home","/home?","/help"],[]]out[0,0,2]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.
[["/img/logo.png?w=200&fmt=webp","/img/logo.png?fmt=webp&w=200","/img/logo.png?w=400&fmt=webp"],[]][0,0,2]not run yetsample[["/a?sid=1&v=2","/a?v=2&sid=9","/a?v=2"],["sid"]][0,0,0]not run yetsample[["/home","/home?","/help"],[]][0,0,2]not run yetsample