Java solution using PriorityQueue, with detailed explanation


  • 6
    C

    We need to implement get() and set() in average O(logn) time, or we will get TLE.

    Obviously, we need a hashmap to remember key-value pair.
    What we need to do, is to remember (frequency, recentness) for each key; and sort them to get the smallest one.
    So, we need to use Collection such as TreeSet or PriorityQueue.

    Now, the only question is, how to update?
    It is difficult to update (frequency, recentness) in the collection, as we don't know the index.
    (Maybe using binary search or hashmap can do this, I haven't tried it.)

    The trick is, just override equals() and hashCode() function, in order to use remove.

    Here is the code with detailed comment.

    public class LFUCache {
        
        class Cache { // a class to remember frequency and recentness
            int key, f, r;
            public Cache(int k, int f, int r) {key=k;this.f=f;this.r=r;}
            // override equals() and hashCode()
            public boolean equals(Object object) {return key==((Cache) object).key;}
            public int hashCode() {return key;}
        }
        
        int capacity, id;
        HashMap<Integer, Integer> hashMap, frequency;
        PriorityQueue<Cache> queue;
    
        public LFUCache(int capacity) {
            this.capacity=capacity;
            id=0;
            hashMap=new HashMap<>();
            frequency=new HashMap<>();
            // sort by frequency and recentness
            queue =new PriorityQueue<>((o1,o2) -> o1.f==o2.f?o1.r-o2.r:o1.f-o2.f); 
        }
        
        public int get(int key) {
            id++;
            if (hashMap.containsKey(key)) {
                update(key);
                return hashMap.get(key);
            }
            return -1;
        }
        
        public void set(int key, int value) {
            if (capacity==0) return;
            id++;
            if (hashMap.containsKey(key)) {
                update(key);
                hashMap.put(key, value);
                return;
            }
            if (hashMap.size()==capacity) {
                Cache first= queue.poll(); // find the smallest one, and remove it
                hashMap.remove(first.key);
                frequency.remove(first.key);
            }
            hashMap.put(key, value);
            frequency.put(key, 1);
            queue.add(new Cache(key, 1, id));
        }
        
        private void update(int key) { // update the priority queue
            int f=frequency.get(key);
            frequency.put(key, f+1); // get and update the frequency
            Cache cache=new Cache(key, f+1, id); // make a new Cache
            // remove the member in queue, if its key equals to the current key.
            // Here, queue uses `equals()` to judge the equality
            queue.remove(cache); 
            queue.add(cache); // add the current Cache to the queue.
        }
    }
    

    PS: I tried TreeSet instead of PriorityQueue, but it didn't work. Can anyone tell me why?





    Update 2016/11/22:
    As priority queue uses O(n) time to remove, it's better to use TreeSet.

    Here is the code. It's similar to the code above.

    public class LFUCache {
        
        class Cache implements Comparable<Cache> {
            int key, f, r;
            public Cache(int k, int f, int r) {key=k;this.f=f;this.r=r;}
            public boolean equals(Object object) {return key==((Cache) object).key;}
            public int hashCode() {return key;}
            public int compareTo(Cache o) {return key==o.key?0:f==o.f?r-o.r:f-o.f;}
        }
    
        int capacity,id;
        HashMap<Integer, Integer> hashMap;
        HashMap<Integer, Cache> caches;
        TreeSet<Cache> treeSet;
    
        public LFUCache(int capacity) {
            this.capacity=capacity;
            id=0;
            hashMap=new HashMap<>();
            caches=new HashMap<>();
            treeSet=new TreeSet<>();
        }
    
        public int get(int key) {
            id++;
            if (hashMap.containsKey(key)) {
                update(key);
                return hashMap.get(key);
            }
            return -1;
        }
    
        public void set(int key, int value) {
            if (capacity==0) return;
            id++;
            if (hashMap.containsKey(key)) {
                update(key);
                hashMap.put(key, value);
                return;
            }
            if (hashMap.size()==capacity) {
                Cache first=treeSet.pollFirst();
                hashMap.remove(first.key);
                caches.remove(first.key);
            }
            hashMap.put(key, value);
            Cache cache=new Cache(key, 1, id);
            caches.put(key, cache);
            treeSet.add(cache);
        }
    
        private void update(int key) {
            int f=caches.get(key).f;
            treeSet.remove(caches.get(key));
            Cache cache=new Cache(key, f+1, id);
            caches.put(key, cache);
            treeSet.add(cache);
        }
    
    }
    

  • 2
    O

    Very nice solution. But I think your update() function takes O(n) to update the key.


  • 1
    C

    @onaiplee Oh, that's a mistake... PriorityQueue.remove(Object) is linear time...
    I think using TreeSet instead of PriorityQueue may be better, as TreeSet.remove() is no doubt O(logn).


  • 0
    R

    @ckcz123

    TreeSet didn't work because it uses the comparator / comparable for equality checks.
    I faced the same issue.
    I could complete it if i used another map to store time for each key.

    public class LFUCache {
        class Data implements Comparable<Data> {
            public int key;
            public int freq;
            public int time;
            public Data(int key, int freq, int time) {
                this.key = key;
                this.freq = freq;
                this.time = time;
            }
            
            @Override 
            public int compareTo(Data d) {
                if(d.key == key) return 0;
                return freq==d.freq ? time-d.time : freq - d.freq;
            }
            
            @Override
            public boolean equals(Object o) {
                Data d = (Data) o;
                return d.key == key && freq == d.freq && time == d.time;
            }
            
            @Override
            public int hashCode() {
                return key;
            }
        }
        
        int t;
        TreeSet<Data> queue = new TreeSet<Data>();
        Map<Integer, Integer> cache = new HashMap<Integer, Integer>();
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        Map<Integer, Integer> time = new HashMap<Integer, Integer>();
        
        int capacity = 0;
        public LFUCache(int capacity) {
            this.capacity = capacity;
        }
        
        public int get(int key) {
            //System.out.println("get k:" + key );
            if(! cache.containsKey(key) || capacity == 0) {
                return -1;
            } else {
                incrementFreq(key);
                return cache.get(key);
            }
        }
        
        private void incrementFreq(int key) {
            t ++;
            Data d = new Data(key, freq.getOrDefault(key, 0), time.getOrDefault(key, t));
            if(queue.remove(d)) {
                //System.out.println("q removed k: " + d.key);
            }
            //System.out.println("q add k: " + d.key);
            d.time = t;
            d.freq ++;
            freq.put(d.key, d.freq);
            time.put(d.key, d.time);
            queue.add(d);
            //System.out.println("incrementing  k:" + d.key + " f:" + d.freq + " t:" + d.time + " size:" + queue.size());
        }
        
        public void set(int key, int value) {
            if(capacity <= 0)
                return;
            System.out.println("set  k:" + key + " v:" + value);
            if(! cache.containsKey(key) && cache.size() == capacity) {
                Data d = queue.pollFirst();
                System.out.println("removing  k:" + d.key);
                freq.remove(d.key);
                time.remove(d.key);
                cache.remove(d.key);
            }
            incrementFreq(key);
            cache.put(key, value);
        }
    }
    

  • 0
    C

    @ramprasad2 It can be simpler with a HashMap<Integer, Cache>
    I've updated the code with TreeSet in my post.


  • 0
    W

    Brilliant solution!


  • 0
    W
    This post is deleted!

  • 0
    S

    Using TreeSet will cost O(LogN) time to remove, so you cannot guarantee a O(1) solution


  • 0
    B

    good solution. besides, you can make the heap as a "hashheap" which can support remove in o(lng) time.

    one more problem is when the id go over max value in integer? I think that is common case in cache, how to handle that?


  • 0
    C

    @bighehe TreeSet is O(logn)
    What does 'when the id go over max value in integer' mean?


  • 1
    O

    Hey folks,

    That's a good solution above. I have one suggestion, take it with a pinch of salt:

    Talking about "n" which you haven't defined anywhere, is a problem. Interviewers don't like ambiguity, that's my take away from quite a few unsuccessful interviews.

    Is n number of distinct keys?
    Is n number of distinct frequencies?
    Is n number of set & gets ?
    Is n number of set & gets on distinct keys?

    So, let's not talk about "n", but talk about the known variables.

    As an example, based on the TreeSet answer, where cap is capacity of LFU cache:

    1. get() time complexity: O(1) for cache look up and frequency update, O (log (cap)) for tree update (like heapify), total O (log (cap))
    2. set() time complexity:
      a. Create/ Insert:
      i. If cap hasn't been reached, O (log(cap)) to find the location for the new node, O(1) time to create and add, O (log(cap)) to update the tree (like heapify), total: O(log(cap)) time
      ii. If cap is reached, O(1) time to get the head, update the key, freq and recent, O (log(cap)) to update the tree (like heapify, but this time per recentness), total: O(log(cap)) time
      b) Update: O (log(cap)) to find the node, O (log(cap)) to update the tree (like heapify), total: O(log(cap)) time

    Does it make sense? Let's iterate!


  • 0
    K

    Clean and smart solution
    UPVOTING+1

    Just wondering why PriorityQueue is working as well, though remove costs O(n).
    Also, you don't have to override the hashCode function no matter using PQ or TreeMap. And putting comparator into collection is always working for both PQ and TreeMap. (following is rephrased code)

     class Cache {
            int key, f, r;
            public Cache(int k, int f, int r) {key=k;this.f=f;this.r=r;}
            public boolean equals(Object object) {return key==((Cache) object).key;}
            /**
            public int hashCode() {return key;}
            implements Comparable<Cache> 
            public int compareTo(Cache o) {return key==o.key?0:f==o.f?r-o.r:f-o.f;}
            */
        }
    
        int capacity,id;
        HashMap<Integer, Integer> hashMap;
        HashMap<Integer, Cache> caches;
        TreeSet<Cache> treeSet;
    
        public LFUCache(int capacity) {
            this.capacity=capacity;
            id=0;
            hashMap=new HashMap<>();
            caches=new HashMap<>();
            treeSet=new TreeSet<>(new Comparator<Cache>() {
                public int compare(Cache c1, Cache c2) {
                    int res = c1.f == c2.f ? c1.r - c2 .r : c1.f - c2.f;
                    return res;
                }
            });
        }

  • 0
    Y

    @ckcz123 I think it is better to put value in class cache then only use one Hashmap <key, Cache>. So that when retrieving value, use map.get(key).value.


  • 0
    N

    @ckcz123
    what is your running time? my java solution using PQ needs around 500 ms.


  • 0
    J

    @ckcz123 Hi, Could you explain why in the treeSet implementation, we are not able to just simply use treemap.remove(cache) just like what we did in the priority queue implementation, but need to construct a hashmap<Integer, Cache> to retrieve the cache node?


  • 0
    Y

    @ckcz123
    Thanks for your brilliant idea!
    However, I think we can use one HashMap mapping from key to cache. There is no need to maintain two hashmaps, which is simpler.
    Here goes my code based on your idea:

    public class LFUCache {
        
        Map<Integer, Cache> caches;
        int cap, time;
        TreeSet<Cache> set;
    
        public LFUCache(int capacity) {
            cap = capacity;
            time = 0;
            caches = new HashMap<>();
            set = new TreeSet<>();
        }
        
        public int get(int key) {
            if(!caches.containsKey(key)) return -1;
            time++;
            update(key, caches.get(key).value);
            return caches.get(key).value;
        }
        
        public void put(int key, int value) {
            if(cap <= 0) return;
            
            time++;
            if(caches.containsKey(key)) {
                update(key, value);
                return;
            }
            if(caches.size() == cap) {
                Cache first = set.pollFirst();
                caches.remove(first.key);
            }
            Cache curr = new Cache(key, value, 1, time);
            caches.put(key, curr);
            set.add(curr);
        }
        
        private void update(int key, int value) {
            Cache old = caches.get(key);
            Cache curr = new Cache(key, value, old.freq + 1, time);
            set.remove(old); // remove() uses 'equals()' to judge the equality
            set.add(curr);
            caches.put(key, curr);
        }
        
        class Cache implements Comparable<Cache> {
            int key;
            int value;
            int freq;
            int time;
            
            public Cache(int k, int v, int f, int t) {
                key = k;
                value = v;
                freq = f;
                time = t;
            }
            
            public boolean equals(Object o) {
                if(!(o instanceof Cache)) return false;
                return key == ((Cache) o).key;
            }
            
            public int hashCode() {
                return key;
            }
            
            public int compareTo(Cache c) {
                return freq == c.freq? time - c.time : freq - c.freq;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.