Java Solution - O(n) with two HashMaps


  • 0
    P

    I have a simple O(n) solution in Java using two HashMaps. It is failing some test cases (passing 17 out of 24). Can anyone help with figuring out what might be wrong with it?

    
    
    import java.util.Date;
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * Created by pmandrek on 30/12/16.
     */
    public class LFUCache {
    
        class CacheObjectProperty{
    
            long lastAccessed;
            Integer frequency;
    
            public CacheObjectProperty(){
                this.lastAccessed = System.nanoTime();
                this.frequency = 0;
            }
    
            public void setLastAccessed(long lastAccessed){
                this.lastAccessed = lastAccessed;
            }
    
            public void updateFrequency(){
                this.frequency++;
            }
    
            public long getLastAccessed(){
                return this.lastAccessed;
            }
    
            public int getFrequency(){
                return this.frequency;
            }
    
    
        }
    
        private Map<Integer, Integer> cache;
        private Map<Integer, CacheObjectProperty> cacheProperty;
        private int capacity;
    
        public LFUCache(int capacity) {
            this.cache = new HashMap<>(capacity);
            this.capacity = capacity;
            this.cacheProperty = new HashMap<>();
        }
    
        public int get(int key) {
            if(this.cache.containsKey(key)){
    
                updateCacheProperties(key);
                return cache.get(key);
    
            }
    
            return -1;
        }
    
        public void set(int key, int value) {
    
            if(!this.cache.containsKey(key)){
                if(this.cache.size() >= this.capacity){
                    Integer evict = getKeyToEvict();
                    if(evict == null){
                        return;
                    }
    
                    this.cache.remove(evict);
                    this.cacheProperty.remove(evict);
                    //System.out.println("Evicting " + evict);
    
                }
            }
    
            cache.put(key, value);
            updateCacheProperties(key);
        }
    
        private void updateCacheProperties(int key){
    
            CacheObjectProperty cacheObjectProperty;
            if(this.cacheProperty.containsKey(key)){
                cacheObjectProperty = this.cacheProperty.get(key);
            }else{
                cacheObjectProperty = new CacheObjectProperty();
            }
    
            cacheObjectProperty.updateFrequency();
            cacheObjectProperty.setLastAccessed(System.nanoTime());
    
            this.cacheProperty.put(key, cacheObjectProperty);
        }
    
        private Integer getKeyToEvict(){
    
            Integer min = null;
            Integer minKey = null;
            Map<Integer, Long> minFrequencyMap = new HashMap<>();
    
            if(this.cacheProperty == null){
                return -1;
            }
    
            for(Map.Entry<Integer, CacheObjectProperty> e : this.cacheProperty.entrySet()){
    
    
    
                if(min == null){
                    min = e.getValue().getFrequency();
                    minKey = e.getKey();
                    minFrequencyMap.put(e.getKey(), e.getValue().getLastAccessed());
                    continue;
                }
    
    
                if(e.getValue().getFrequency() < min){
                    //Found a new low frequency so reset min map and add entry
                    minFrequencyMap.clear();
                    minFrequencyMap.put(e.getKey(), e.getValue().getLastAccessed());
                    minKey = e.getKey();
    
                }else if(e.getValue().getFrequency() == min){
                    minFrequencyMap.put(e.getKey(), e.getValue().getLastAccessed());
                    minKey = e.getKey();
                }
            }
    
            if(minFrequencyMap.size() > 1){
                Long minDate = null;
                for(Map.Entry<Integer, Long> e : minFrequencyMap.entrySet()){
    
                    //System.out.println("Key " + e.getKey() + "  ,Value " + e.getValue());
    
                    if(minDate == null){
                        minDate = e.getValue();
                        minKey = e.getKey();
                        continue;
                    }
    
    
                    if(e.getValue() < minDate){
                        minDate = e.getValue();
                        minKey = e.getKey();
                    }
    
                }
            }
    
            return minKey;
        }
    }
    
    
    
    

Log in to reply
 

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