Added 3 solutions

varunu28 · varunu28 · commit 62f60b49a7ce · 2018-10-11T11:54:46.000-07:00
diff --git a/Hard/LRU Cache.java b/Hard/LRU Cache.java
@@ -0,0 +1,96 @@
+class LRUCache {
+
+    Map<Integer, Node> map;
+    Node head, tail;
+    int capacity;
+    int count;
+
+    public LRUCache(int capacity) {
+        map = new HashMap<>();
+        this.capacity = capacity;
+
+        head = new Node();
+        head.previous = null;
+
+        tail = new Node();
+        tail.next = null;
+
+        head.next = tail;
+        tail.previous = head;
+
+        this.count = 0;
+    }
+
+    public int get(int key) {
+        Node node = map.get(key);
+
+        if (node == null) {
+            return -1;
+        }
+
+        moveToHead(node);
+        
+        return node.val;
+    }
+
+    private void moveToHead(Node node) {
+        removeNode(node);
+        addNode(node);
+    }
+
+    private void addNode(Node node) {
+        node.previous = head;
+        node.next = head.next;
+
+        head.next.previous = node;
+        head.next = node;
+    }
+
+    private Node popTail() {
+        Node res = tail.previous;
+        removeNode(res);
+
+        return res;
+    }
+
+    private void removeNode(Node node) {
+        Node pre = node.previous;
+        Node post = node.next;
+
+        pre.next = post;
+        post.previous = pre;
+    }
+
+    public void put(int key, int value) {
+        Node node = map.get(key);
+
+        if (node == null) {
+            Node newNode = new Node();
+            newNode.key = key;
+            newNode.val = value;
+
+            map.put(key, newNode);
+            addNode(newNode);
+
+            count++;
+
+            if (count > capacity) {
+                Node tail = popTail();
+                map.remove(tail.key);
+                count--;
+            }
+        }
+        else {
+            node.val = value;
+            moveToHead(node);
+        }
+    }
+
+    private class Node {
+        Node previous;
+        Node next;
+        int key;
+        int val;
+    }
+}
+
diff --git a/Medium/Coin Change.java b/Medium/Coin Change.java
@@ -0,0 +1,18 @@
+class Solution {
+    public int coinChange(int[] coins, int amount) {
+        int max = amount + 1;
+        int[] cache = new int[amount + 1];
+        Arrays.fill(cache, max);
+        cache[0] = 0;
+
+        for (int i=1; i<=amount; i++) {
+            for (int j=0; j<coins.length; j++) {
+                if (coins[j] <= i) {
+                    cache[i] = Math.min(cache[i], cache[i - coins[j]] + 1);
+                }
+            }
+        }
+
+        return cache[amount] > amount ? -1 : cache[amount];
+    }
+}
diff --git a/Medium/Container With Most Water.java b/Medium/Container With Most Water.java
@@ -0,0 +1,24 @@
+class Solution {
+    public int maxArea(int[] height) {
+        int start = 0;
+        int end = height.length - 1;
+        int mul = end;
+        int res = Integer.MIN_VALUE;
+
+        while (end - start >= 1) {
+            int temp = mul * Math.min(height[start], height[end]);
+            res = Math.max(res, temp);
+
+            if (height[start] < height[end]) {
+                start++;
+            }
+            else {
+                end--;
+            }
+
+            mul--;
+        }
+
+        return res;
+    }
+}
