Thursday, November 6, 2014

Facebook: Implement a LRU Cache

Implement a LRU cache

Leetcode: http://buttercola.blogspot.com/2014/08/leetcode-lru-cache.html

Code (Java):
public class LRUCache {
    private class ListNode {
        int key;
        int value;
        ListNode next;
        ListNode prev;
        
        ListNode (int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    ListNode head = null;
    ListNode tail = null;
    int capacity;
    int size = 0;
    HashMap<Integer, ListNode> map = new HashMap<Integer, ListNode>();
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            int result = map.get(key).value;
            // Move the  to the head of the list.
            ListNode temp = map.get(key);
            deleteNode(temp);
            insertHead(temp);
            
            return result;
        } else {
            return -1;
        } 
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            ListNode temp = map.get(key);
            deleteNode(temp);
            temp.value = value;
            
            insertHead(temp);
            map.put(key, temp);
        } else {
            ListNode temp = new ListNode(key, value);
            if (size < capacity) {
                insertHead(temp);
                map.put(key, temp);
                size++;
            } else {
                map.remove(tail.key);
                deleteNode(tail);
                insertHead(temp);
                map.put(key, temp);
            }
        }
    }
    
    private void insertHead(ListNode node) {
        if (head == null) {
            head = node;
            tail = node;
            head.prev = null;
            tail.next = null;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
            head.prev = null;
        }
    }
    
    private void deleteNode(ListNode node) {
        if (node == head) {
            head = head.next;
            if (head != null) {
                head.prev = null;
            } else {
                tail = null;
            }
        } else if (node == tail) {
            tail = tail.prev;
            if (tail != null) {
                tail.next = null;
            } else {
                head = null;
            }
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    }
}

Discussion:
The error-prone parts of the implementation is when we delete a node, we need to check if the node to be deleted is the head, tail or internal node of he list. 
If it is the head or tail, after we remove the node, we need to check if the list becomes null, i.e, the list had only 1 node before. That is because we couldn't set a null node's prev or next node, which are null as well.


No comments:

Post a Comment