Quick Overview

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.

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'

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

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

Expected Output: [None]

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

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

Expected 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.

Loading coding console...