Design a cluster of nodes, where each node can store some number of keys.
Complete the implementation of the class ConsistentHashing:
ConsistentHashing(int initialNodes) Initializes the object with nodes with ids from 1 to initialNodes.
int getNodeForKey(int key) Returns a node to which key is assigned. If no such node exists, you can choose any existing node and assign key to it, then return the id of that node. Also, if key is assigned to multiple nodes, you can return any of them.
int removeNode(int node) Removes node from the cluster. The keys of node should be reassigned to some other node of your choice, then you have to return the id of that node. It is guaranteed that node will exist, and at least one other node will exist in the cluster after removing node.
int[] addNode() Adds a node to the cluster. This new node should contain all the keys of some other node of your choice. The return value is an integer array of length 2. The first returned integer is the id of the new node added. This id should be sequentially increasing, that is, the first added node's id should be initialNodes + 1, the second added node's id should be initialNodes + 2, and so forth. The second returned integer is the id of the chosen node whose keys will also be assigned to this new node. Note that these keys will now be assigned to both the new node and the node that you have chosen.
List<Integer> getKeysInNode(int node) Returns all the keys of node in any order. It is guaranteed that node will exist.
Example 1:
Input
["ConsistentHashing", "getNodeForKey", "getNodeForKey", "getNodeForKey", "getNodeForKey", "getNodeForKey", "getNodeForKey", "removeNode", "getNodeForKey", "getNodeForKey", "addNode", "getNodeForKey", "getNodeForKey", "getNodeForKey","getKeysInNode"]
[[6], [10], [20], [30], [40], [50], [10], [2], [40], [30], [], [10], [20], [30], [1]]
Output
[null, 3, 1, 4, 2, 1, 3, 3, 3, 4, [7, 4], 3, 1, 4, [20, 50]]
Explanation
ConsistentHashing consistentHashing = new ConsistentHashing(6);
consistentHashing.getNodeForKey(10); // return 3. This returns any node, say 3.
consistentHashing.getNodeForKey(20); // return 1. This returns any node, say 1.
consistentHashing.getNodeForKey(30); // return 4. This returns any node, say 4.
consistentHashing.getNodeForKey(40); // return 2. This returns any node, say 2.
consistentHashing.getNodeForKey(50); // return 1. This returns any node, say 1.
consistentHashing.getNodeForKey(10); // return 3. 10 is already stored in node 3, so 3 should be returned.
consistentHashing.removeNode(2); // return 3. Node 2 gets deleted.
// We store the data of node 2 which is [40] in some other node, say 3.
consistentHashing.getNodeForKey(40); // return 3. 40 is stored in node 3, so 3 should be returned.
consistentHashing.getNodeForKey(30); // return 4. 30 is stored in node 4, so 4 should be returned.
consistentHashing.addNode(); // return [7, 4]. The new node's id should be 7.
// This node should have the data of some other node, say 4.
// So the data of node 7 is now [30].
consistentHashing.getNodeForKey(10); // return 3. 10 was stored in node 3 before, so 3 should be returned.
consistentHashing.getNodeForKey(20); // return 1. 20 was stored in node 1 before, so 1 should be returned.
consistentHashing.getNodeForKey(30); // return 4. This can return either 4 or 7, because 30 is stored in both of them.
consistentHashing.getKeysInNode(1); // return [20,50]. This returns the keys stored in node 1, which are [20,50].
// Note that the keys can be in any order.
Constraints:
1 <= node, key <= 1000
Total nodes in the cluster will be at most 300 at each time.
removeNode will be called only if there is at least two nodes in the cluster.
addNode will be called only if there is at least one node in the cluster.
At most 300 calls in total will be made for getNodeForKey, removeNode, and addNode.
