Code RoomCache key normalization
MediumPrep Room Coding #4876

Cache key normalization

CodingStorage & CDNAlgorithms & data structuresMid–Senior~25 min

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.

Implement
cache_entry_owner(urls: list[str], ignored_params: list[str]) → list[int]
Examples
in[["/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]
in[["/a?sid=1&v=2","/a?v=2&sid=9","/a?v=2"],["sid"]]out[0,0,0]
in[["/home","/home?","/help"],[]]out[0,0,2]
What a strong answer looks like

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:00 of about 25 min
InputExpectedGot
[["/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