Mercurial

comparison grok_interview/consistent_hash.py @ 51:68fa88ac73fe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Interview prep for xAI
author June Park <parkjune1995@gmail.com>
date Mon, 15 Dec 2025 19:55:17 -0800
parents
children
comparison
equal deleted inserted replaced
46:b9a40c633c93 51:68fa88ac73fe
1 # Write a function taht maps
2 # Key string to one of N servers
3 from bisect import bisect_left
4 from hashlib import sha256
5
6 class Server:
7
8 def __init__(self):
9 self.id = str(sha256())
10
11 class ConsistentHash:
12 def __init__(self):
13 self.server = []
14 self.hash_key_to_server = {}
15 self.hash_range = 10000
16
17 def get_hash_pos(self, key: str) -> int:
18 x = sha256(bytes(key, "utf-8"))
19 return int.from_bytes(x.digest()[:8]) % self.hash_range
20
21 def add_server(self, server: Server):
22 self.server.append(server)
23 for i in range(len(self.server) + 1):
24 hash_key = self.get_hash_pos(server.id)
25 self.hash_key_to_server[hash_key] = i
26
27 def get_server(self, key):
28 hash_key = self.get_hash_pos(key)
29 return self.server[bisect_left(list(self.hash_key_to_server.keys()), hash_key)]
30
31 def remove_server(self, server):
32 hash_key = self.get_hash_pos(server.id)