Read router replica selection
A read router decides where each query goes. leader_index is the log position the leader has committed, and applied_indexes[i] is the position the follower replica_names[i] has applied, never past the leader, so that follower's lag is leader_index minus its applied position. Each entry of max_lags is one query's staleness allowance: a follower may serve that query when its lag is at most the allowance. Among the followers that qualify the router deliberately takes the stalest one, meaning the largest lag, so the fresher replicas stay free for queries with tighter allowances. A tie goes to the follower given first. When no follower qualifies the query goes to the leader, reported as the string "leader", and no replica carries that name. Return the target chosen for each query, in query order.
follower_read_targets(replica_names: list[str], applied_indexes: list[int], leader_index: int, max_lags: list[int]) → list[str][["r1","r2","r3"],[180,190,195],200,[0,4,5,12,20,25]]out["leader","leader","r3","r2","r1","r1"][["a","b","c","d"],[10,40,25,40],40,[0,15,29,30,31]]out["b","c","c","a","a"][["west","east"],[90,90],100,[9,10]]out["leader","west"]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.
[["r1","r2","r3"],[180,190,195],200,[0,4,5,12,20,25]]["leader","leader","r3","r2","r1","r1"]not run yetsample[["a","b","c","d"],[10,40,25,40],40,[0,15,29,30,31]]["b","c","c","a","a"]not run yetsample[["west","east"],[90,90],100,[9,10]]["leader","west"]not run yetsample