Design and Data Structure Patterns

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // key -> node
        
        // Dummy head and tail for easier insertion/deletion
        this.head = { key: 0, value: 0, prev: null, next: null };
        this.tail = { key: 0, value: 0, prev: null, next: null };
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    
    get(key) {
        if (!this.cache.has(key)) return -1;
        
        const node = this.cache.get(key);
        
        // Move to front (most recently used)
        this.removeNode(node);
        this.addToHead(node);
        
        return node.value;
    }
    
    put(key, value) {
        if (this.cache.has(key)) {
            // Update existing
            const node = this.cache.get(key);
            node.value = value;
            this.removeNode(node);
            this.addToHead(node);
        } else {
            // Add new
            const newNode = { key, value, prev: null, next: null };
            this.cache.set(key, newNode);
            this.addToHead(newNode);
            
            // Check capacity
            if (this.cache.size > this.capacity) {
                // Remove LRU (tail.prev)
                const lru = this.tail.prev;
                this.removeNode(lru);
                this.cache.delete(lru.key);
            }
        }
    }
    
    addToHead(node) {
        // Insert between head and head.next
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next.prev = node;
        this.head.next = node;
    }
    
    removeNode(node) {
        // Remove from current position
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

// Usage:
const lru = new LRUCache(2);
lru.put(1, 1);        // cache: {1=1}
lru.put(2, 2);        // cache: {1=1, 2=2}
lru.get(1);           // returns 1, cache: {2=2, 1=1}
lru.put(3, 3);        // evicts key 2, cache: {1=1, 3=3}
lru.get(2);           // returns -1 (not found)
lru.put(4, 4);        // evicts key 1, cache: {3=3, 4=4}
lru.get(1);           // returns -1
lru.get(3);           // returns 3
lru.get(4);           // returns 4

class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyToVal = new Map();  // key -> {value, freq}
        this.freqToKeys = new Map(); // freq -> Set of keys
    }
    
    get(key) {
        if (!this.keyToVal.has(key)) return -1;
        
        const { value, freq } = this.keyToVal.get(key);
        
        // Increment frequency
        this.increaseFreq(key, value, freq);
        
        return value;
    }
    
    put(key, value) {
        if (this.capacity === 0) return;
        
        if (this.keyToVal.has(key)) {
            // Update existing
            const { freq } = this.keyToVal.get(key);
            this.increaseFreq(key, value, freq);
        } else {
            // Add new
            if (this.keyToVal.size >= this.capacity) {
                // Evict least frequently used
                const keysWithMinFreq = this.freqToKeys.get(this.minFreq);
                const keyToEvict = keysWithMinFreq.values().next().value;
                keysWithMinFreq.delete(keyToEvict);
                this.keyToVal.delete(keyToEvict);
            }
            
            // Insert new key with freq = 1
            this.keyToVal.set(key, { value, freq: 1 });
            
            if (!this.freqToKeys.has(1)) {
                this.freqToKeys.set(1, new Set());
            }
            this.freqToKeys.get(1).add(key);
            
            this.minFreq = 1;
        }
    }
    
    increaseFreq(key, value, freq) {
        // Remove from current frequency
        this.freqToKeys.get(freq).delete(key);
        
        // If this was the only key with minFreq, increment minFreq
        if (freq === this.minFreq && this.freqToKeys.get(freq).size === 0) {
            this.minFreq++;
        }
        
        // Add to next frequency
        const newFreq = freq + 1;
        if (!this.freqToKeys.has(newFreq)) {
            this.freqToKeys.set(newFreq, new Set());
        }
        this.freqToKeys.get(newFreq).add(key);
        
        // Update value and frequency
        this.keyToVal.set(key, { value, freq: newFreq });
    }
}

// Usage:
const lfu = new LFUCache(2);
lfu.put(1, 1);   // cache={1=1}, freq: 1->[1]
lfu.put(2, 2);   // cache={1=1, 2=2}, freq: 1->[1,2]
lfu.get(1);      // returns 1, freq: 1->[2], 2->[1]
lfu.put(3, 3);   // evicts 2, cache={1=1, 3=3}
lfu.get(2);      // returns -1
lfu.get(3);      // returns 3
lfu.put(4, 4);   // evicts 3, cache={1=1, 4=4}
lfu.get(1);      // returns 1
lfu.get(3);      // returns -1
lfu.get(4);      // returns 4

