def simple_hash_demo():
    """
    Demonstrate how hash functions convert words to numbers
    """
    print("🎯 HASH FUNCTION DEMONSTRATION")
    print("=" * 40)
 
    def hash_function_1(text):
        """First magic formula: sum of letter positions"""
        total = 0
        for char in text.lower():
            if char.isalpha():
                total += ord(char) - ord('a') + 1  # a=1, b=2, c=3, etc.
        return total
 
    def hash_function_2(text):
        """Second magic formula: alternating sum"""
        total = 0
        for i, char in enumerate(text.lower()):
            if char.isalpha():
                value = ord(char) - ord('a') + 1
                if i % 2 == 0:
                    total += value
                else:
                    total -= value
        return abs(total)
 
    def hash_function_3(text):
        """Third magic formula: multiply and shift"""
        total = 1
        for char in text.lower():
            if char.isalpha():
                total = (total * 7 + ord(char)) % 1000
        return total
 
    # Test with different words
    test_words = ["apple", "banana", "cherry", "dog", "elephant"]
 
    print("Word      | Hash 1 | Hash 2 | Hash 3")
    print("-" * 35)
 
    for word in test_words:
        h1 = hash_function_1(word)
        h2 = hash_function_2(word)
        h3 = hash_function_3(word)
        print(f"{word:9} | {h1:6} | {h2:6} | {h3:6}")
 
    print("\n💡 Key Point: Same word always gives same numbers!")
    print("🎯 Different words usually give different numbers!")
 
# Run the demonstration
if __name__ <mark class="obsidian-highlight"> "__main__":
    simple_hash_demo()

public class SimpleHashDemo {
 
    /**
     * Demonstrate how hash functions convert words to numbers
     */
    public static void simpleHashDemo() {
        System.out.println("🎯 HASH FUNCTION DEMONSTRATION");
        System.out.println("</mark>======================================");
 
        // Test with different words
        String[] testWords = {"apple", "banana", "cherry", "dog", "elephant"};
 
        System.out.println("Word      | Hash 1 | Hash 2 | Hash 3");
        System.out.println("-----------------------------------");
 
        for (String word : testWords) {
            int h1 = hashFunction1(word);
            int h2 = hashFunction2(word);
            int h3 = hashFunction3(word);
            System.out.printf("%-9s | %6d | %6d | %6d%n", word, h1, h2, h3);
        }
 
        System.out.println("\n💡 Key Point: Same word always gives same numbers!");
        System.out.println("🎯 Different words usually give different numbers!");
    }
 
    /**
     * First magic formula: sum of letter positions
     */
    private static int hashFunction1(String text) {
        int total = 0;
        for (char c : text.toLowerCase().toCharArray()) {
            if (Character.isLetter(c)) {
                total += c - 'a' + 1; // a=1, b=2, c=3, etc.
            }
        }
        return total;
    }
 
    /**
     * Second magic formula: alternating sum
     */
    private static int hashFunction2(String text) {
        int total = 0;
        char[] chars = text.toLowerCase().toCharArray();
 
        for (int i = 0; i < chars.length; i++) {
            if (Character.isLetter(chars[i])) {
                int value = chars[i] - 'a' + 1;
                if (i % 2 == 0) {
                    total += value;
                } else {
                    total -= value;
                }
            }
        }
        return Math.abs(total);
    }
 
    /**
     * Third magic formula: multiply and shift
     */
    private static int hashFunction3(String text) {
        int total = 1;
        for (char c : text.toLowerCase().toCharArray()) {
            if (Character.isLetter(c)) {
                total = (total * 7 + c) % 1000;
            }
        }
        return total;
    }
 
    // Run the demonstration
    public static void main(String[] args) {
        simpleHashDemo();
    }
}

import hashlib
import math
from typing import List, Set
 
