HardNLPnlp-418

MinHash Signature Minimum

Problem

For each permutation (a, b, m), the MinHash signature value is min over shingle hashes h of (a * h + b) mod m.

Given the shingle hash values and the list of [a, b, m] permutations, return the signature list in permutation order.

Hint

Apply the affine hash under the modulus first, then take the minimum.

case 1

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

expected: [1,0]

case 2

in: [[5],[[3,2,11],[5,4,13]]]

expected: [6,3]

case 3

in: [[10,20],[[1,1,13]]]

expected: [8]

Starter codePython

def minhash_signature_min(shingle_hashes, permutations):
    # Your code here
    pass

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