Реализуйте упрощенный Bloom filter.
Есть битовый массив размера size, num_hashes hash-функций и список операций:
- ["add", value] — добавить строку в фильтр;
- ["check", value] — проверить строку.
Для check верните "MAYBE_EXISTS", если все нужные биты выставлены, иначе "DOES_NOT_EXIST".
Чтобы автотесты были детерминированными, используйте стабильный hash:
def stable_hash(item: str, salt: int, size: int) -> int:
total = 0
for ch in f"{salt}:{item}":
total = (total * 131 + ord(ch)) % size
return totaldef bloom_filter_trace(size: int, num_hashes: int, operations: list[list[str]]) -> list[str]:size = 32num_hashes = 3operations = [["add","hello"],["check","hello"],["check","world"]]["MAYBE_EXISTS","DOES_NOT_EXIST"]size = 1num_hashes = 2operations = [["add","alpha"],["check","beta"]]["MAYBE_EXISTS"]Маленький фильтр дает false positive
size = 10num_hashes = 2operations = [["add","a"],["add","b"],["check","a"],["check","c"],["add","c"],["check","c"]]["MAYBE_EXISTS","DOES_NOT_EXIST","MAYBE_EXISTS"]