How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Implement a consistent hashing ring | DoorDash Coding Question

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.

Input: (2, ['add_server', 'add_server', 'add_server', 'get_server', 'remove_server', 'get_server', 'remove_server', 'get_server', 'remove_server', 'get_server'], [['A'], ['B'], ['C'], ['qT'], ['C'], ['qT'], ['A'], ['qT'], ['B'], ['qT']])

Expected Output: [None, None, None, 'C', None, 'A', None, 'B', None, None]

Explanation: With 2 replicas: A -> 279, 282; B -> 280, 283; C -> 281, 284. 'qT' hashes to 281, so it first maps to C. After removing C it maps to A at 282, after removing A it maps to B at 283, and after removing B the ring is empty.

Input: (1, ['add_server', 'get_server', 'remove_server', 'get_server'], [['A'], [''], ['A'], ['']])

Expected Output: [None, 'A', None, None]

Explanation: The empty string hashes to 0. With only A#0 at 279, it maps to A. After removing A, the ring is empty again.

Hints

Think of each virtual node as a point on a sorted circle. Then 'get_server' becomes a successor/lower_bound query with wrap-around.
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.

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.