Algorithm Design & Real-Time System Optimization Questions

import hashlib
import bisect
from typing import List, Tuple

def sha256_int(s: str) -> int:
    return int(hashlib.sha256(s.encode()).hexdigest(), 16)

class ConsistentHash:
    def __init__(self, nodes: List[str], vnodes: int = 100):
        self.vnodes = vnodes
        self.ring: List[Tuple[int, str]] = []  # list of (hash, node_id)
        for node in nodes:
            for i in range(vnodes):
                h = sha256_int(f"{node}#{i}")
                self.ring.append((h, node))
        # sort by hash for binary search
        self.ring.sort(key=lambda x: x[0])
        self.hashes = [h for h, _ in self.ring]

    def get_node(self, key: str) -> str:
        if not self.ring:
            raise ValueError("No nodes in ring")
        h = sha256_int(key)
        # find first hash >= h, else wrap
        idx = bisect.bisect_left(self.hashes, h)
        if idx == len(self.hashes):
            idx = 0
        return self.ring[idx][1]

# Demo (example usage)
if __name__ == "__main__":
    ch = ConsistentHash(["node1", "node2", "node3"], vnodes=10)
    for k in ['a', 'b', 'c']:
        print(k, "->", ch.get_node(k))

# Example output (deterministic for given nodes/vnodes):
# a -> node2
# b -> node1
# c -> node3