Modern Topics

// Count-Min Sketch Implementation
class CountMinSketch {
    private table: number[][];
    private hashFunctions: ((x: string) => number)[];
    private width: number;
    private depth: number;
    
    constructor(epsilon: number, delta: number) {
        this.width = Math.ceil(Math.E / epsilon);
        this.depth = Math.ceil(Math.log(1 / delta));
        this.table = Array(this.depth).fill(null).map(() => Array(this.width).fill(0));
        this.hashFunctions = this.generateHashFunctions();
    }
    
    private generateHashFunctions(): ((x: string) => number)[] {
        const functions: ((x: string) => number)[] = [];
        for (let i = 0; i < this.depth; i++) {
            const a = Math.floor(Math.random() * 1000) + 1;
            const b = Math.floor(Math.random() * 1000);
            functions.push((x: string) => {
                let hash = 0;
                for (let j = 0; j < x.length; j++) {
                    hash = (hash * a + x.charCodeAt(j) + b) % this.width;
                }
                return Math.abs(hash);
            });
        }
        return functions;
    }
    
    add(element: string, count: number = 1): void {
        for (let i = 0; i < this.depth; i++) {
            const j = this.hashFunctions[i](element);
            this.table[i][j] += count;
        }
    }
    
    query(element: string): number {
        let minCount = Infinity;
        for (let i = 0; i < this.depth; i++) {
            const j = this.hashFunctions[i](element);
            minCount = Math.min(minCount, this.table[i][j]);
        }
        return minCount;
    }
}

// Reservoir Sampling Implementation
class ReservoirSampling {
    private reservoir: any[];
    private sampleSize: number;
    private itemsSeen: number;
    
    constructor(sampleSize: number) {
        this.reservoir = [];
        this.sampleSize = sampleSize;
        this.itemsSeen = 0;
    }
    
    addItem(item: any): void {
        this.itemsSeen++;
        if (this.reservoir.length < this.sampleSize) {
            this.reservoir.push(item);
        } else {
            const randomIndex = Math.floor(Math.random() * this.itemsSeen);
            if (randomIndex < this.sampleSize) {
                this.reservoir[randomIndex] = item;
            }
        }
    }
    
    getSample(): any[] {
        return [...this.reservoir];
    }
}
                                    

// Online Algorithms Implementation

// Ski Rental Problem
class SkiRental {
    private buyPrice: number;
    private rentPrice: number;
    private strategy: 'rent' | 'buy' | 'threshold';
    private currentCost: number;
    private daysSinceDecision: number;
    private hasWontBuy: boolean;
    
    constructor(buyPrice: number, rentPrice: number = 1, strategy: 'rent' | 'buy' | 'threshold' = 'threshold') {
        this.buyPrice = buyPrice;
        this.rentPrice = rentPrice;
        this.strategy = strategy;
        this.currentCost = 0;
        this.daysSinceDecision = 0;
        this.hasWontBuy = false;
    }
    
    // Make decision for next ski day
    skiDay(): { action: string; cost: number; totalCost: number } {
        this.daysSinceDecision++;
        let action: string;
        let dayCost: number;
        
        switch (this.strategy) {
            case 'rent':
                action = 'rent';
                dayCost = this.rentPrice;
                break;
                
            case 'buy':
                if (this.daysSinceDecision === 1) {
                    action = 'buy';
                    dayCost = this.buyPrice;
                } else {
                    action = 'use_owned_skis';
                    dayCost = 0;
                }
                break;
                
            case 'threshold':
                // Rent for (buyPrice - 1) days, then buy
                const threshold = this.buyPrice - 1;
                if (this.daysSinceDecision <= threshold && !this.hasWontBuy) {
                    action = 'rent';
                    dayCost = this.rentPrice;
                } else if (!this.hasWontBuy) {
                    action = 'buy';
                    dayCost = this.buyPrice;
                    this.hasWontBuy = true;
                } else {
                    action = 'use_owned_skis';
                    dayCost = 0;
                }
                break;
        }
        
        this.currentCost += dayCost;
        return {
            action,
            cost: dayCost,
            totalCost: this.currentCost
        };
    }
    
    // Calculate competitive ratio against optimal offline solution
    static competitiveAnalysis(skiDays: number, buyPrice: number, rentPrice: number = 1): {
        optimalCost: number;
        thresholdCost: number;
        competitiveRatio: number;
    } {
        // Optimal offline solution (knows future)
        const optimalCost = Math.min(skiDays * rentPrice, buyPrice);
        
        // Threshold strategy cost
        const threshold = buyPrice - 1;
        let thresholdCost: number;
        
        if (skiDays <= threshold) {
            thresholdCost = skiDays * rentPrice;
        } else {
            thresholdCost = threshold * rentPrice + buyPrice;
        }
        
        const competitiveRatio = thresholdCost / optimalCost;
        
        return { optimalCost, thresholdCost, competitiveRatio };
    }
}

// Online Caching Algorithm - Least Recently Used (LRU)
class OnlineLRUCache {
    private capacity: number;
    private cache: Map;
    private accessOrder: string[];
    private hits: number;
    private misses: number;
    
    constructor(capacity: number) {
        this.capacity = capacity;
        this.cache = new Map();
        this.accessOrder = [];
        this.hits = 0;
        this.misses = 0;
    }
    
    get(key: string): any | null {
        if (this.cache.has(key)) {
            this.hits++;
            // Move to end (most recently used)
            this.accessOrder = this.accessOrder.filter(k => k !== key);
            this.accessOrder.push(key);
            return this.cache.get(key);
        } else {
            this.misses++;
            return null;
        }
    }
    
    put(key: string, value: any): void {
        if (this.cache.has(key)) {
            // Update existing key
            this.cache.set(key, value);
            this.accessOrder = this.accessOrder.filter(k => k !== key);
            this.accessOrder.push(key);
        } else {
            // Add new key
            if (this.cache.size >= this.capacity) {
                // Evict least recently used
                const lru = this.accessOrder.shift()!;
                this.cache.delete(lru);
            }
            this.cache.set(key, value);
            this.accessOrder.push(key);
        }
    }
    
    getStats(): { hits: number; misses: number; hitRate: number } {
        const total = this.hits + this.misses;
        return {
            hits: this.hits,
            misses: this.misses,
            hitRate: total > 0 ? this.hits / total : 0
        };
    }
}