Robin Hood Hashing Probe Distance

Problem

Insert keys with Robin Hood hashing and report probe distances.

capacity is the table size and keys are inserted in order at key % capacity. A key whose probe distance exceeds the resident's distance steals the slot, pushing the richer resident onward.

Return [max_probe_distance, final_table_keys].

Hint

Stealing from richer residents equalizes probe lengths across the table.

Test cases

case 1

in: [3,[0,3,6]]

expected: [2,[0,3,6]]

case 2

in: [4,[1,5,9,2]]

expected: [2,[2,1,5,9]]

case 3

in: [2,[]]

expected: [0,[null,null]]

case 4

in: [2,[0,1]]

expected: [0,[0,1]]

Starter codePython

def robin_hood(capacity, keys):
    # Your code here
    pass

4 test cases · run your code against them in the editor