system_design_patterns.cpp

/*
System Design Patterns for Interviews
Mathematical Foundation: Scalability = Load × Response Time
CAP Theorem: Consistency, Availability, Partition tolerance (pick 2)
Throughput = Requests/Time, Latency = Response Time
Applications: Design Twitter, Chat systems, URL shortener
*/

#include <bits/stdc++.h>
using namespace std;

// LRU Cache (Already in linkedlist.cpp, but key pattern)
// LeetCode: 146. LRU Cache
// https://leetcode.com/problems/lru-cache/
class LRUCache {
    struct Node {
        int key, val;
        Node* prev, *next;
        Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };
    
    unordered_map<int, Node*> mp;
    Node* head, *tail;
    int cap;
    
public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(); tail = new Node();
        head->next = tail; tail->prev = head;
    }
    
    int get(int key) {
        if (!mp.count(key)) return -1;
        Node* node = mp[key];
        moveToHead(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if (mp.count(key)) {
            Node* node = mp[key];
            node->val = value;
            moveToHead(node);
        } else {
            if (mp.size() >= cap) {
                Node* last = tail->prev;
                removeNode(last);
                mp.erase(last->key);
                delete last;
            }
            Node* node = new Node(key, value);
            addToHead(node);
            mp[key] = node;
        }
    }
    
private:
    void addToHead(Node* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }
};

// LFU Cache (Least Frequently Used)
// LeetCode: 460. LFU Cache
// https://leetcode.com/problems/lfu-cache/
class LFUCache {
    struct Node {
        int key, val, freq;
        Node* prev, *next;
        Node(int k, int v, int f) : key(k), val(v), freq(f), prev(nullptr), next(nullptr) {}
    };
    
    unordered_map<int, Node*> keyToNode;
    unordered_map<int, Node*> freqToHead; // freq -> dummy head
    int cap, minFreq;
    
public:
    LFUCache(int capacity) : cap(capacity), minFreq(0) {}
    
    int get(int key) {
        if (!keyToNode.count(key)) return -1;
        Node* node = keyToNode[key];
        updateFreq(node);
        return node->val;
    }
    
    void put(int key, int value) {
        if (cap == 0) return;
        
        if (keyToNode.count(key)) {
            Node* node = keyToNode[key];
            node->val = value;
            updateFreq(node);
        } else {
            if (keyToNode.size() >= cap) {
                Node* tail = freqToHead[minFreq]->prev;
                removeNode(tail);
                keyToNode.erase(tail->key);
                delete tail;
            }
            
            Node* node = new Node(key, value, 1);
            keyToNode[key] = node;
            addToFreqList(node);
            minFreq = 1;
        }
    }
    
private:
    void updateFreq(Node* node) {
        removeNode(node);
        node->freq++;
        addToFreqList(node);
        
        if (freqToHead[node->freq - 1]->next == freqToHead[node->freq - 1] && 
            minFreq == node->freq - 1) {
            minFreq++;
        }
    }
    
    void addToFreqList(Node* node) {
        if (!freqToHead.count(node->freq)) {
            freqToHead[node->freq] = new Node(0, 0, 0);
            freqToHead[node->freq]->next = freqToHead[node->freq]->prev = freqToHead[node->freq];
        }
        
        Node* head = freqToHead[node->freq];
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};

// Consistent Hashing (Distributed Systems)
class ConsistentHash {
    map<uint32_t, string> ring;
    int virtualNodes;
    
    uint32_t hash(const string& str) {
        // Simple hash function (use better hash in production)
        uint32_t hash = 5381;
        for (char c : str) hash = ((hash << 5) + hash) + c;
        return hash;
    }
    
public:
    ConsistentHash(int vnodes = 150) : virtualNodes(vnodes) {}
    
    void addNode(const string& node) {
        for (int i = 0; i < virtualNodes; i++) {
            string vnode = node + ":" + to_string(i);
            ring[hash(vnode)] = node;
        }
    }
    
    void removeNode(const string& node) {
        for (int i = 0; i < virtualNodes; i++) {
            string vnode = node + ":" + to_string(i);
            ring.erase(hash(vnode));
        }
    }
    
    string getNode(const string& key) {
        if (ring.empty()) return "";
        
        uint32_t h = hash(key);
        auto it = ring.lower_bound(h);
        if (it == ring.end()) it = ring.begin();
        return it->second;
    }
};

// Rate Limiter (Token Bucket)
class TokenBucket {
    int capacity, tokens;
    int refillRate; // tokens per second
    long long lastRefill;
    
public:
    TokenBucket(int cap, int rate) : capacity(cap), tokens(cap), refillRate(rate) {
        lastRefill = chrono::duration_cast<chrono::milliseconds>(
            chrono::system_clock::now().time_since_epoch()).count();
    }
    
    bool allowRequest() {
        refill();
        if (tokens > 0) {
            tokens--;
            return true;
        }
        return false;
    }
    
private:
    void refill() {
        long long now = chrono::duration_cast<chrono::milliseconds>(
            chrono::system_clock::now().time_since_epoch()).count();
        
        long long elapsed = now - lastRefill;
        int tokensToAdd = (elapsed / 1000) * refillRate;
        
        tokens = min(capacity, tokens + tokensToAdd);
        lastRefill = now;
    }
};

// Sliding Window Rate Limiter
class SlidingWindowRateLimiter {
    queue<long long> requests;
    int maxRequests;
    long long windowSizeMs;
    
public:
    SlidingWindowRateLimiter(int max, long long windowMs) 
        : maxRequests(max), windowSizeMs(windowMs) {}
    