class MyQueue {
    constructor() {
        this.input = [];   // Newest on top
        this.output = [];  // Oldest on top
    }
    
    push(x) {
        // Always push to input stack
        this.input.push(x);
    }
    
    pop() {
        this.peek(); // Ensure output stack has elements
        return this.output.pop();
    }
    
    peek() {
        // If output is empty, transfer from input
        if (this.output.length === 0) {
            while (this.input.length > 0) {
                this.output.push(this.input.pop());
            }
        }
        return this.output[this.output.length - 1];
    }
    
    empty() {
        return this.input.length === 0 && this.output.length === 0;
    }
}

// Example walkthrough:
const q = new MyQueue();

q.push(1);  // input: [1], output: []
q.push(2);  // input: [1,2], output: []
q.push(3);  // input: [1,2,3], output: []

q.peek();   // Transfer: input: [], output: [3,2,1]
            // Returns 1

q.pop();    // output: [3,2], returns 1

q.push(4);  // input: [4], output: [3,2]

q.pop();    // output: [3], returns 2
q.pop();    // output: [], returns 3
q.pop();    // Transfer from input, returns 4

// Amortized O(1):
// - Element 1: pushed to input (1 op), transferred to output (1 op), popped (1 op) = 3 ops
// - Element 2: pushed to input (1 op), transferred to output (1 op), popped (1 op) = 3 ops
// - Each element: at most 1 push to input, 1 transfer, 1 pop from output = 3 operations total
// - Average per operation: O(1)

class Twitter {
    constructor() {
        this.timestamp = 0;
        this.tweets = new Map();     // userId -> [{id, time}, ...]
        this.following = new Map();  // userId -> Set of followeeIds
    }
    
    postTweet(userId, tweetId) {
        if (!this.tweets.has(userId)) {
            this.tweets.set(userId, []);
        }
        this.tweets.get(userId).push({ id: tweetId, time: this.timestamp++ });
    }
    
    getNewsFeed(userId) {
        // Get all relevant users (self + followees)
        const users = new Set([userId]);
        if (this.following.has(userId)) {
            for (const followeeId of this.following.get(userId)) {
                users.add(followeeId);
            }
        }
        
        // Merge tweets from all users using max heap
        const heap = [];
        
        for (const user of users) {
            if (this.tweets.has(user)) {
                const userTweets = this.tweets.get(user);
                if (userTweets.length > 0) {
                    // Add most recent tweet from each user
                    const idx = userTweets.length - 1;
                    heap.push({ 
                        tweetId: userTweets[idx].id,
                        time: userTweets[idx].time,
                        user,
                        index: idx
                    });
                }
            }
        }
        
        // Build max heap by time
        heap.sort((a, b) => b.time - a.time);
        
        const feed = [];
        
        // Get top 10 most recent tweets
        while (feed.length < 10 && heap.length > 0) {
            // Extract max (most recent)
            const { tweetId, user, index } = heap.shift();
            feed.push(tweetId);
            
            // Add next tweet from same user if exists
            if (index > 0) {
                const userTweets = this.tweets.get(user);
                const nextIdx = index - 1;
                heap.push({
                    tweetId: userTweets[nextIdx].id,
                    time: userTweets[nextIdx].time,
                    user,
                    index: nextIdx
                });
                heap.sort((a, b) => b.time - a.time);
            }
        }
        
        return feed;
    }
    
    follow(followerId, followeeId) {
        if (followerId === followeeId) return; // Can't follow self
        
        if (!this.following.has(followerId)) {
            this.following.set(followerId, new Set());
        }
        this.following.get(followerId).add(followeeId);
    }
    
    unfollow(followerId, followeeId) {
        if (this.following.has(followerId)) {
            this.following.get(followerId).delete(followeeId);
        }
    }
}

// Usage:
const twitter = new Twitter();
twitter.postTweet(1, 5);
twitter.getNewsFeed(1);      // [5]
twitter.follow(1, 2);
twitter.postTweet(2, 6);
twitter.getNewsFeed(1);      // [6, 5]
twitter.unfollow(1, 2);
twitter.getNewsFeed(1);      // [5]