How should I practice Maintain a Consistent-Hashing Ring?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Apple phone screen problems in FastPrep.

Is Maintain a Consistent-Hashing Ring associated with Apple?

FastPrep tags this as a Apple phone screen coding practice problem when the problem catalog has that company and stage context.

Maintain a Consistent-Hashing Ring

Apple● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

Maintain the node membership and key ownership of a consistent-hashing ring. Positions increase clockwise, and the last position wraps back to the first. The input supplies already-computed integer hash positions, so you do not implement a hash function.

The ring starts empty. Process the parallel arrays operations and positions from left to right. At index i, apply exactly one operation:

ADD: add a node at positions[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 at positions[i]. Removing a missing node has no effect.
LOOKUP: interpret positions[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 -1 for this lookup.

Return an integer array containing only the LOOKUP results in encounter order. Do not mutate either input array. Each operation observes exactly the membership produced by the preceding operations; future additions are not active early.

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, or LOOKUP.
0 <= positions[i] <= 1000000000.
Positions and the returned node identifiers are integers.