←ENG-DSA-006Distributed Hash Ring — Consistent Hashing (Binary Search)
00:00
🐍 Python Idle
Mode:Web

Distributed Hash Ring — Consistent Hashing (Binary Search)

CompaniesAmazon, Cloudflare
Est. Time~45 min
LevelSenior
Binary SearchHashingDistributed Systems
🚨 P0 Incident
AmazonCloudflare

Amazon's ElastiCache team uses consistent hashing to distribute cache keys across Redis nodes. The classic problem: with regular modular hashing (key % N), adding a new server remaps ~83% of keys, causing a massive cache stampede. Consistent hashing reduces remapping to ~1/N of keys. This is how DynamoDB, Cassandra, and Riak distribute data.

📥 Assigned to:You — Senior Engineer
Your Task

Building a distributed Redis cache. When a node is added, map user IDs to servers using Consistent Hashing so only 1/N of keys need remapping. Implement the lookup algorithm.

⏱ Time: O(log N) lookup, O(V log V) build💾 Space: O(V*N)
Example 1
Input:  ring(['s1','s2','s3']): get_server('user-42')
Output: One of: s1, s2, s3
Example 2
Input:  get_server('user-42') called twice
Output: Same server both times (deterministic)
🔒 +3 hidden test cases — revealed on Submit
Hints
Loading editor…
Test Output
▶ Run Code to test against examples · Submit to judge all 5 test cases
EngPrep — Real Engineering. Real Interviews.