Cache key migration
A cache fleet is retiring one machine, and the on call engineer wants to know exactly which cached keys change hands. node_names lists the machines and node_slots[i] is the ring position that node_names[i] holds. Positions are distinct and are not listed in ring order. A key sitting at position p belongs to the machine at the nearest position at or after p, walking positions upward and rolling from the highest position round to the lowest one. key_slots holds the position of each live key, unsorted, and two keys may share a position. leaving_node names the machine being retired, and at least one machine stays behind. Return the positions of the keys whose owner changes, ascending, keeping repeats. Return an empty list when nothing moves.
keys_moved_on_decommission(node_names: list[str], node_slots: list[int], key_slots: list[int], leaving_node: str) → list[int][["alpha","bravo","charlie"],[10,40,90],[5,12,41,95,40],"bravo"]out[12,40][["north","south"],[30,80],[90,5,31],"north"]out[5,90][["a","b","c"],[10,20,30],[11,12],"c"]out[]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.
[["alpha","bravo","charlie"],[10,40,90],[5,12,41,95,40],"bravo"][12,40]not run yetsample[["north","south"],[30,80],[90,5,31],"north"][5,90]not run yetsample[["a","b","c"],[10,20,30],[11,12],"c"][]not run yetsample