Question 1257

Every Anagram Same Bucket

A signup service buckets usernames with this function and stores each bucket as a linked list.

def h(s: str) -> int:
    total = 0
    for ch in s:
        total += ord(ch)
    return total % 1024

An attacker wants 5000 distinct usernames that all land in the same bucket, using as little compute as possible. What is the cheapest construction?

A

Brute-force search the space of usernames, evaluating h on each candidate until 5000 land in the target bucket

B

Take one fixed 8-character string and register 5000 of its permutations, since the sum ignores position

C

Register 5000 random usernames, because with 1024 buckets the birthday bound already piles thousands into one bucket

D

Register 5000 usernames whose lengths are all congruent modulo 1024