class BloomFilter:
    """
    A space-efficient probabilistic data structure for membership testing
 
    - Can tell you if an item is DEFINITELY NOT in a set
    - Can tell you if an item MIGHT BE in a set
    - Uses much less memory than storing the actual items
    """
 
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        """
        Initialize Bloom Filter with optimal parameters
 
        Args:
            expected_items: How many items you plan to add
            false_positive_rate: Desired probability of false positives (0.01 = 1%)
        """
        self.expected_items = expected_items
        self.false_positive_rate = false_positive_rate
 
        # Calculate optimal bit array size
        self.bit_array_size = self._calculate_bit_array_size()
 
        # Calculate optimal number of hash functions
        self.num_hash_functions = self._calculate_hash_functions()
 
        # Initialize bit array (all zeros)
        self.bit_array = [0] * self.bit_array_size
 
        # Track items added for verification
        self.items_added = 0
 
        print(f"🎪 Bloom Filter Created!")
        print(f"   📊 Expected items: {expected_items:,}")
        print(f"   🎯 False positive rate: {false_positive_rate:.1%}")
        print(f"   💾 Bit array size: {self.bit_array_size:,} bits ({self.bit_array_size/8:.0f} bytes)")
        print(f"   🔢 Hash functions: {self.num_hash_functions}")
        print()
 
    def _calculate_bit_array_size(self) -> int:
        """Calculate optimal bit array size using mathematical formula"""
        # Formula: m = -(n * ln(p)) / (ln(2)^2)
        # Where: n = expected items, p = false positive rate, m = bit array size
 
        n = self.expected_items
        p = self.false_positive_rate
 
        m = -(n * math.log(p)) / (math.log(2) ** 2)
        return int(math.ceil(m))
 
    def _calculate_hash_functions(self) -> int:
        """Calculate optimal number of hash functions"""
        # Formula: k = (m/n) * ln(2)
        # Where: m = bit array size, n = expected items, k = number of hash functions
 
        m = self.bit_array_size
        n = self.expected_items
 
        k = (m / n) * math.log(2)
        return int(math.ceil(k))
 
    def _get_hash_values(self, item: str) -> List[int]:
        """
        Generate multiple hash values for an item using different hash functions
 
        Args:
            item: The item to hash
 
        Returns:
            List of hash values (positions in bit array)
        """
        # Convert item to bytes for hashing
        item_bytes = item.encode('utf-8')
 
        hash_values = []
 
        for i in range(self.num_hash_functions):
            # Create different hash functions by adding a salt
            salted_item = f"{item}_{i}".encode('utf-8')
 
            # Use SHA256 hash function
            hash_obj = hashlib.sha256(salted_item)
            hash_int = int(hash_obj.hexdigest(), 16)
 
            # Map to bit array index
            bit_index = hash_int % self.bit_array_size
            hash_values.append(bit_index)
 
        return hash_values
 
    def add(self, item: str) -> None:
        """
        Add an item to the Bloom filter
 
        Args:
            item: The item to add
        """
        # Get hash positions for this item
        hash_positions = self._get_hash_values(item)
 
        # Set bits at those positions to 1
        for position in hash_positions:
            self.bit_array[position] = 1
 
        self.items_added += 1
 
        print(f"➕ Added '{item}' → positions: {hash_positions}")
 
    def might_contain(self, item: str) -> bool:
        """
        Check if item might be in the filter
 
        Args:
            item: The item to check
 
        Returns:
            True if item MIGHT be in the set
            False if item is DEFINITELY NOT in the set
        """
        # Get hash positions for this item
        hash_positions = self._get_hash_values(item)
 
        # Check if ALL positions are set to 1
        for position in hash_positions:
            if self.bit_array[position] <mark class="obsidian-highlight"> 0:
                print(f"❌ '{item}' is DEFINITELY NOT in set (position {position} is 0)")
                return False
 
        print(f"✅ '{item}' MIGHT be in set (all positions {hash_positions} are 1)")
        return True
 
    def get_current_false_positive_rate(self) -> float:
        """Calculate current false positive probability"""
        if self.items_added </mark> 0:
            return 0.0
 
        # Count number of bits set to 1
        bits_set = sum(self.bit_array)
 
        # Probability that a random bit is 1
        prob_bit_is_1 = bits_set / self.bit_array_size
 
        # Probability of false positive
        false_positive_prob = prob_bit_is_1 ** self.num_hash_functions
 
        return false_positive_prob
 
    def show_statistics(self) -> None:
        """Display detailed statistics about the Bloom filter"""
        bits_set = sum(self.bit_array)
        fill_ratio = bits_set / self.bit_array_size
        current_fp_rate = self.get_current_false_positive_rate()
 
        print(f"📊 BLOOM FILTER STATISTICS")
        print(f"=" * 35)
        print(f"🎯 Items added: {self.items_added:,}")
        print(f"💡 Bits set: {bits_set:,} / {self.bit_array_size:,}")
        print(f"📈 Fill ratio: {fill_ratio:.1%}")
        print(f"🎲 Expected FP rate: {self.false_positive_rate:.1%}")
        print(f"🎲 Current FP rate: {current_fp_rate:.1%}")
        print(f"💾 Memory used: {len(self.bit_array)} bits = {len(self.bit_array)/8:.0f} bytes")
 
        # Compare with storing actual items
        estimated_item_size = 20  # Average string length
        normal_memory = self.items_added * estimated_item_size
        bloom_memory = len(self.bit_array) // 8
        memory_savings = (1 - bloom_memory / max(normal_memory, 1)) * 100
 
        print(f"💰 Memory vs storing items: {bloom_memory} vs {normal_memory} bytes")
        print(f"💰 Memory savings: {memory_savings:.1f}%")
        print()
 
    def visualize_bit_array(self, start: int = 0, length: int = 50) -> None:
        """Show a visual representation of part of the bit array"""
        if start + length > self.bit_array_size:
            length = self.bit_array_size - start
 
        print(f"🔍 Bit Array Visualization (positions {start}-{start+length-1}):")
 
        # Show position numbers
        positions = [str(i % 10) for i in range(start, start + length)]
        print("Pos: " + "".join(positions))
 
        # Show bit values
        bits = [str(self.bit_array[i]) for i in range(start, start + length)]
        print("Bit: " + "".join(bits))
 
        # Show visual representation
        visual = ["█" if self.bit_array[i] == 1 else "░" for i in range(start, start + length)]
        print("     " + "".join(visual))
        print("     █ = 1 (set)    ░ = 0 (not set)")
        print()
 
### **☕ Java Implementation - Complete Bloom Filter**:
 
