Consistent hash rebalance
Your task
A cluster shards keys with a consistent-hashing ring (one ring point per node, no virtual nodes for this problem). A node id maps to ring position hash31(node) % ring_size and a key maps to hash31(key) % ring_size, using the FNV-1a hash in the reference; ownership is the first node clockwise (smallest position >= key position, wrapping). Given the current nodes, a new_node that joins, the ring_size, and the list of keys, return the number of keys whose owning node CHANGES as a result of the join (i.e., keys that must be moved). Assume new_node is not already present.
Examples
keys_moved_on_join(nodes: list[str], new_node: str, ring_size: int, keys: list[str]) -> intExample 1
Input
keys_moved_on_join(["A", "B"], "C", 1024, ["k1", "k2", "k3", "k4", "k5"])Output
4