import unittest
import importlib

class TestTask(unittest.TestCase):
    def setUp(self):
        import user_code
        importlib.reload(user_code)
        self.BloomFilter = user_code.BloomFilter

    def test_add_sets_bits(self):
        bf = self.BloomFilter(size=20, hash_count=3)
        before = list(bf.bit_array)
        bf.add("testitem")
        after = list(bf.bit_array)

        changed = sum(a != b for a, b in zip(before, after))

        _dynamic_test(
            self,
            changed >= 1,
            "add() correctly sets one or more bits in the filter.",
            f"add() failed to set any bits. Bit array: {after}",
        )

    def test_contains_true_for_added(self):
        bf = self.BloomFilter(size=30, hash_count=4)
        items = ["cat", "dog", "bird"]

        for item in items:
            bf.add(item)

        for item in items:
            result = bf.contains(item)
            _dynamic_test(
                self,
                result is True,
                f'contains() returns True for added item "{item}".',
                f'False negative: contains() returned False for added item "{item}".',
            )

    def test_contains_false_for_unadded(self):
        bf = self.BloomFilter(size=20, hash_count=3)
        bf.add("a")
        bf.add("b")

        result = bf.contains("zzz_unlikely")
        _dynamic_test(
            self,
            result in (True, False),
            "contains() executes correctly for an unadded item.",
            "contains() failed to execute for an unadded item.",
        )

        # Empty filter must NOT give false positives
        bf2 = self.BloomFilter(size=20, hash_count=3)
        result2 = bf2.contains("never_added")
        _dynamic_test(
            self,
            result2 is False,
            "contains() returns False for an item in an empty filter.",
            "contains() returned True in an empty filter (incorrect false positive).",
        )

    def test_multiple_hash_functions_used(self):
        bf = self.BloomFilter(size=50, hash_count=5)
        indices1 = bf._hashes("x")
        indices2 = bf._hashes("y")

        _dynamic_test(
            self,
            isinstance(indices1, list) and len(indices1) == 5 and
            isinstance(indices2, list) and len(indices2) == 5,
            "_hashes() returns correct number of indices.",
            f"_hashes() returned incorrect results: {indices1}, {indices2}",
        )

        _dynamic_test(
            self,
            len(set(indices1)) > 1,
            "Multiple hash functions produce different indices.",
            "All hash outputs were identical — must use multiple hash functions.",
        )

    def test_no_false_negatives(self):
        bf = self.BloomFilter(size=30, hash_count=4)
        items = ["red", "blue", "green"]

        for item in items:
            bf.add(item)

        for item in items:
            result = bf.contains(item)
            _dynamic_test(
                self,
                result is True,
                f'contains() correctly avoids false negatives for "{item}".',
                f'False negative detected: "{item}" was added but not found.',
            )

def _dynamic_test(test_case, condition, success_message, failure_message):
    if condition:
        test_case._testMethodName = success_message
        test_case.assertTrue(True, success_message)
    else:
        test_case._testMethodName = failure_message
        test_case.fail(failure_message)

if __name__ == "__main__":
    unittest.main()

test_main.py

A comprehensive course exploring the foundational algorithms and data structures that underpin modern data engineering and large-scale data systems. Learn how sorting, hashing, indexing, and probabilistic structures power real-world data infrastructure, with conceptual explanations and practical Python demonstrations.

Explore the essential algorithms for processing and organizing data efficiently, including sorting, hashing, and key-value lookup structures, with practical Python demonstrations.

Examine the tree-based and heap-based data structures that power fast search, indexing, and data organization in modern storage engines.

Delve into memory-efficient, approximate data structures and algorithms for high-throughput, streaming, and big-data scenarios.

Challenge: Implement a Bloom Filter

Soluzione

Challenge: Implement a Bloom Filter

Soluzione