```java
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
import java.math.*;
 
/**
 * A space-efficient probabilistic data structure for membership testing
 *
 * - Can tell you if an item is DEFINITELY NOT in a set
 * - Can tell you if an item MIGHT BE in a set
 * - Uses much less memory than storing the actual items
 */
public class BloomFilter {
 
    private final int expectedItems;
    private final double falsePositiveRate;
    private final int bitArraySize;
    private final int numHashFunctions;
    private final BitSet bitArray;
    private int itemsAdded;
 
    /**
     * Initialize Bloom Filter with optimal parameters
     *
     * @param expectedItems How many items you plan to add
     * @param falsePositiveRate Desired probability of false positives (0.01 = 1%)
     */
    public BloomFilter(int expectedItems, double falsePositiveRate) {
        this.expectedItems = expectedItems;
        this.falsePositiveRate = falsePositiveRate;
 
        // Calculate optimal bit array size
        this.bitArraySize = calculateBitArraySize();
 
        // Calculate optimal number of hash functions
        this.numHashFunctions = calculateHashFunctions();
 
        // Initialize bit array (all zeros)
        this.bitArray = new BitSet(bitArraySize);
 
        // Track items added for verification
        this.itemsAdded = 0;
 
        System.out.println("🎪 Bloom Filter Created!");
        System.out.printf("   📊 Expected items: %,d%n", expectedItems);
        System.out.printf("   🎯 False positive rate: %.1f%%%n", falsePositiveRate * 100);
        System.out.printf("   💾 Bit array size: %,d bits (%,.0f bytes)%n",
                         bitArraySize, bitArraySize / 8.0);
        System.out.printf("   🔢 Hash functions: %d%n", numHashFunctions);
        System.out.println();
    }
 
    /**
     * Calculate optimal bit array size using mathematical formula
     */
    private int calculateBitArraySize() {
        // Formula: m = -(n * ln(p)) / (ln(2)^2)
        // Where: n = expected items, p = false positive rate, m = bit array size
 
        double n = expectedItems;
        double p = falsePositiveRate;
 
        double m = -(n * Math.log(p)) / Math.pow(Math.log(2), 2);
        return (int) Math.ceil(m);
    }
 
    /**
     * Calculate optimal number of hash functions
     */
    private int calculateHashFunctions() {
        // Formula: k = (m/n) * ln(2)
        // Where: m = bit array size, n = expected items, k = number of hash functions
 
        double m = bitArraySize;
        double n = expectedItems;
 
        double k = (m / n) * Math.log(2);
        return (int) Math.ceil(k);
    }
 
    /**
     * Generate multiple hash values for an item using different hash functions
     *
     * @param item The item to hash
     * @return Array of hash values (positions in bit array)
     */
    private int[] getHashValues(String item) {
        int[] hashValues = new int[numHashFunctions];
 
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
 
            for (int i = 0; i < numHashFunctions; i++) {
                // Create different hash functions by adding a salt
                String saltedItem = item + "_" + i;
                byte[] hashBytes = md.digest(saltedItem.getBytes());
 
                // Convert to positive integer
                int hashInt = Math.abs(bytesToInt(hashBytes));
 
                // Map to bit array index
                hashValues[i] = hashInt % bitArraySize;
            }
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("SHA-256 not available", e);
        }
 
        return hashValues;
    }
 
    /**
     * Helper method to convert bytes to integer
     */
    private int bytesToInt(byte[] bytes) {
        int result = 0;
        for (int i = 0; i < Math.min(4, bytes.length); i++) {
            result |= (bytes[i] & 0xFF) << (8 * i);
        }
        return result;
    }
 
    /**
     * Add an item to the Bloom filter
     *
     * @param item The item to add
     */
    public void add(String item) {
        // Get hash positions for this item
        int[] hashPositions = getHashValues(item);
 
        // Set bits at those positions to 1
        for (int position : hashPositions) {
            bitArray.set(position);
        }
 
        itemsAdded++;
 
        System.out.printf("➕ Added '%s' → positions: %s%n",
                         item, java.util.Arrays.toString(hashPositions));
    }
 
    /**
     * Check if item might be in the filter
     *
     * @param item The item to check
     * @return true if item MIGHT be in the set, false if DEFINITELY NOT
     */
    public boolean mightContain(String item) {
        // Get hash positions for this item
        int[] hashPositions = getHashValues(item);
 
        // Check if ALL positions are set to 1
        for (int position : hashPositions) {
            if (!bitArray.get(position)) {
                System.out.printf("❌ '%s' is DEFINITELY NOT in set (position %d is 0)%n",
                                item, position);
                return false;
            }
        }
 
        System.out.printf("✅ '%s' MIGHT be in set (all positions %s are 1)%n",
                         item, java.util.Arrays.toString(hashPositions));
        return true;
    }
 
    /**
     * Calculate current false positive probability
     */
    public double getCurrentFalsePositiveRate() {
        if (itemsAdded == 0) {
            return 0.0;
        }
 
        // Count number of bits set to 1
        int bitsSet = bitArray.cardinality();
 
        // Probability that a random bit is 1
        double probBitIsOne = (double) bitsSet / bitArraySize;
 
        // Probability of false positive
        return Math.pow(probBitIsOne, numHashFunctions);
    }
 
    /**
     * Display detailed statistics about the Bloom filter
     */
    public void showStatistics() {
        int bitsSet = bitArray.cardinality();
        double fillRatio = (double) bitsSet / bitArraySize;
        double currentFpRate = getCurrentFalsePositiveRate();
 
        System.out.println("📊 BLOOM FILTER STATISTICS");
        System.out.println("===================================");
        System.out.printf("🎯 Items added: %,d%n", itemsAdded);
        System.out.printf("💡 Bits set: %,d / %,d%n", bitsSet, bitArraySize);
        System.out.printf("📈 Fill ratio: %.1f%%%n", fillRatio * 100);
        System.out.printf("🎲 Expected FP rate: %.1f%%%n", falsePositiveRate * 100);
        System.out.printf("🎲 Current FP rate: %.1f%%%n", currentFpRate * 100);
        System.out.printf("💾 Memory used: %d bits = %,.0f bytes%n",
                         bitArraySize, bitArraySize / 8.0);
 
        // Compare with storing actual items
        int estimatedItemSize = 20; // Average string length
        int normalMemory = itemsAdded * estimatedItemSize;
        int bloomMemory = bitArraySize / 8;
        double memorySavings = (1.0 - (double) bloomMemory / Math.max(normalMemory, 1)) * 100;
 
        System.out.printf("💰 Memory vs storing items: %d vs %d bytes%n",
                         bloomMemory, normalMemory);
        System.out.printf("💰 Memory savings: %.1f%%%n", memorySavings);
        System.out.println();
    }
 
    /**
     * Show a visual representation of part of the bit array
     */
    public void visualizeBitArray(int start, int length) {
        if (start + length > bitArraySize) {
            length = bitArraySize - start;
        }
 
        System.out.printf("🔍 Bit Array Visualization (positions %d-%d):%n",
                         start, start + length - 1);
 
        // Show position numbers
        System.out.print("Pos: ");
        for (int i = start; i < start + length; i++) {
            System.out.print(i % 10);
        }
        System.out.println();
 
        // Show bit values
        System.out.print("Bit: ");
        for (int i = start; i < start + length; i++) {
            System.out.print(bitArray.get(i) ? "1" : "0");
        }
        System.out.println();
 
        // Show visual representation
        System.out.print("     ");
        for (int i = start; i < start + length; i++) {
            System.out.print(bitArray.get(i) ? "█" : "░");
        }
        System.out.println();
        System.out.println("     █ = 1 (set)    ░ = 0 (not set)");
        System.out.println();
    }
}

/**
 * Comprehensive demonstration of Bloom filter capabilities
 */
public class BloomFilterDemo {
 
    public static BloomFilter demonstrateBloomFilter() {
        System.out.println("🎪 BLOOM FILTER COMPREHENSIVE DEMO");
        System.out.println("=============================================");
        System.out.println();
 
        // Create Bloom filter expecting 1000 items with 1% false positive rate
        BloomFilter bloom = new BloomFilter(1000, 0.01);
 
        // Add some fruits to the filter
        String[] fruitsToAdd = {
            "apple", "banana", "cherry", "date", "elderberry",
            "fig", "grape", "honeydew", "kiwi", "lemon"
        };
 
        System.out.println("🍎 Adding fruits to the Bloom filter:");
        for (String fruit : fruitsToAdd) {
            bloom.add(fruit);
        }
 
        System.out.println();
 
        // Test items that ARE in the filter
        System.out.println("✅ Testing fruits that ARE in the filter:");
        String[] testFruitsIn = {"apple", "banana", "grape"};
        for (String fruit : testFruitsIn) {
            boolean result = bloom.mightContain(fruit);
            System.out.printf("   Result: %b%n", result);
        }
 
        System.out.println();
 
        // Test items that are NOT in the filter
        System.out.println("❌ Testing fruits that are NOT in the filter:");
        String[] testFruitsNot = {"orange", "pear", "mango"};
        for (String fruit : testFruitsNot) {
            boolean result = bloom.mightContain(fruit);
            System.out.printf("   Result: %b%n", result);
        }
 
        System.out.println();
 
        // Show statistics
        bloom.showStatistics();
 
        // Show bit array visualization
        bloom.visualizeBitArray(0, 100);
 
        return bloom;
    }
 
    public static void main(String[] args) {
        demonstrateBloomFilter();
    }
}

class BitcoinTransactionFilter:
    """
    Bitcoin-style Bloom filter for lightweight clients
    Helps mobile wallets find their transactions efficiently
    """
 
    def __init__(self, wallet_addresses: List[str]):
        # Create Bloom filter for wallet's addresses and transactions
        self.transaction_filter = BloomFilter(expected_items=10000, false_positive_rate=0.01)
        self.wallet_addresses = set(wallet_addresses)
 
        print("₿ BITCOIN TRANSACTION FILTER")
        print("=" * 35)
        print(f"👛 Wallet addresses: {len(wallet_addresses)}")
 
        # Add wallet addresses to filter
        for address in wallet_addresses:
            self.transaction_filter.add(address)
            print(f"   Added address: {address[:10]}...")
 
        print()
 
    def add_transaction_interest(self, transaction_id: str):
        """Add a transaction ID we're interested in"""
        self.transaction_filter.add(transaction_id)
 
    def should_download_block(self, block_transactions: List[str]) -> bool:
        """
        Check if a block might contain transactions relevant to our wallet
 
        Args:
            block_transactions: List of transaction IDs in the block
 
        Returns:
            True if block might contain relevant transactions
            False if block definitely doesn't contain relevant transactions
        """
        # Check if any transaction in the block might be relevant
        for tx_id in block_transactions:
            if self.transaction_filter.might_contain(tx_id):
                return True
 
        return False
 
    def demonstrate_bitcoin_filtering(self):
        """Show how Bitcoin lightweight clients work"""
        print("₿ BITCOIN LIGHTWEIGHT CLIENT SIMULATION")
        print("=" * 45)
 
        # Simulate blockchain blocks with transaction IDs
        blockchain_blocks = [
            {
                'block_id': 1,
                'transactions': ['tx001', 'tx002', 'tx003', 'wallet_addr_1', 'tx004']
            },
            {
                'block_id': 2,
                'transactions': ['tx005', 'tx006', 'tx007', 'tx008']
            },
            {
                'block_id': 3,
                'transactions': ['tx009', 'wallet_addr_2', 'tx010', 'tx011']
            },
            {
                'block_id': 4,
                'transactions': ['tx012', 'tx013', 'tx014', 'tx015']
            }
        ]
 
        blocks_to_download = []
 
        print("📦 Scanning blockchain blocks:")
        for block in blockchain_blocks:
            should_download = self.should_download_block(block['transactions'])
 
            status = "DOWNLOAD" if should_download else "SKIP"
            print(f"   Block {block['block_id']}: {status}")
 
            if should_download:
                blocks_to_download.append(block['block_id'])
 
                # Show which transactions triggered the download
                for tx in block['transactions']:
                    if self.transaction_filter.might_contain(tx):
                        print(f"      → Found relevant: {tx}")
 
        print()
        print(f"📥 Downloading {len(blocks_to_download)} out of {len(blockchain_blocks)} blocks")
        print(f"💰 Bandwidth saved: {((len(blockchain_blocks) - len(blocks_to_download)) / len(blockchain_blocks) * 100):.0f}%")
 
# Demonstrate Bitcoin filtering
def demonstrate_bitcoin_filter():
    """Show Bitcoin's transaction filtering approach"""
    # Simulate a mobile wallet with some addresses
    wallet_addresses = [
        "wallet_addr_1",
        "wallet_addr_2",
        "wallet_addr_3"
    ]
 
    bitcoin_filter = BitcoinTransactionFilter(wallet_addresses)
    bitcoin_filter.demonstrate_bitcoin_filtering()
 
if __name__ == "__main__":
    demonstrate_bitcoin_filter()

class YouTubeRecommendationFilter:
    """
    YouTube-style Bloom filter for video recommendations
    Helps avoid recommending videos users have already watched
    """
 
    def __init__(self, user_id: str):
        self.user_id = user_id
 
        # Create Bloom filter for watched videos
        self.watched_videos = BloomFilter(expected_items=50000, false_positive_rate=0.02)
 
        # Create Bloom filter for disliked videos
        self.disliked_videos = BloomFilter(expected_items=5000, false_positive_rate=0.01)
 
        print(f"📺 YOUTUBE RECOMMENDATION FILTER")
        print(f"=" * 40)
        print(f"👤 User: {user_id}")
        print(f"🎥 Watched videos filter ready")
        print(f"👎 Disliked videos filter ready")
        print()
 
    def mark_video_watched(self, video_id: str):
        """Mark a video as watched"""
        self.watched_videos.add(video_id)
        print(f"✅ Marked as watched: {video_id}")
 
    def mark_video_disliked(self, video_id: str):
        """Mark a video as disliked"""
        self.disliked_videos.add(video_id)
        print(f"👎 Marked as disliked: {video_id}")
 
    def should_recommend_video(self, video_id: str) -> tuple[bool, str]:
        """
        Check if a video should be recommended to the user
 
        Returns:
            (should_recommend, reason)
        """
        # Check if user has watched this video
        if self.watched_videos.might_contain(video_id):
            return False, "Already watched"
 
        # Check if user has disliked this video
        if self.disliked_videos.might_contain(video_id):
            return False, "Previously disliked"
 
        return True, "Good to recommend"
 
    def demonstrate_youtube_recommendations(self):
        """Show how YouTube recommendation filtering works"""
        print("📺 YOUTUBE RECOMMENDATION SIMULATION")
        print("=" * 45)
 
        # Simulate user watching some videos
        watched_videos = [
            "funny_cats_2024",
            "cooking_tutorial_pasta",
            "music_video_pop_hit",
            "tech_review_phone",
            "gaming_stream_highlights"
        ]
 
        print("🎬 User watching history:")
        for video in watched_videos:
            self.mark_video_watched(video)
 
        print()
 
        # User dislikes some videos
        disliked_videos = [
            "boring_lecture_math",
            "annoying_ad_product"
        ]
 
        print("👎 User dislikes:")
        for video in disliked_videos:
            self.mark_video_disliked(video)
 
        print()
 
        # Test recommendation candidates
        candidate_videos = [
            "funny_cats_2024",        # Already watched
            "new_funny_cats_2024",    # New, should recommend
            "cooking_tutorial_pizza", # New, should recommend
            "boring_lecture_math",    # Previously disliked
            "tech_review_laptop",     # New, should recommend
            "music_video_pop_hit",    # Already watched
            "gaming_new_release"      # New, should recommend
        ]
 
        print("🎯 Testing recommendation candidates:")
        print("-" * 40)
 
        recommended_count = 0
        filtered_count = 0
 
        for video in candidate_videos:
            should_recommend, reason = self.should_recommend_video(video)
 
            if should_recommend:
                print(f"✅ RECOMMEND: {video:25} ({reason})")
                recommended_count += 1
            else:
                print(f"❌ FILTER:    {video:25} ({reason})")
                filtered_count += 1
 
        print()
        print(f"📊 Results:")
        print(f"   Recommended: {recommended_count}")
        print(f"   Filtered out: {filtered_count}")
        print(f"   Efficiency: {(filtered_count / len(candidate_videos) * 100):.0f}% filtered")
 
# Demonstrate YouTube filtering
def demonstrate_youtube_filter():
    """Show YouTube's recommendation filtering approach"""
    youtube_filter = YouTubeRecommendationFilter("user_12345")
    youtube_filter.demonstrate_youtube_recommendations()
 
if __name__ == "__main__":
    demonstrate_youtube_filter()

class CountingBloomFilter:
    """
    Counting Bloom Filter - supports insertions AND deletions
    Uses counters instead of bits
    """
 
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01):
        self.expected_items = expected_items
        self.false_positive_rate = false_positive_rate
 
        # Calculate parameters (same as regular Bloom filter)
        self.bit_array_size = self._calculate_bit_array_size()
        self.num_hash_functions = self._calculate_hash_functions()
 
        # Use counters instead of bits (4-bit counters = max count 15)
        self.counters = [0] * self.bit_array_size
        self.max_counter_value = 15
 
        print(f"🧮 COUNTING BLOOM FILTER CREATED")
        print(f"   📊 Counter array size: {self.bit_array_size:,}")
        print(f"   🔢 Hash functions: {self.num_hash_functions}")
        print(f"   📈 Max counter value: {self.max_counter_value}")
        print()
 
    def _calculate_bit_array_size(self) -> int:
        """Same calculation as regular Bloom filter"""
        n = self.expected_items
        p = self.false_positive_rate
        m = -(n * math.log(p)) / (math.log(2) ** 2)
        return int(math.ceil(m))
 
    def _calculate_hash_functions(self) -> int:
        """Same calculation as regular Bloom filter"""
        m = self.bit_array_size
        n = self.expected_items
        k = (m / n) * math.log(2)
        return int(math.ceil(k))
 
    def _get_hash_values(self, item: str) -> List[int]:
        """Same hash function as regular Bloom filter"""
        item_bytes = item.encode('utf-8')
        hash_values = []
 
        for i in range(self.num_hash_functions):
            salted_item = f"{item}_{i}".encode('utf-8')
            hash_obj = hashlib.sha256(salted_item)
            hash_int = int(hash_obj.hexdigest(), 16)
            bit_index = hash_int % self.bit_array_size
            hash_values.append(bit_index)
 
        return hash_values
 
    def add(self, item: str) -> bool:
        """
        Add item to counting Bloom filter
 
        Returns:
            True if successfully added
            False if counter would overflow
        """
        hash_positions = self._get_hash_values(item)
 
        # Check if any counter would overflow
        for position in hash_positions:
            if self.counters[position] >= self.max_counter_value:
                print(f"⚠️ Cannot add '{item}': counter overflow at position {position}")
                return False
 
        # Increment all counters
        for position in hash_positions:
            self.counters[position] += 1
 
        print(f"➕ Added '{item}' → incremented counters at: {hash_positions}")
        return True
 
    def remove(self, item: str) -> bool:
        """
        Remove item from counting Bloom filter
 
        Returns:
            True if successfully removed
            False if item was not in filter (any counter is 0)
        """
        hash_positions = self._get_hash_values(item)
 
        # Check if item might be in filter (all counters > 0)
        for position in hash_positions:
            if self.counters[position] == 0:
                print(f"❌ Cannot remove '{item}': not in filter (counter {position} is 0)")
                return False
 
        # Decrement all counters
        for position in hash_positions:
            self.counters[position] -= 1
 
        print(f"➖ Removed '{item}' → decremented counters at: {hash_positions}")
        return True
 
    def might_contain(self, item: str) -> bool:
        """Check if item might be in the filter"""
        hash_positions = self._get_hash_values(item)
 
        for position in hash_positions:
            if self.counters[position] == 0:
                return False
 
        return True
 
    def show_counters(self, start: int = 0, length: int = 20):
        """Show counter values"""
        if start + length > len(self.counters):
            length = len(self.counters) - start
 
        print(f"🧮 Counter Values (positions {start}-{start+length-1}):")
        positions = [f"{i%10}" for i in range(start, start + length)]
        values = [f"{self.counters[i]}" for i in range(start, start + length)]
 
        print("Pos: " + " ".join(f"{p:>2}" for p in positions))
        print("Val: " + " ".join(f"{v:>2}" for v in values))
        print()
 
def demonstrate_counting_bloom_filter():
    """Demonstrate counting Bloom filter with add/remove operations"""
    print("🧮 COUNTING BLOOM FILTER DEMONSTRATION")
    print("=" * 45)
 
    # Create counting Bloom filter
    cbf = CountingBloomFilter(expected_items=100, false_positive_rate=0.01)
 
    # Add some items
    items_to_add = ["apple", "banana", "cherry"]
 
    print("➕ Adding items:")
    for item in items_to_add:
        cbf.add(item)
 
    print()
    cbf.show_counters(0, 30)
 
    # Test membership
    print("🔍 Testing membership:")
    test_items = ["apple", "banana", "orange", "cherry"]
    for item in test_items:
        result = cbf.might_contain(item)
        status = "MIGHT BE PRESENT" if result else "DEFINITELY NOT PRESENT"
        print(f"   '{item}': {status}")
 
    print()
 
    # Remove some items
    print("➖ Removing items:")
    cbf.remove("banana")
    cbf.remove("apple")
 
    print()
    cbf.show_counters(0, 30)
 
    # Test membership after removal
    print("🔍 Testing membership after removals:")
    for item in test_items:
        result = cbf.might_contain(item)
        status = "MIGHT BE PRESENT" if result else "DEFINITELY NOT PRESENT"
        print(f"   '{item}': {status}")
 
if __name__ == "__main__":
    demonstrate_counting_bloom_filter()

class ScalableBloomFilter:
    """
    Scalable Bloom Filter - grows automatically as more items are added
    Maintains constant false positive rate even with unknown number of items
    """
 
    def __init__(self, initial_capacity: int = 1000, false_positive_rate: float = 0.01,
                 growth_rate: int = 2):
        self.initial_capacity = initial_capacity
        self.false_positive_rate = false_positive_rate
        self.growth_rate = growth_rate
 
        # List of Bloom filters (we add more as needed)
        self.filters: List[BloomFilter] = []
 
        # Create first filter
        self._add_new_filter(initial_capacity)
 
        # Track total items added
        self.total_items = 0
 
        print(f"📈 SCALABLE BLOOM FILTER CREATED")
        print(f"   🎯 Initial capacity: {initial_capacity:,}")
        print(f"   📊 False positive rate: {false_positive_rate:.1%}")
        print(f"   📈 Growth rate: {growth_rate}x")
        print()
 
    def _add_new_filter(self, capacity: int) -> None:
        """Add a new Bloom filter to the collection"""
        # Each new filter gets a tighter false positive rate
        # to maintain overall target rate
        filter_fp_rate = self.false_positive_rate * (0.5 ** len(self.filters))
 
        new_filter = BloomFilter(expected_items=capacity,
                               false_positive_rate=filter_fp_rate)
 
        self.filters.append(new_filter)
 
        print(f"🆕 Added filter #{len(self.filters)}")
        print(f"   Capacity: {capacity:,}")
        print(f"   FP rate: {filter_fp_rate:.4%}")
        print()
 
    def add(self, item: str) -> None:
        """Add item to the scalable Bloom filter"""
        current_filter = self.filters[-1]  # Most recent filter
 
        # Check if current filter is getting full
        # (rough estimate: when we've added expected_items)
        if current_filter.items_added >= current_filter.expected_items:
            # Create new filter with increased capacity
            new_capacity = self.initial_capacity * (self.growth_rate ** len(self.filters))
            self._add_new_filter(new_capacity)
            current_filter = self.filters[-1]
 
        # Add to current filter
        current_filter.add(item)
        self.total_items += 1
 
    def might_contain(self, item: str) -> bool:
        """Check if item might be in any of the filters"""
        # Check all filters (if any returns True, item might be present)
        for i, bloom_filter in enumerate(self.filters):
            if bloom_filter.might_contain(item):
                print(f"   Found potential match in filter #{i+1}")
                return True
 
        print(f"   Not found in any of {len(self.filters)} filters")
        return False
 
    def get_statistics(self) -> dict:
        """Get comprehensive statistics about the scalable filter"""
        total_memory = sum(len(f.bit_array) for f in self.filters) // 8  # bytes
        total_expected_capacity = sum(f.expected_items for f in self.filters)
 
        return {
            'num_filters': len(self.filters),
            'total_items_added': self.total_items,
            'total_expected_capacity': total_expected_capacity,
            'total_memory_bytes': total_memory,
            'average_fill_ratio': self.total_items / total_expected_capacity if total_expected_capacity > 0 else 0
        }
 
    def show_detailed_status(self) -> None:
        """Show detailed status of all filters"""
        stats = self.get_statistics()
 
        print(f"📈 SCALABLE BLOOM FILTER STATUS")
        print(f"=" * 40)
        print(f"🔢 Number of filters: {stats['num_filters']}")
        print(f"📊 Total items added: {stats['total_items_added']:,}")
        print(f"📈 Total capacity: {stats['total_expected_capacity']:,}")
        print(f"💾 Total memory: {stats['total_memory_bytes']:,} bytes")
        print(f"📊 Average fill: {stats['average_fill_ratio']:.1%}")
        print()
 
        print("Individual filter details:")
        print("Filter | Items | Capacity | Fill% | Memory")
        print("-" * 45)
 
        for i, bloom_filter in enumerate(self.filters):
            fill_ratio = bloom_filter.items_added / bloom_filter.expected_items * 100
            memory_bytes = len(bloom_filter.bit_array) // 8
 
            print(f"  #{i+1:2}   | {bloom_filter.items_added:5} | "
                  f"{bloom_filter.expected_items:8} | {fill_ratio:4.1f}% | {memory_bytes:6}")
 
def demonstrate_scalable_bloom_filter():
    """Demonstrate scalable Bloom filter growing automatically"""
    print("📈 SCALABLE BLOOM FILTER DEMONSTRATION")
    print("=" * 50)
 
    # Create scalable filter with small initial capacity
    sbf = ScalableBloomFilter(initial_capacity=10, false_positive_rate=0.01)
 
    # Add many items to trigger scaling
    print("➕ Adding items to trigger automatic scaling:")
 
    items_to_add = [f"item_{i:04d}" for i in range(50)]  # 50 items, capacity starts at 10
 
    for i, item in enumerate(items_to_add):
        if i % 10 == 0:  # Show progress every 10 items
            print(f"\n📊 Adding item #{i+1}: {item}")
 
        sbf.add(item)
 
        # Show status after certain milestones
        if i in [9, 19, 29, 39, 49]:  # After 10, 20, 30, 40, 50 items
            print(f"\n📈 Status after {i+1} items:")
            sbf.show_detailed_status()
            print()
 
    # Test membership
    print("🔍 Testing membership:")
    test_items = ["item_0005", "item_0025", "item_0045", "item_9999"]
 
    for item in test_items:
        print(f"\nChecking '{item}':")
        result = sbf.might_contain(item)
        status = "MIGHT BE PRESENT" if result else "DEFINITELY NOT PRESENT"
        print(f"Result: {status}")
 
if __name__ == "__main__":
    demonstrate_scalable_bloom_filter()

def analyze_bloom_filter_efficiency():
    """
    Comprehensive analysis of Bloom filter memory efficiency
    """
    print("💾 BLOOM FILTER MEMORY EFFICIENCY ANALYSIS")
    print("=" * 55)
 
    # Test different scenarios
    scenarios = [
        {'items': 1000, 'fp_rate': 0.01, 'name': 'Small website cache'},
        {'items': 100000, 'fp_rate': 0.01, 'name': 'Medium user database'},
        {'items': 10000000, 'fp_rate': 0.001, 'name': 'Large search index'},
        {'items': 1000000000, 'fp_rate': 0.0001, 'name': 'Google-scale system'}
    ]
 
    for scenario in scenarios:
        print(f"\n📊 Scenario: {scenario['name']}")
        print(f"   Items: {scenario['items']:,}")
        print(f"   Target FP rate: {scenario['fp_rate']:.4%}")
        print("-" * 50)
 
        # Create Bloom filter
        bloom = BloomFilter(expected_items=scenario['items'],
                          false_positive_rate=scenario['fp_rate'])
 
        # Calculate memory usage
        bloom_memory_bits = bloom.bit_array_size
        bloom_memory_bytes = bloom_memory_bits // 8
        bloom_memory_kb = bloom_memory_bytes / 1024
        bloom_memory_mb = bloom_memory_kb / 1024
 
        # Estimate memory for storing actual items
        avg_item_size = 20  # bytes (typical string)
        actual_memory_bytes = scenario['items'] * avg_item_size
        actual_memory_kb = actual_memory_bytes / 1024
        actual_memory_mb = actual_memory_kb / 1024
 
        # Calculate savings
        memory_savings = (1 - bloom_memory_bytes / actual_memory_bytes) * 100
 
        print(f"   Bloom filter memory:")
        if bloom_memory_mb >= 1:
            print(f"     {bloom_memory_mb:.1f} MB ({bloom_memory_bytes:,} bytes)")
        elif bloom_memory_kb >= 1:
            print(f"     {bloom_memory_kb:.1f} KB ({bloom_memory_bytes:,} bytes)")
        else:
            print(f"     {bloom_memory_bytes:,} bytes")
 
        print(f"   Storing actual items:")
        if actual_memory_mb >= 1:
            print(f"     {actual_memory_mb:.1f} MB ({actual_memory_bytes:,} bytes)")
        elif actual_memory_kb >= 1:
            print(f"     {actual_memory_kb:.1f} KB ({actual_memory_bytes:,} bytes)")
        else:
            print(f"     {actual_memory_bytes:,} bytes")
 
        print(f"   💰 Memory savings: {memory_savings:.1f}%")
        print(f"   🔢 Hash functions: {bloom.num_hash_functions}")
 
        # Bits per item
        bits_per_item = bloom_memory_bits / scenario['items']
        print(f"   📊 Bits per item: {bits_per_item:.1f}")
 
if __name__ == "__main__":
    analyze_bloom_filter_efficiency()

def analyze_false_positive_rates():
    """
    Analyze how false positive rates change with different parameters
    """
    print("🎲 FALSE POSITIVE RATE ANALYSIS")
    print("=" * 40)
 
    # Test different false positive rates
    fp_rates = [0.1, 0.01, 0.001, 0.0001]  # 10%, 1%, 0.1%, 0.01%
    num_items = 10000
 
    print(f"📊 Analysis for {num_items:,} items:")
    print()
    print("Target FP | Actual FP | Memory (KB) | Hash Funcs | Bits/Item")
    print("-" * 65)
 
    for fp_rate in fp_rates:
        # Create Bloom filter
        bloom = BloomFilter(expected_items=num_items, false_positive_rate=fp_rate)
 
        # Add items
        for i in range(num_items):
            bloom.add(f"item_{i}")
 
        # Calculate actual false positive rate
        actual_fp = bloom.get_current_false_positive_rate()
 
        # Memory usage
        memory_kb = (bloom.bit_array_size // 8) / 1024
        bits_per_item = bloom.bit_array_size / num_items
 
        print(f"  {fp_rate:6.1%}   |  {actual_fp:6.1%}   | "
              f"{memory_kb:8.1f}   |    {bloom.num_hash_functions:6}    | "
              f"{bits_per_item:6.1f}")
 
    print()
 
    # Test how fill ratio affects false positive rate
    print("📈 How fill ratio affects false positive rate:")
    print("(Using 1% target FP rate)")
    print()
 
    bloom = BloomFilter(expected_items=10000, false_positive_rate=0.01)
 
    fill_ratios = []
    actual_fps = []
 
    print("Items Added | Fill Ratio | Actual FP Rate")
    print("-" * 40)
 
    for items_added in range(1000, 20001, 2000):  # 1K to 20K in steps of 2K
        # Add items
        while bloom.items_added < items_added:
            bloom.add(f"item_{bloom.items_added}")
 
        # Calculate metrics
        bits_set = sum(bloom.bit_array)
        fill_ratio = bits_set / bloom.bit_array_size
        actual_fp = bloom.get_current_false_positive_rate()
 
        fill_ratios.append(fill_ratio)
        actual_fps.append(actual_fp)
 
        print(f"  {items_added:6,}    |   {fill_ratio:5.1%}    |    {actual_fp:6.1%}")
 
    print()
    print("💡 Key Insights:")
    print("   • Lower target FP rate → More memory needed")
    print("   • More hash functions → More computation but better accuracy")
    print("   • Overfilling → Higher actual FP rate than target")
 
if __name__ == "__main__":
    analyze_false_positive_rates()

def bloom_filter_performance_summary():
    """
    Final performance summary of Bloom filter capabilities
    """
    print("🏆 BLOOM FILTER PERFORMANCE SUMMARY")
    print("=" * 45)
 
    performance_metrics = {
        'Time Complexity': {
            'Insert': 'O(k) - k hash functions',
            'Query': 'O(k) - k hash functions',
            'Delete': 'Not supported (regular BF)',
            'Space': 'O(m) - m bits in array'
        },
        'Memory Efficiency': {
            'Savings vs Set': '90-99% less memory',
            'Bits per item': '8-15 bits typical',
            'Scalability': 'Linear with items',
            'Cache friendly': 'Yes - compact arrays'
        },
        'Accuracy Guarantees': {
            'False negatives': 'Never (100% accurate)',
            'False positives': 'Configurable (0.1%-10%)',
            'Deterministic': 'Yes - same input = same result',
            'Probabilistic': 'Yes - statistical guarantees'
        },
        'Real-World Performance': {
            'Google Chrome': 'Billions of URLs checked',
            'Bitcoin wallets': '99.9% bandwidth savings',
            'Database systems': '10-100x faster queries',
            'CDN caching': 'Millisecond response times'
        }
    }
 
    for category, metrics in performance_metrics.items():
        print(f"\n📊 {category}:")
        for metric, value in metrics.items():
            print(f"   {metric:15}: {value}")
 
    print(f"\n🎯 Bottom Line:")
    print(f"   Bloom filters trade a small amount of accuracy")
    print(f"   for MASSIVE improvements in speed and memory efficiency!")
 
if __name__ == "__main__":
    bloom_filter_performance_summary()