    bool allowRequest() {
        long long now = chrono::duration_cast<chrono::milliseconds>(
            chrono::system_clock::now().time_since_epoch()).count();
        
        // Remove old requests
        while (!requests.empty() && now - requests.front() > windowSizeMs) {
            requests.pop();
        }
        
        if (requests.size() < maxRequests) {
            requests.push(now);
            return true;
        }
        return false;
    }
};

// URL Shortener (Design TinyURL)
// LeetCode: 535. Encode and Decode TinyURL
// https://leetcode.com/problems/encode-and-decode-tinyurl/
class URLShortener {
    unordered_map<string, string> longToShort;
    unordered_map<string, string> shortToLong;
    string chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    string baseUrl = "http://tinyurl.com/";
    
    string generateShortCode() {
        string code;
        for (int i = 0; i < 6; i++) {
            code += chars[rand() % chars.size()];
        }
        return code;
    }
    
public:
    string encode(string longUrl) {
        if (longToShort.count(longUrl)) {
            return baseUrl + longToShort[longUrl];
        }
        
        string shortCode;
        do {
            shortCode = generateShortCode();
        } while (shortToLong.count(shortCode));
        
        longToShort[longUrl] = shortCode;
        shortToLong[shortCode] = longUrl;
        
        return baseUrl + shortCode;
    }
    
    string decode(string shortUrl) {
        string shortCode = shortUrl.substr(baseUrl.length());
        return shortToLong.count(shortCode) ? shortToLong[shortCode] : "";
    }
};

// Design Twitter
// LeetCode: 355. Design Twitter
// https://leetcode.com/problems/design-twitter/
class Twitter {
    unordered_map<int, unordered_set<int>> followers;
    vector<pair<int, int>> tweets; // {userId, tweetId}
    
public:
    void postTweet(int userId, int tweetId) {
        tweets.push_back({userId, tweetId});
    }
    
    vector<int> getNewsFeed(int userId) {
        vector<int> feed;
        for (int i = tweets.size() - 1; i >= 0 && feed.size() < 10; i--) {
            int author = tweets[i].first;
            if (author == userId || followers[userId].count(author)) {
                feed.push_back(tweets[i].second);
            }
        }
        return feed;
    }
    
    void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            followers[followerId].insert(followeeId);
        }
    }
    
    void unfollow(int followerId, int followeeId) {
        followers[followerId].erase(followeeId);
    }
};

// Design Chat System (Message Queue)
class ChatSystem {
    struct Message {
        int fromUser, toUser;
        string content;
        long long timestamp;
    };
    
    unordered_map<int, queue<Message>> userMessages;
    unordered_map<int, vector<int>> userConnections; // friends
    
public:
    void sendMessage(int from, int to, string content) {
        Message msg = {from, to, content, 
            chrono::duration_cast<chrono::milliseconds>(
                chrono::system_clock::now().time_since_epoch()).count()};
        
        userMessages[to].push(msg);
    }
    
    vector<Message> getMessages(int userId, int limit = 10) {
        vector<Message> messages;
        auto& queue = userMessages[userId];
        
        int count = 0;
        while (!queue.empty() && count < limit) {
            messages.push_back(queue.front());
            queue.pop();
            count++;
        }
        
        return messages;
    }
    
    void addFriend(int user1, int user2) {
        userConnections[user1].push_back(user2);
        userConnections[user2].push_back(user1);
    }
};

// Design Hit Counter
// LeetCode: 362. Design Hit Counter
// https://leetcode.com/problems/design-hit-counter/
class HitCounter {
    queue<int> hits;
    
public:
    void hit(int timestamp) {
        hits.push(timestamp);
    }
    
    int getHits(int timestamp) {
        while (!hits.empty() && timestamp - hits.front() >= 300) {
            hits.pop();
        }
        return hits.size();
    }
};

// Load Balancer (Round Robin)
class LoadBalancer {
    vector<string> servers;
    int currentIndex;
    
public:
    LoadBalancer() : currentIndex(0) {}
    
    void addServer(const string& server) {
        servers.push_back(server);
    }
    
    void removeServer(const string& server) {
        auto it = find(servers.begin(), servers.end(), server);
        if (it != servers.end()) {
            servers.erase(it);
            if (currentIndex >= servers.size() && !servers.empty()) {
                currentIndex = 0;
            }
        }
    }
    
    string getServer() {
        if (servers.empty()) return "";
        
        string server = servers[currentIndex];
        currentIndex = (currentIndex + 1) % servers.size();
        return server;
    }
};

// Bloom Filter (Probabilistic Data Structure)
class BloomFilter {
    vector<bool> bits;
    int size, hashCount;
    
    int hash(const string& str, int seed) {
        int hash = seed;
        for (char c : str) {
            hash = hash * 31 + c;
        }
        return abs(hash) % size;
    }
    
public:
    BloomFilter(int n, double falsePositiveRate = 0.01) {
        size = -n * log(falsePositiveRate) / (log(2) * log(2));
        hashCount = size * log(2) / n;
        bits.resize(size, false);
    }
    
    void add(const string& item) {
        for (int i = 0; i < hashCount; i++) {
            bits[hash(item, i)] = true;
        }
    }
    
    bool contains(const string& item) {
        for (int i = 0; i < hashCount; i++) {
            if (!bits[hash(item, i)]) return false;
        }
        return true; // Maybe contains (no false negatives)
    }
};