# 20191210

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

dummyHead <-> 1 <-> 3 <-> dummyTail

class LRUCache {

    class DLinkedNode {
        int val;
        int key;
        DLinkedNode pre;
        DLinkedNode post;
    }
    
    private int capacity;
    private int counter = 0;
    private DLinkedNode head;
    private DLinkedNode tail;
    private Map<Integer, DLinkedNode> map = new HashMap();

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.post = tail;
        tail.pre = head;
    }
    
    // dummyHead <-> 1 <-> 3 <-> 5 <-> dummyTail
    private void addNode(DLinkedNode node) {
        node.pre = head;
        node.post = head.post;
        
        head.post.pre = node;
        head.post = node;
    }
    
    // dummyHead <-> 1 <-> 3 <-> dummyTail
    private void removeNode(DLinkedNode node) {
          node.pre.post = node.post;
          node.post.pre = node.pre;
    }
    
    private void moveToHead(DLinkedNode node) {
        this.addNode(node);
        this.removeNode(node);
    }
    
    private DLinkedNode removeTail() {
        DLinkedNode node = tail.pre;
        this.removeNode(tail.pre);
        return node;
    }
    
    public int get(int key) {
        DLinkedNode node = map.get(key);
        if (node == null) return -1;
        this.moveToHead(node);
        return node.val;
    }
    
    public void put(int key, int value) {
       DLinkedNode node = map.get(key);
        if (node == null) {
           DLinkedNode newNode = new DLinkedNode();
           newNode.val = value;
           newNode.key = key;
           this.addNode(newNode);
           this.map.put(key, newNode);
           counter++;
           if (counter > capacity) {
               DLinkedNode removedNode = removeTail();
               map.remove(removedNode.key);
               counter--;
           }
        } else {
           node.val = value;
           moveToHead(node);
        }
    }
}

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

Example 1:
Input: [3,4,5,1,2] 
Output: 1


Example 2:
Input: [4,5,6,7,0,1,2]
Output: 0

public int findMin(int[] nums) {
    int min = Integer.MAX_VALUE;
    for (int num : nums) {
        min = Math.min(min, num);
    }
    
    return min;
}

public int findMin(int[] nums) {
    int low = 0;
    int high = nums.length - 1;
    // [3,4,5,6,2] mid > high
    // [5,1,2,3,4] mid <= high
    while (low <= high) {
        int mid = (low + high) >>> 1;
        if (nums[mid] > nums[high]) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    } 
    return nums[low];
}