Cuckoo Hashing Kick-Out Chain

Problem

Simulate cuckoo hashing kick-out chains across two tables.

capacity is the size of each table. Table 0 uses key % capacity and table 1 uses (key // capacity) % capacity. Keys are inserted in order; an occupied slot evicts its occupant to the other table, and an insertion fails if the chain exceeds twice the capacity.

Return [failure_count, table0, table1].

Hint

Alternating tables on every kick spreads each key across its two candidate slots.

Test cases

case 1

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

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

case 2

in: [2,[1,3,5]]

expected: [0,[null,5],[1,3]]

case 3

in: [3,[1,2,3]]

expected: [0,[3,1,2],[null,null,null]]

case 4

in: [2,[]]

expected: [0,[null,null],[null,null]]

case 5

in: [1,[0,1,2,3]]

expected: [2,[3],[2]]

Starter codePython

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

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