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.