Open Addressing Linear Probe Insert

Problem

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

Build the table by inserting keys in order, then find the slot for key. Probing starts at key % capacity and advances one slot at a time, wrapping around. A key already present is considered found at its existing slot.

Return the slot index where the key is or would be stored, or -1 when the table is full and the key is absent.

Hint

Duplicate keys occupy their original slot, so the probe stops on either an empty slot or a match.

Test cases

case 1

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

expected: 4

case 2

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

expected: 3

case 3

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

expected: -1

case 4

in: [5,[],8]

expected: 3

case 5

in: [4,[4,8],0]

expected: 2

Starter codePython

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

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