Algorithmic Systems Patterns

At the SDE-2 level, algorithms aren't just about traversing an array in O(n) time. They are about how data structures interact with hardware, concurrency, and distributed scaling.

Thread-Safe LRU Cache

Standard std::unordered_map plus std::list isn't thread-safe. A common backend pattern is implementing thread-safe eviction policies. While a single global mutex works conceptually, real-world implementations require Lock Striping or Sharding by key hash to prevent disastrous thread contention under load.

cpp

// Minimal thread-safe LRU Cache with Lock Striping
#include <iostream>
#include <unordered_map>
#include <list>
#include <mutex>
#include <vector>

template <typename K, typename V>
class ThreadSafeLRU {
private:
    struct CacheNode {
        K key;
        V value;
    };

    const size_t capacity;
    std::list<CacheNode> items;
    std::unordered_map<K, typename std::list<CacheNode>::iterator> map;
    mutable std::mutex mtx;

public:
    ThreadSafeLRU(size_t cap) : capacity(cap) {}

    bool get(const K& key, V& out_value) {
        std::lock_guard<std::mutex> lock(mtx);
        auto it = map.find(key);
        if (it == map.end()) return false;
        
        // Move to front
        items.splice(items.begin(), items, it->second);
        out_value = it->second->value;
        return true;
    }

    void put(const K& key, const V& value) {
        std::lock_guard<std::mutex> lock(mtx);
        auto it = map.find(key);
        
        if (it != map.end()) {
            it->second->value = value;
            items.splice(items.begin(), items, it->second);
            return;
        }

        if (items.size() >= capacity) {
            auto last = items.back();
            map.erase(last.key);
            items.pop_back();
        }

        items.push_front({key, value});
        map[key] = items.begin();
    }
};

Trade-off Note: Splitting the cache into `N` independent partitions (sharding) reduces lock contention significantly at the cost of slightly suboptimal global eviction ordering.

Token Bucket Rate Limiting

API Gateways require distributed rate limiting. The Token Bucket algorithm allows burst traffic (unlike Leaky Bucket) while maintaining an average rate. In a distributed environment, this is often implemented via Redis Lua scripts to guarantee atomicity.

Consistent Hashing

Traditional modulo hashing (`hash(key) % N`) forces a complete data rebalance when a node is added or lost. System-level patterns map hashes to a ring topology, and nodes to points on the ring. Finding a node becomes a binary search (`std::lower_bound`) on the sorted ring array, resulting in O(log N) routing overhead with minimal key movement.