Double Hashing Collision Check

Problem

Find the first pair of strings that collide under two different hash functions.

Each string is hashed with djb2 (start at 5381, then h = (h * 33 + ord(ch)) mod 2**32) and reduced modulo mod1 and mod2. Scan left to right storing the first index for each (mod1, mod2) bucket; a repeated bucket is a double-hash collision.

Return [i, j] with i < j, or [-1, -1] when no pair collides.

Hint

One dictionary keyed by the pair of remainders detects matches in a single pass.

Test cases

case 1

in: [["a","b","c","d","ad"],3,5]

expected: [0,4]

case 2

in: [["a","g"],2,3]

expected: [0,1]

case 3

in: [["a","b","ca"],7,11]

expected: [0,2]

case 4

in: [["x","y","z"],3,5]

expected: [-1,-1]

case 5

in: [["b","c","d","a","ad"],3,5]

expected: [3,4]

Starter codePython

def first_collision_pair(keys, mod1, mod2):
    # Your code here
    pass

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