Quadratic Probe Insert

Problem

Insert a key into an open-addressing hash table using quadratic probing.

Build the table by inserting keys in order, then find the slot for key. Probing starts at key % capacity and visits (base + i*i) % capacity for i = 0, 1, 2, ... Quadratic probes may fail to reach every slot, so give up after capacity attempts.

Return the slot index for the key, or -1 when it cannot be placed.

Hint

The i-th probe lands at (key + i*i) % capacity, so the offsets are squares.

Test cases

case 1

in: [7,[10,20],17]

expected: 4

case 2

in: [5,[0,1,5],6]

expected: 2

case 3

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

expected: -1

case 4

in: [3,[],4]

expected: 1

Starter codePython

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

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