Implement a consistent hashing ring
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
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)`
Quick Answer: This question evaluates understanding of consistent hashing, virtual nodes, deterministic hash functions, and data structure design for efficient key-to-server mapping and dynamic membership changes.
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)'
For this platform, 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'