Implement a consistent hashing ring

Implement a class ConsistentHashRing that distributes keys across servers using a hash ring with virtual nodes.

Required API:

• ConsistentHashRing(replicas_per_server: int)
• add_server(server_id: str) -> None
• remove_server(server_id: str) -> None
• get_server(key: str) -> Optional[str]

Behavior:

• Use any deterministic hash function that maps a string to a 32-bit integer.
• When a server is added, create replicas_per_server virtual nodes at positions hash(server_id + "#" + i) for i = 0..replicas_per_server-1.
• get_server(key) computes hash(key) and returns the server owning the first virtual node found when moving clockwise around the ring.
• If there is no virtual node with position greater than or equal to hash(key), wrap around and return the server at the smallest position.
• If the ring is empty, return None.
• Removing a server removes all of its virtual nodes.

Target complexity:

• add_server / remove_server: O(R log N) where R is the number of replicas added or removed
• get_server: O(log N)

Implement a Consistent Hashing Ring

Design a consistent hashing ring with virtual nodes.

Conceptually, you are implementing a class 'ConsistentHashRing' with these methods:

• 'ConsistentHashRing(replicas_per_server)'
• 'add_server(server_id)'
• 'remove_server(server_id)'
• 'get_server(key)'

Implement a function 'solution(replicas_per_server, operations, arguments)' that simulates those API calls and returns the result of each operation.

Use this exact deterministic 32-bit hash function so the outputs are well-defined: H(s) = sum((index + 1) * ord(s[index]) for index in range(len(s))) mod 2^32

Rules:

• When a server is added, create 'replicas_per_server' virtual nodes at positions H(server_id + '#' + i) for i from 0 to replicas_per_server - 1.
• 'get_server(key)' computes H(key) and returns the server owning the first virtual node found when moving clockwise around the ring.
• If no virtual node has position greater than or equal to H(key), wrap around and return the server at the smallest position.
• If the ring is empty, return None.
• Removing a server removes all of its virtual nodes.
• If multiple virtual nodes land on the same numeric position, order them by the replica token 'server_id#i' so the behavior stays deterministic.

Your function should return a list with one result per operation:

• return None for 'add_server' and 'remove_server'
• return the selected server_id or None for 'get_server'

Constraints

• 1 <= replicas_per_server <= 1000
• 1 <= len(operations) == len(arguments) <= 2 * 10^5
• The number of active virtual nodes never exceeds 2 * 10^5
• 1 <= len(server_id) <= 100 and 0 <= len(key) <= 100
• Server IDs are unique while active; removing a missing server should do nothing

Examples

Example 1

Input: (3, ['get_server'], [['qS']])
Output: [None]

Explanation: The ring is empty, so 'get_server' must return None.

Example 2

Input: (3, ['add_server', 'add_server', 'get_server', 'get_server', 'get_server', 'get_server'], [['A'], ['B'], ['qS'], ['qT'], ['qU'], ['zz']])
Output: [None, None, 'A', 'A', 'B', 'A']

Explanation: With 3 replicas: A -> 279, 282, 285 and B -> 280, 283, 286. 'qS' hashes to 279 -> A, 'qT' hashes to 281 so it advances to 282 -> A, 'qU' hashes to 283 -> B, and 'zz' hashes to 366 so it wraps to the smallest position 279 -> A.

Hints

1. Think of each virtual node as a point on a sorted circle. Then 'get_server' becomes a successor/lower_bound query with wrap-around.
2. Store every replica token created for a server so you can delete them quickly later. Using keys like (position, replica_token) also makes hash collisions deterministic.