Can anyone find the flaw in my solution? I keep getting 18/23 test cases passed.


  • 0
    H
    import java.util.*;
    
    public class LFUCache {
        
    	class Node {
    		int freq;
    		Node next;
    		Node prev;
    		LinkedHashSet<Integer> LHS;
    		
    		Node(int freq) {
    			this.freq = freq;
    			LHS = new LinkedHashSet<Integer>();
    		}
    	}
    	//vars
    	private HashMap<Integer, Integer> valueMap;
    	private HashMap<Integer, Node> FNmap;
    	private int capacity;
    	private int currCapacity = 0;
    	Node head = null;
    	
    	public LFUCache(int capacity) {
    		this.capacity = capacity;
    		valueMap = new HashMap<Integer, Integer>();
    		FNmap = new HashMap<Integer, Node>();
    		this.capacity = capacity;
    	}
    	
    	public void put(int key, int val) {
    		if (capacity == 0) {
    			return;
    		}
    		
    		//variables
    		Node currNode = null;
    		Node nextNode = null;
    		
    		boolean exists = valueMap.containsKey(key);
    		valueMap.remove(key);
    		valueMap.put(key, val);
    		if (exists) {
    			currNode = FNmap.get(key);
    			currNode.LHS.remove(key);
    			nextNode = FNmap.get(currNode.freq + 1);
    			
    			if (nextNode == null) {
    				nextNode = new Node(currNode.freq + 1);
    				addNext(currNode, nextNode);
    			} 
    			
    			nextNode.LHS.add(key);
    			
    			if (currNode.LHS.size() == 0) {
    				remove(currNode);
    			}
    			
    			FNmap.remove(key);
    			FNmap.put(key, nextNode);
    			
    		} else {
    			
    			if (currCapacity >= capacity) {
    				purge();
    				currCapacity--;
    			}
    			if (head == null || head.freq != 1) {
    				currNode = new Node(1);
    				currNode.LHS.add(key);
    				addToHead(currNode);
    			} else if (head.freq == 1) {
    				head.LHS.add(key);
    			} 
    			FNmap.put(key, head);
    			currCapacity++;
    		}
    	}
    	
    	public int get (int key) {
    		if (capacity == 0) {
    			return -1;
    		}
    		boolean exists = valueMap.containsKey(key);
    		if (!exists) {
    			System.out.println("value map does not contain key " + key);
    			return -1;
    		} else {
    			Node node = FNmap.get(key);
    			FNmap.remove(key);
    			node.LHS.remove(key);
    			
    			Node nextNode = FNmap.get(node.freq+1);
    			if (nextNode == null) {
    				nextNode = new Node(node.freq + 1);
    				addNext(node, nextNode);
    			} 
    			nextNode.LHS.add(key);
    			
    			if (node.LHS.size() == 0) {
    				remove(node);
    			}
    			FNmap.put(key, nextNode);
    			System.out.println("getting key " + key + "  actual : " + valueMap.get(key));
    			return valueMap.get(key);
    		}
    	}
    	
    	//Remove node if the size if it's linked hash set is 0
    	
    	private void remove(Node node) {
    		if (node == null) { 
    			return;
    		}
    		if (node.prev == null && node.next == null) {
    			head = null;
    		} else if (node.prev == null  && node.next != null) {
    			node = node.next;
    			node.prev = null;
    			head = node;
    		} else if (node.next == null && node.prev != null) {
    			node.prev.next = null;
    		} else {
    			Node prev = node.prev;
    			prev.next = node.next;
    			node.next.prev = prev;
    		}
    	}
    	
    	
       private void remove_old(Node node) {
            if (node.prev == null) {
                head = node.next;
            } else {
                node.prev.next = node.next;
            } 
            if (node.next != null) {
                node.next.prev = node.prev;
            }
        }
    	
    	private void addNext(Node currNode, Node nextNode) {
    		Node currNext = currNode.next;
    		if (currNext == null) {
    			currNode.next = nextNode;
    			nextNode.prev = currNode;
    		} else {
    			currNode.next = nextNode;
    			nextNode.prev = currNode;
    			nextNode.next = currNext;
    			currNext.prev = nextNode;
    		}
    	}
    	
    	private void addToHead(Node node) {
    		Node next = head;
    		head = node;
    		if (next != null) {
    			head.next = next;
    			next.prev = head;
    			head.prev = null;
    		}
    	}
    	
    	private void purge() {
            Iterator<Integer> itr = head.LHS.iterator();
            //LinkedList<Integer> list = new LinkedList<Integer>(head.LHS);
            //Iterator<Integer> itr = list.descendingIterator();
            
            int keyToPurge = -1;
            while (itr.hasNext()) {
                keyToPurge = itr.next();                   
                itr.remove();
                break;
            }
            System.out.println("Purging key " + keyToPurge + " from node frequency " + head.freq);
            head.LHS.remove(keyToPurge);
            FNmap.remove(keyToPurge);
            valueMap.remove(keyToPurge);
            
            if (head.LHS.size() == 0) { ////////////?
            	/*
            	Node n = head.next;
            	if (n == null) {
            		head = new Node(0);
            	} else {
            		head = n;
            	}*/
            	head = head.next;
            }
    	}
    	
    	public void printHM() {
    		System.out.println("\n Hashmap contents: \n");
            for (Map.Entry<Integer, Integer> entry : valueMap.entrySet()) {
                System.out.println( "key : " + entry.getKey() + "  value : " + entry.getValue());
            }
    	}
    	
    	public void printFN() {
            System.out.println("\n Frequencies: \n");
            for (Map.Entry<Integer, Node> entry : FNmap.entrySet()) {
                System.out.println( "key : " + entry.getKey() + " frequency : " + entry.getValue().freq);
                Iterator<Integer> itr = entry.getValue().LHS.iterator();
                System.out.println("content(s) ");
                while (itr.hasNext()) {
                    System.out.println("\t" + itr.next());
                }
                System.out.println();
            }
    	}
    }
    

Log in to reply
 

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