LFU Cache

This page explains Java solution to problem LFU Cache using HashMap data structure.

Problem Statement

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.

Follow up: Could you do both operations in O(1) time complexity?

Example 1:
LFUCache cache = new LFUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class LfuCache {

    private int capacity = 0;
    private int min = 1;
    private HashMap<Integer, Integer> valueMap;
    private HashMap<Integer, Integer> countMap;
    private HashMap<Integer, LinkedHashSet<Integer>> countGroupMap;

    public LfuCache(int capacity) {
        this.capacity = capacity;
        this.valueMap = new HashMap<>();
        this.countMap = new HashMap<>();
        this.countGroupMap = new HashMap<>();
    }

    public int get(int key) {
        if(valueMap.containsKey(key)) {
            updateFrequency(key);
            return valueMap.get(key);
        }
        else return -1;
    }

    public void put(int key, int value) {
        if(capacity == 0) return;

        if(valueMap.containsKey(key)) {
            updateFrequency(key);
            valueMap.put(key, value);
        }
        else {
            if(valueMap.size() == capacity) {
                LinkedHashSet<Integer> minCountSet = countGroupMap.getOrDefault(min, new LinkedHashSet<>());

                int toBeRemoved = minCountSet.iterator().next();

                //Remove from countGroupMap
                minCountSet.remove(toBeRemoved);

                //Remove from valueMap
                valueMap.remove(toBeRemoved);

                //Remove from countMap
                countMap.remove(toBeRemoved);

                put(key, value);
            }
            else {
                //Update valueMap
                valueMap.put(key, value);

                //Add to countMap
                countMap.put(key, 1);

                //Update countGroupMap
                LinkedHashSet<Integer> countSet = countGroupMap.getOrDefault(1, new LinkedHashSet<>());
                countSet.add(key);
                countGroupMap.put(1, countSet);

                //Update min
                min = 1;
            }
        }
    }

    private void updateFrequency(int key) {
        int oldCount = countMap.getOrDefault(key, 0);
        int newCount = oldCount + 1;

        //Update key's count
        countMap.put(key, newCount);

        //Remove key from oldCountGroup
        LinkedHashSet<Integer> oldSet = countGroupMap.getOrDefault(oldCount, new LinkedHashSet<>());
        oldSet.remove(key);
        if(oldSet.size() == 0) {
            countGroupMap.remove(oldCount);
            if(min == oldCount) min = newCount;
        }

        //Add key to newCountGroup
        LinkedHashSet<Integer> newSet = countGroupMap.getOrDefault(newCount, new LinkedHashSet<>());
        newSet.add(key);
        countGroupMap.put(newCount, newSet);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LfuCache obj = new LfuCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Time Complexity

O(1)

Space Complexity

O(1)