Consistent hash rebalance

Write codeMedium25 minAmazon style

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]) -> int
Example 1
Inputkeys_moved_on_join(["A", "B"], "C", 1024, ["k1", "k2", "k3", "k4", "k5"])
Output4