Design a Ring Buffer for Consistent Hashing

Problem: Implement a Ring Buffer for Consistent Hashing Implement a ring buffer (hash ring) for consistent hashing to map an arbitrary key to a backend node. Required APIs Build a class/module that supports: add_node(node_id: str): add a node onto the hash ring. remove_node(node_id: str): remove a node from the hash ring. get_node(key: str) -> str: given a key, return the node_id responsible for it. Consistent hashing rule Hash both node_id and key using the same hash function into an integer space [0, M) (e.g., M = 2^32). For get_node(key): compute h = hash(key). On the ring, find the first node whose hash is >= h clockwise; if none exists, wrap around and return the node with the smallest hash. Constraints & edge cases If the ring is empty, get_node must return a null value or raise an exception (state your choice). Define behavior for adding a duplicate node id (ignore/overwrite/error). Define behavior for removing a non-existent node. Explain/aim for time complexity for add/remove/get (using an ordered structure for clockwise lookup). Example tests Assume a deterministic hash function (you may use a stable hash such as md5/sha1 truncated to 32-bit). Empty ring: get_node("k1") should return null/exception. Add nodes and query: add_node("A"), add_node("B"), add_node("C") For multiple keys (e.g., "order_1", "order_2", "order_3"), calling get_node should always return a deterministic, reproducible node. Minimal movement after removal: After removing "B", re-query the same keys; only keys originally mapped to "B" should change mapping; other keys should remain on the same nodes. Scale Number of nodes: 1 ~ 1e5 Number of queries: 1 ~ 1e6 Note: Virtual nodes are not required; implementing them can be a plus if you explain trade-offs. Example Input GET k1 Output ERROR