Least Frequently Used Cache - Amazon Top Interview Questions

                        Solution in C++ :

void set(int key, int value) {
    // Scenario 1:
    if (!keyMap.count(key)) {

        // Case 1:
        if (keyMap.size() < cap) {
            freqMap[1].emplace_back(key, value);
            keyMap[key] = {1, --freqMap[1].end()};
            lowestFreq = 1;
        } 

        // Case 2:
        if (keyMap.size() == cap) {
            if (lowestFreq == 0) return;
            auto [k, v] = freqMap[lowestFreq].front();
            freqMap[lowestFreq].erase(freqMap[lowestFreq].begin());
            keyMap.erase(k);
            set(key, value);
        }
    } 

   // Scenario 2:
   if(keyMap.count(key) {
        auto [freq, it] = keyMap[key];
        if (freqMap[freq].size() == 1 and freq == lowestFreq) lowestFreq++;
        freqMap[freq].erase(it);
        freqMap[freq+1].emplace_back(key, value);
        keyMap[key] = {freq+1, --freqMap[freq+1].end()};
    }
}
                    

                        Solution in Java :

import java.util.*;

class LFUCache {
    private Map<Integer, Integer> values;
    private Map<Integer, Integer> freq;
    private Map<Integer, LinkedHashSet<Integer>> lists;
    private int capacity;
    private int minIndex = -1; // to keep track of lists (index)

    public LFUCache(int capacity) {
        this.capacity = capacity;
        values = new HashMap<>();
        freq = new HashMap<>();
        lists = new HashMap<>();
        lists.put(1, new LinkedHashSet<>()); // create 1 count bucket
    }

    public int get(int key) {
        // key not found
        if (!values.containsKey(key))
            return -1;
        // update frequency counts
        int count = freq.get(key);
        freq.put(key, count + 1);
        // remove from <count> bucket lists
        lists.get(count).remove(key);
        // update min to pick next bucket from list
        if (count == minIndex && lists.get(count).size() == 0)
            minIndex++;

        // add it new count bucket lists
        lists.computeIfAbsent(count + 1, f -> new LinkedHashSet());
        lists.get(count + 1).add(key);
        return values.get(key);
    }

    public void set(int key, int val) {
        // not enough capacity
        if (capacity <= 0)
            return;

        // Case 1: if key exists
        if (values.containsKey(key)) {
            values.put(key, val);
            get(key); // update count
            return;
        }

        // case 2: if capacity is Full
        // evict policy
        if (values.size() >= capacity) {
            int evit = lists.get(minIndex).iterator().next();
            lists.get(minIndex).remove(evit);
            values.remove(evit);
        }

        values.put(key, val);
        freq.put(key, 1);
        minIndex = 1; // reset min index
        lists.get(minIndex).add(key);
    }
}
                    

                        Solution in Python : 
                            
from collections import defaultdict, OrderedDict


class Node:
    def __init__(self, key: int, value: int, count: int = 1):
        self.key = key
        self.value = value
        self.count = count


class LFUCache:
    def __init__(self, capacity: int):
        self._size = 0
        self._capacity = capacity
        self._nodes = {}
        self._counts = defaultdict(OrderedDict)
        self._min_count = 0

    def _touch(self, node: Node):
        self._counts[node.count].popitem(node.key)
        if not self._counts[self._min_count]:
            self._min_count += 1

        node.count += 1
        self._counts[node.count][node.key] = node

    def get(self, key: int) -> int:
        if key not in self._nodes:
            return -1

        node = self._nodes[key]
        self._touch(node)
        return node.value

    def set(self, key: int, value: int):
        if not self._capacity:
            return

        if key in self._nodes:
            node = self._nodes[key]
            self._touch(node)
            node.value = value
        else:
            if self._size == self._capacity:
                evict_key, _ = self._counts[self._min_count].popitem(last=False)
                self._nodes.pop(evict_key)
                self._size -= 1

            node = Node(key, value)
            self._nodes[key] = node
            self._counts[1][key] = node
            self._min_count = 1
            self._size += 1