Design LFU cache with distributed extension

Hash Maps + Frequency Buckets To satisfy the LFU policy, every key must be associated with two things: its current value and its current access count. The non-obvious part is tie-breaking: when several keys share the lowest frequency, we must evict the one accessed least recently. We can handle both rules in constant time by maintaining one insertion-ordered container per frequency. The cache keeps four structures: valueByKey maps a key to its value. freqByKey maps a key to…