# 20191209

https://www.youtube.com/watch?v=S6IfqDXWa10

Least Recently Used 
LRUCache cache = new LRUCache( 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.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

k : v
4 : 4 -> 3 : 3

class LRUCache {
    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int capacity = 0;
    private int count = 0;
    private DLinkedNode head;
    private DLinkedNode tail;
    
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode pre;
        DLinkedNode post;
    }
    
    // null <-> head  <-> tail <-> null;
//    public void addNode(DListNode node) {
//        head.pre = node;
//        node.post = head;
//        head = node;
//    }
    // head <-> 1 <-> 2 <-> 3 <-> tail
    // head <-> 4 <-> 1 <-> 2 <-> 3 <-> tail
    private void addNode(DLinkedNode node) {
        node.pre = head;
        node.post = head.post;

        head.post.pre = node;
        head.post = node;
    }
    
//    public void removeNode(DListNode node) {
//        node.pre.post = node.post.pre;
//        node.post.pre = node.pre.post;
//    }
    
    // head <-> 4 <-> 1 <-> 2 <-> 3 <-> tail
    // head <-> 4 <-> 1 <-> 3 <-> tail
    private void removeNode(DLinkedNode node){
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;

        pre.post = post;
        post.pre = pre;
    }
    
//    public void moveHead(DListNode node) {
//        this.removeNode(node);
//        this.addNode(node);
//    }
    
    private void moveToHead(DLinkedNode node){
        this.removeNode(node);
        this.addNode(node);
    }
    
//    public DListNdoe popTail() {
//        // tail.pre.post = null;
//        DListNdoe tempTail = tail.pre;
//        remove(tempTail);
//        return tempTail;
//    }
    
    private DLinkedNode popTail(){
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }

    // null <-> head <-> tail <-> null;
    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;
        
        head = new DListNode();
        tail = new DListNode();
        head.pre = null;
        tail.post = null;
        
        head.post = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        DListNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        
        this.moveHead(node);
        
        return node.value;
    }
    
    public void put(int key, int value) {
        DListNode node = cache.get(key);
    
        if (node == null) {
            DListNode newNode = new DListNode();
            newNode.key = key;
            newNode.value = value;
            
            this.cache.put(key, newNode);
            
            count++;
            
            if (count > capacity) {
                DListNode removedNode = this.popTail();
                this.cache.remove(removedNode);
                conut--;
            }
        } else {
            node.value = value;
            this.moveHead(node);
        }
    }
}

// FizzBuzz
Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

n = 15,

Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]

public List<String> fizzBuzz(int n) {     
   List<String> result = new ArrayList();
   for (int = 1; i <= n; i++) {
      if (i % 3 == 0 && i % 5 == 0) {
         result.add("FizzBuzz");
      } else if (i % 3 == 0) {
         result.add("Fizz");
      } else if (i % 5 == 0) {
         result.add("Buzz");
      } else {
         result.add(i + '');
      }
   }
   return result;
}