@@ -0,0 +1,2630 @@
+// LFU cache algorithm, O(1) time complexity on search, O(n) time complexity on insert.%0A// Cache can be also implemented as max heap with support for rebalancing when value is modified,%0A// this should make search O(logN) and insert O(logN).%0A//%0A// This is the most naive implementation, for all-O(1) time complexity operations for LFU see%0A// paper: http://dhruvbird.com/lfu.pdf%0A%0Apublic class LFUCache %7B%0A    static class Container %7B%0A        int key;%0A        int value;%0A        int freq;%0A        int time;%0A%0A        Container(int key, int value) %7B%0A            this.key = key;%0A            this.value = value;%0A            this.freq = 0;%0A            this.time = 0;%0A        %7D%0A    %7D%0A%0A    private HashMap%3CInteger, Container%3E lookup;%0A    private Container%5B%5D arr;%0A    private int time;%0A%0A    public LFUCache(int capacity) %7B%0A        assert(capacity %3E= 0);%0A        lookup = new HashMap%3CInteger, Container%3E();%0A        arr = new Container%5Bcapacity%5D;%0A        time = 0;%0A    %7D%0A%0A    public int get(int key) %7B%0A        Container cnt = lookup.get(key);%0A        if (cnt != null) %7B%0A            cnt.freq++;%0A            cnt.time = this.time++;%0A            return cnt.value;%0A        %7D else %7B%0A            return -1;%0A        %7D%0A    %7D%0A%0A    public void set(int key, int value) %7B%0A        if (lookup.containsKey(key)) %7B%0A            Container cnt = lookup.get(key);%0A            cnt.value = value;%0A            cnt.freq++;%0A            cnt.time = this.time++;%0A        %7D else if (arr.length %3E 0) %7B%0A            Container cnt = new Container(key, value);%0A            cnt.time = this.time++;%0A            int least = 0;%0A            Container leastCnt = null;%0A            for (int i = 0; i %3C arr.length; i++) %7B%0A                if (arr%5Bi%5D == null) %7B%0A                    leastCnt = null;%0A                    least = i;%0A                    break;%0A                %7D%0A%0A                if (leastCnt == null) %7B%0A                    leastCnt = arr%5Bi%5D;%0A                    least = i;%0A                %7D else if (leastCnt.freq %3E arr%5Bi%5D.freq) %7B%0A                    leastCnt = arr%5Bi%5D;%0A                    least = i;%0A                %7D else if (leastCnt.freq == arr%5Bi%5D.freq && leastCnt.time %3E arr%5Bi%5D.time) %7B%0A                    leastCnt = arr%5Bi%5D;%0A                    least = i;%0A                %7D%0A            %7D%0A%0A            if (leastCnt != null) %7B%0A                lookup.remove(leastCnt.key);%0A                arr%5Bleast%5D = null;%0A            %7D%0A            lookup.put(key, cnt);%0A            arr%5Bleast%5D = cnt;%0A        %7D%0A    %7D%0A%7D%0A%0A/**%0A * Your LFUCache object will be instantiated and called as such:%0A * LFUCache obj = new LFUCache(capacity);%0A * int param_1 = obj.get(key);%0A * obj.set(key,value);%0A */%0A

add naive lfu cache algorithm