Maintain a Consistent-Hashing Ring
Updated
Problem statement
Keep track of the nodes in a consistent-hashing ring and which node owns each key. Positions increase clockwise, and the last position wraps back to the first. The input gives the integer hash positions. You do not need to write a hash function.
The ring starts empty. Process the matching arrays operations and positions from left to right. At index i, apply exactly one operation:
ADD: add a node atpositions[i]. A node is identified by its position and has exactly one ring point. Adding an existing position has no effect.REMOVE: remove the node atpositions[i]. Removing a missing node has no effect.LOOKUP: interpretpositions[i]as a key position. Its owner is the active node with the smallest position greater than or equal to that key. If there is no such node, wrap to the active node with the smallest position. If the ring is empty, return-1for this lookup.
Return an integer array containing only the LOOKUP results in the order of the lookups. Do not change either input array. Each operation uses the nodes present after the earlier operations. A node added later is not yet available.
Function
runConsistentHashRing(operations: String[], positions: int[]) → int[]Examples
Example 1
operations = ["ADD","ADD","LOOKUP","LOOKUP","LOOKUP"]positions = [10,30,10,11,35]return = [10,30,10]Position 10 owns its exact key. The next clockwise node after 11 is 30, and 35 wraps to 10.
Example 2
operations = ["LOOKUP","ADD","ADD","REMOVE","LOOKUP","REMOVE","ADD","LOOKUP"]positions = [5,20,20,20,0,20,0,1]return = [-1,-1,0]The first lookup finds an empty ring. Adding node 20 twice still creates one member, so one removal empties the ring. Removing that missing member does nothing. The final lookup wraps to node 0.
Example 3
operations = ["ADD","ADD","LOOKUP","ADD","LOOKUP","REMOVE","LOOKUP"]positions = [10,30,20,25,20,25,20]return = [30,25,30]The key at 20 is first assigned to 30, then to newly added node 25, and back to 30 after node 25 is removed.
Constraints
0 <= operations.length <= 100000.positions.length == operations.length.- Every operation is
ADD,REMOVE, orLOOKUP. 0 <= positions[i] <= 1000000000.- Positions and the returned node identifiers are integers.
More Cohesity interview questions
Similar questions at other companies
- Maintain a Consistent-Hashing RingApple · PHONE SCREENApple interview questions
- Transaction Event StoreCapital One · ONSITE INTERVIEWCapital One interview questions
- Out-of-Order Logger Rate LimiterGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Dynamic Weighted SamplingCitadel · ONSITE INTERVIEWCitadel interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions
- Subscription and Usage-Based Billing CalculatorStripe · OAStripe interview questions
- Time Map with Sum and AverageConfluent · PHONE SCREENConfluent interview questions
- Structured Log Stream with QueriesOpenAI · PHONE SCREENOpenAI interview questions
- Choose ContainersIMC Trading · OAIMC Trading interview questions
- Interview Slot BookingTrueFoundry · PHONE SCREEN