enterpredator · February 3, 2017 06:22 · Feb 1, 2017 · Jan 31, 2017 · Jan 31, 2017 · Nov 28, 2016
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1810,10 +1810,10 @@ private boolean isRowValid(int[][] board, int row){
             return false;
         }
 
-        if(uniqueNumbers.contains(i)){ // found duplicate
+        if(uniqueNumbers.contains(value)){ // found duplicate
             return false;
         } else {
-            uniqueNumbers.add(i);
+            uniqueNumbers.add(value);
         }
     }
 

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -737,8 +737,8 @@ void swap(int array[], int left, int right){
 ```
 
 ### Radix Sort
-* Radix sort is a sorting algorithm for integers (and some other data types) that takes advantage of the fact that integers have a finite number of bits. In radix sort, we iterate through each digit of the number, grouping numbers by each digit. For example, if we have an array of integers, we might first sort by the first digit, so that the Os are grouped together. Then, we sort each of these groupings by the next digit. We repeat this process sorting by each subsequent digit, until finally the whole array issorted.
-* Unlike comparison sorting algorithms, which cannot perform better than 0(n log(n)) in the average case, radix sort has a runtime of 0(kn), where n is the number of elements and k is the number of passes of the sorting algorithm.
+* Radix sort is a sorting algorithm for integers (and some other data types) that takes advantage of the fact that integers have a finite number of bits. In radix sort, we iterate through each digit of the number, grouping numbers by each digit. For example, if we have an array of integers, we might first sort by the first digit, so that the 0s are grouped together. Then, we sort each of these groupings by the next digit. We repeat this process sorting by each subsequent digit, until finally the whole array is sorted.
+* Unlike comparison sorting algorithms, which cannot perform better than O(n log(n)) in the average case, radix sort has a runtime of O(kn), where n is the number of elements and k is the number of passes of the sorting algorithm.
 
 ```java
 void radixSort(int[] a){

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -330,7 +330,7 @@ class Node {
 ### Breadth First Search
 * An algorithm for traversing or searching tree or graph data structures. 
 * It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.
-* Breadth First Search algorithm(BFS) traverses a graph in a breadthwards motion and uses a queue.
+* The Breadth First Search (BFS) algorithm traverses a graph in a breadthwards motion and uses a queue.
 * This traversal visits nodes by levels from top to bottom and from left to right.
 * Breadth first search can also be useful to find the shortest path.
 

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -116,6 +116,7 @@
   * [LRU Cache] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#lru-cache)
   * [LinkedList Cycle] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#linkedlist-cycle)
   * [Reverse Stack] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#reverse-stack)
+  * [Valid Expression] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#valid-expression)
 
 ## Data Structures
 
@@ -2143,4 +2144,68 @@ void insert(Stack stack, Object obj){
         stack.push(element);
     }
 }
-```
+```
+
+### Valid Expression
+* Given a string   ((0+4)+(1x3)  ) Or ( { } ) { ] [ } Or { ( [ (1*3) +2 ] )  / a+ [12 ] } Or { ( a+b ) Output whether the expression is valid (that is, the brackets “match up”). No need to evaluate results. 1 and 3 are valid, 2 and 4 are not.
+
+```java
+String a = "((0+4)+(1x3)  )";
+String b = "( { } ) { ] [ }";
+String c = "{ ( [ (1*3) +2 ] )  / a+ [12 ] }";
+String d = "{ ( a+b )";
+
+System.out.println(String.format("Exp a is %b", isValidExpression(a)));
+System.out.println(String.format("Exp b is %b", isValidExpression(b)));
+System.out.println(String.format("Exp c is %b", isValidExpression(c)));
+System.out.println(String.format("Exp d is %b", isValidExpression(d)));
+
+public static boolean isValidExpression(String exp){
+    Stack<Character> bracesStack = new Stack<Character>();
+
+    for(int i=0; i<exp.length(); i++){
+      char c1 = exp.charAt(i);
+
+      if(isOpeningChar(c1)){
+        bracesStack.push(c1);
+      } else if(isClosingChar(c1)) {
+        char c2 = bracesStack.peek();
+        if(isMatchingBrace(c2, c1))
+          bracesStack.pop();
+        else
+          return false;
+      } 
+    }
+
+    if(bracesStack.isEmpty())
+      return true;
+
+	return false;
+}
+
+private static boolean isOpeningChar(char c1){
+	if(c1 == '(' || c1 == '[' || c1 == '{')
+      return true;
+    else
+      return false;
+}
+
+private static boolean isClosingChar(char c1){
+	if(c1 == ')' || c1 == ']' || c1 == '}')
+      return true;
+    else
+      return false;
+}
+
+private static boolean isMatchingBrace(char c1, char c2){
+	if(c1 == '(' && c2 == ')'){
+		return true;  
+    } else if(c1 == '{' && c2 == '}'){
+      return true;
+    } else if(c1 == '[' && c2 == ']'){
+      return true;
+    } 
+
+	return false;
+}
+```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -265,6 +265,15 @@ class Queue {
 		return null;
 	}
 }
+
+class Node {
+    Object data;
+    Node next;
+
+    Node(Object item){
+        data = item;
+    }
+}
 ```
 
 ### Vectors

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -115,6 +115,7 @@
   * [BigInt sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#bigint-sum)
   * [LRU Cache] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#lru-cache)
   * [LinkedList Cycle] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#linkedlist-cycle)
+  * [Reverse Stack] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#reverse-stack)
 
 ## Data Structures
 
@@ -2108,4 +2109,29 @@ boolean hasCycle(Node first) {
     }
     return false;  // fast reached null, so the list terminates
 }
+```
+
+### Reverse Stack
+* Reverse the elements of a stack without using another data structure.
+
+```java
+void reverseStack(Stack stack) {
+    if (stack.isEmpty()) {
+        return;
+    } else {
+        Object obj = stack.pop();
+        reverseStack(stack);
+        insert(stack, obj);
+    }
+}
+
+void insert(Stack stack, Object obj){
+    if (stack.isEmpty()) {
+        stack.push(obj);
+    } else {
+        Object element = stack.pop();
+        insert(stack, obj);
+        stack.push(element);
+    }
+}
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1724,16 +1724,29 @@ public String stringCompression(String uncompressedString){
 
 ```java
 public void twoSum(int[] array, int sum){
-    Map<Integer, Integer> map = new HashMap<>();
+    Map<Integer, List<Integer>> map = new HashMap<>();
 
     for(int i=0; i<array.length; i++){
-        map.put(array[i], i);
+        if(map.containsKey(array[i])){
+            List<Integer> indices = map.get(array[i]);
+            indices.add(i);
+            map.put(array[i], indices);
+        } else {
+            List<Integer> indices = new ArrayList<>();
+            indices.add(i);
+            map.put(array[i], indices);
+        }
     }
 
     for(int i=0; i<array.length; i++){
         int b = sum - array[i];
-        if(map.containsKey(b) && i < map.get(b)){
-            System.out.println(String.format("twoSum() : Indices %d and %d add up to the target %d", i, map.get(b), sum));
+        if(map.containsKey(b)){
+            List<Integer> indices = map.get(b);
+            for(Integer index : indices){
+                if(i!=index && i < index){
+                    System.out.println(String.format("twoSum() : Indices %d and %d add up to the target %d", i, index, sum));
+                }
+            }
         }
     }
 }

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -114,6 +114,7 @@
   * [Fibonacci series] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#fibonacci-series)
   * [BigInt sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#bigint-sum)
   * [LRU Cache] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#lru-cache)
+  * [LinkedList Cycle] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#linkedlist-cycle)
 
 ## Data Structures
 
@@ -2075,4 +2076,23 @@ public class LRUCache {
     }
     // endregion
 }
+```
+
+### LinkedList Cycle
+* Detect if a linkedlist has a cycle.
+
+```java
+boolean hasCycle(Node first) {
+    Node slow = first;
+    Node fast = first;
+
+    while(fast != null && fast.next != null) {
+        slow = slow.next;          // 1 hop
+        fast = fast.next.next;     // 2 hops
+
+        if(slow == fast)  // fast caught up to slow, so there is a loop
+            return true;
+    }
+    return false;  // fast reached null, so the list terminates
+}
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1768,7 +1768,6 @@ public boolean isSudokuBoardValid(int[][] board){
             if(!isRegionValid(board, i, i + 2, j, j + 2)){
                 return false;
             }
-
             j+=3;
         }
         i+=3;

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1730,9 +1730,7 @@ public void twoSum(int[] array, int sum){
     }
 
     for(int i=0; i<array.length; i++){
-
         int b = sum - array[i];
-
         if(map.containsKey(b) && i < map.get(b)){
             System.out.println(String.format("twoSum() : Indices %d and %d add up to the target %d", i, map.get(b), sum));
         }

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1733,7 +1733,7 @@ public void twoSum(int[] array, int sum){
 
         int b = sum - array[i];
 
-        if(map.containsKey(b) && i!=map.get(b) && i < map.get(b)){
+        if(map.containsKey(b) && i < map.get(b)){
             System.out.println(String.format("twoSum() : Indices %d and %d add up to the target %d", i, map.get(b), sum));
         }
     }

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1930,4 +1930,152 @@ public String sum(String a, String b) {
 * `set(key, value)` - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
 
 ```java
+public class LRUCache {
+
+    // region Member Variables
+    private int capacity;
+    private Map<Integer, Node> data;
+    private Node head;
+    private Node tail;
+    // endregion
+
+    // region Constructors
+    public LRUCache(int capacity) {
+        this.capacity = capacity;
+        this.data = new HashMap<>();
+    }
+    // endregion
+
+    public int get(int key){
+
+        // Existing key
+        if(data.containsKey(key)){
+
+            // Move to first
+            Node node = data.get(key);
+            moveFirst(node);
+
+            return node.value;
+        }
+
+        // Not found
+        return -1;
+    }
+
+    public void set(int key, int value){
+        // Existing slot
+        if(data.containsKey(key)){
+            Node node = data.get(key);
+            node.value = value;
+            moveFirst(node);
+            return;
+        }
+
+        // Out of capacity, cleaning the oldest slot
+        if(data.size() >= capacity){
+            int id = tail.key;
+            removeLast();
+            data.remove(id);
+        }
+
+        // New slot
+        Node node = new Node(key, value);
+        add(node);
+        data.put(key, node);
+    }
+
+    private void add(Node node){
+        // Reset position
+        node.prev = null;
+        node.next = null;
+
+        // First element
+        if(head == null){
+            head = node;
+            tail = node;
+            return;
+        }
+
+        // Existing element
+        head.prev = node;
+        node.next = head;
+        head = node;
+
+    }
+
+    private void remove(Node node){
+        // Nothing to do
+        if(node == null || head == null){
+            return;
+        }
+
+        // The only one item
+        if(head == tail && node == head){
+            head = null;
+            tail = null;
+            return;
+        }
+
+        // Remove from head
+        if(node == head){
+            head.next.prev = null;
+            head = head.next;
+            return;
+        }
+
+        // Remove from end
+        if(node == tail){
+            tail.prev.next = null;
+            tail = tail.prev;
+            return;
+        }
+
+        // Remove in the middle
+        node.prev.next = node.next;
+        node.next.prev = node.prev;
+
+    }
+
+    // move a node to the head (for a cache hit)
+    private void moveFirst(Node node){
+        remove(node);
+        add(node);
+    }
+
+    // remove the oldest item which is the tail
+    private void removeLast(){
+        remove(tail);
+    }
+
+    public void printContents(){
+        if(head == null){
+            System.out.println("LRUCache is empty");
+            return;
+        }
+
+        Node currNode = head;
+
+        String contents = "";
+        while(currNode != null){
+            contents += String.format("%s ", currNode.value);
+            currNode = currNode.next;
+        }
+
+        System.out.println(String.format("LRUCache contents : %s", contents));
+    }
+
+    // region Inner Classes
+    private class Node {
+        Node prev;
+        Node next;
+        int key;
+        int value;
+
+        private Node(int key, int value) {
+            this.key = key;
+            this.value = value;
+        }
+    }
+    // endregion
+}
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -113,6 +113,7 @@
   * [Multiples of 3] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#multiples-of-3)
   * [Fibonacci series] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#fibonacci-series)
   * [BigInt sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#bigint-sum)
+  * [LRU Cache] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#lru-cache)
 
 ## Data Structures
 
@@ -1921,4 +1922,12 @@ public String sum(String a, String b) {
 
     return sb.toString();
 }
+```
+
+### LRU Cache
+* Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get() and set(). 
+* `get(key)` - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
+* `set(key, value)` - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
+
+```java
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1859,7 +1859,7 @@ private String multiplesOfThree(int[] a){
 ```
 
 ### Fibonacci series
-* The Fibonacci series is a series of numbers in which each number ( Fibonacci number ) is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, etc. // Write a recursive function to compute the nth number in the fibonacci series.
+* The Fibonacci series is a series of numbers in which each number ( Fibonacci number ) is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, etc. Write a recursive function to compute the nth number in the fibonacci series.
 
 ```java
 int fibonacci(int n) {

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -112,6 +112,7 @@
   * [Sudoku Board Validator] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#sudoku-board-validator)
   * [Multiples of 3] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#multiples-of-3)
   * [Fibonacci series] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#fibonacci-series)
+  * [BigInt sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#bigint-sum)
 
 ## Data Structures
 
@@ -1877,4 +1878,47 @@ int fibonacci(int n, int[] a) {
     }
     return a[n];
 }
+```
+
+### BigInt sum
+* Given two very long sequeces of digits, lets call these BigInts, write a function to calculate the sum of two BigInts. These sequences could be 1000 or more digits long. Think of the sequences as strings.
+
+```java
+public String sum(String a, String b) {
+    int d1, d2, tempSum;
+    int carry = 0;
+
+    int sumLength = (a.length()>b.length()) ? a.length() : b.length();
+    StringBuilder sb = new StringBuilder(sumLength);
+
+    int i=a.length()-1;
+    int j=b.length()-1;
+
+    while(i>=0 || j>=0){
+        d1 = 0;
+        d2 = 0;
+
+        if(i>=0) {
+            d1 = a.charAt(i) - '0';
+            i--;
+        }
+
+        if(j>=0) {
+            d2 = b.charAt(j) - '0';
+            j--;
+        }
+
+        tempSum = d1+d2+carry;
+        if(tempSum>9){
+            carry = tempSum / 10;
+            tempSum = tempSum % 10;
+        } else {
+            carry = 0;
+        }
+
+        sb.insert(0, tempSum);
+    }
+
+    return sb.toString();
+}
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -111,6 +111,7 @@
   * [Two Sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#two-sum)
   * [Sudoku Board Validator] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#sudoku-board-validator)
   * [Multiples of 3] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#multiples-of-3)
+  * [Fibonacci series] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#fibonacci-series)
 
 ## Data Structures
 
@@ -1854,4 +1855,26 @@ private String multiplesOfThree(int[] a){
 
     return indices.substring(0, indices.length()-1);
 }
+```
+
+### Fibonacci series
+* The Fibonacci series is a series of numbers in which each number ( Fibonacci number ) is the sum of the two preceding numbers. The simplest is the series 1, 1, 2, 3, 5, 8, etc. // Write a recursive function to compute the nth number in the fibonacci series.
+
+```java
+int fibonacci(int n) {
+    int[] memoizationArray = new int[n+1];
+    Arrays.fill(memoizationArray, -1);
+    return fibonacci(n, memoizationArray);
+}
+
+int fibonacci(int n, int[] a) {
+    if (n <= 2) {
+        return 1;
+    } else if (a[n] != -1) {
+        return a[n]; // Return cached result.
+    } else {
+        a[n] = fibonacci(n-1, a) + fibonacci(n-2, a); // Cache result
+    }
+    return a[n];
+}
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -110,6 +110,7 @@
   * [String compression] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#string-compression)
   * [Two Sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#two-sum)
   * [Sudoku Board Validator] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#sudoku-board-validator)
+  * [Multiples of 3] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#multiples-of-3)
 
 ## Data Structures
 
@@ -1833,4 +1834,24 @@ private boolean isRegionValid(int[][] board, int rowStartIndex, int rowEndIndex,
 
     return true;
 }
+```
+
+### Multiples of 3
+* Given an int array, write a function that prints out the indices where the value at that index is a mulitple of 3. So for example if the int [] a = { 1, 2, 3, 5, 7, 8, 11, 12, 14, 15, 17} , then the output should be all on one line (no newlines) : 2, 7, 9
+
+```java
+private String multiplesOfThree(int[] a){
+    String indices = "";
+    for(int i=0; i<a.length; i++){
+        if(a[i] % 3 == 0){
+            if(i == a.length){
+                indices += i+"";
+            } else {
+                indices += i+",";
+            }
+        }
+    }
+
+    return indices.substring(0, indices.length()-1);
+}
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -109,6 +109,7 @@
  * [Longest common subsequence] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#longest-common-subsequence)
   * [String compression] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#string-compression)
   * [Two Sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#two-sum)
+  * [Sudoku Board Validator] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#sudoku-board-validator)
 
 ## Data Structures
 
@@ -1733,4 +1734,103 @@ public void twoSum(int[] array, int sum){
         }
     }
 }
+```
+
+### Sudoku Board Validator
+* Given a sudoku board as a two-dimensional int array, write a method to validate if the board is valid.
+
+```java
+public static int BOARD_DIMENSION = 9;
+
+public boolean isSudokuBoardValid(int[][] board){
+
+    // check rows
+    for(int i=0; i<BOARD_DIMENSION; i++){
+        if(!isRowValid(board, i)){
+            return false;
+        }
+    }
+
+    // check columns
+    for(int j=0; j<BOARD_DIMENSION; j++){
+        if(!isColumnValid(board, j)){
+            return false;
+        }
+    }
+
+    // check sections
+    int i=0;
+    int j=0;
+    for( ; i<BOARD_DIMENSION; ){
+        for( ; j<BOARD_DIMENSION; ){
+            if(!isRegionValid(board, i, i + 2, j, j + 2)){
+                return false;
+            }
+
+            j+=3;
+        }
+        i+=3;
+    }
+
+    return true;
+}
+
+private boolean isRowValid(int[][] board, int row){
+    Set<Integer> uniqueNumbers = new HashSet<>();
+
+    for(int i=0; i<BOARD_DIMENSION; i++){
+        int value = board[row][i];
+        if(value<1 || value>9){
+            return false;
+        }
+
+        if(uniqueNumbers.contains(i)){ // found duplicate
+            return false;
+        } else {
+            uniqueNumbers.add(i);
+        }
+    }
+
+    return true;
+}
+
+private boolean isColumnValid(int[][] board, int column){
+    Set<Integer> uniqueNumbers = new HashSet<>();
+
+    for(int i=0; i<BOARD_DIMENSION; i++){
+        int value = board[i][column];
+        if(value<1 || value>9){
+            return false;
+        }
+
+        if(uniqueNumbers.contains(value)){ // found duplicate
+            return false;
+        } else {
+            uniqueNumbers.add(value);
+        }
+    }
+
+    return true;
+}
+
+private boolean isRegionValid(int[][] board, int rowStartIndex, int rowEndIndex, int columnStartIndex, int columnEndIndex){
+    Set<Integer> uniqueNumbers = new HashSet<>();
+
+    for(int i=rowStartIndex; i <rowEndIndex; i++){
+        for(int j=columnStartIndex; j<columnEndIndex; j++){
+            int value = board[i][j];
+            if(value<1 || value>9){
+                return false;
+            }
+
+            if(uniqueNumbers.contains(value)){ // found duplicate
+                return false;
+            } else {
+                uniqueNumbers.add(value);
+            }
+        }
+    }
+
+    return true;
+}
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -108,6 +108,7 @@
  * [Most frequent K words in a document] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#most-frequent-k-words-in-a-document)
  * [Longest common subsequence] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#longest-common-subsequence)
   * [String compression] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#string-compression)
+  * [Two Sum] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#two-sum)
 
 ## Data Structures
 
@@ -1712,3 +1713,24 @@ public String stringCompression(String uncompressedString){
 }
 ```
 
+### Two Sum
+* You have an unsorted array, and you are given a value S. Print all pairs of elements in the array that add up to value S. 
+
+```java
+public void twoSum(int[] array, int sum){
+    Map<Integer, Integer> map = new HashMap<>();
+
+    for(int i=0; i<array.length; i++){
+        map.put(array[i], i);
+    }
+
+    for(int i=0; i<array.length; i++){
+
+        int b = sum - array[i];
+
+        if(map.containsKey(b) && i!=map.get(b) && i < map.get(b)){
+            System.out.println(String.format("twoSum() : Indices %d and %d add up to the target %d", i, map.get(b), sum));
+        }
+    }
+}
+```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1678,7 +1678,7 @@ private String maxSequence(String firstSequence, String secondSequence){
 ```
 
 ### String compression
-* Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the orig- inal string, your method should return the original string.
+* Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.
 
 ```java
 public String stringCompression(String uncompressedString){

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -107,6 +107,7 @@
 * [Questions] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#questions)
  * [Most frequent K words in a document] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#most-frequent-k-words-in-a-document)
  * [Longest common subsequence] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#longest-common-subsequence)
+  * [String compression] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#string-compression)
 
 ## Data Structures
 
@@ -1674,4 +1675,40 @@ private String maxSequence(String firstSequence, String secondSequence){
         return secondSequence;
     }
 }    
-```
+```
+
+### String compression
+* Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the orig- inal string, your method should return the original string.
+
+```java
+public String stringCompression(String uncompressedString){
+    String compressedString = "";
+    if(TextUtils.isEmpty(uncompressedString))
+        return "";
+
+    int repeatedFreqCount = 0;
+    for(int i=0; i<uncompressedString.length(); i++){
+        if(i == 0){
+            repeatedFreqCount++;
+        } else {
+            if(uncompressedString.charAt(i) == uncompressedString.charAt(i-1)){
+                repeatedFreqCount++;
+            } else {
+                compressedString += uncompressedString.charAt(i-1)+""+repeatedFreqCount;
+                repeatedFreqCount = 1;
+            }
+
+            if(i == uncompressedString.length()-1){
+                compressedString += uncompressedString.charAt(i)+""+repeatedFreqCount;
+            }
+        }
+    }
+
+    if(compressedString.length() < uncompressedString.length()){
+        return compressedString;
+    } else {
+        return uncompressedString;
+    }
+}
+```
+
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -106,6 +106,7 @@
  * [Multidex] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#multidex)
 * [Questions] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#questions)
  * [Most frequent K words in a document] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#most-frequent-k-words-in-a-document)
+ * [Longest common subsequence] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#longest-common-subsequence)
 
 ## Data Structures
 
@@ -1649,4 +1650,28 @@ private class Word{
     }
     // endregion
 }
+```
+
+### Longest common subsequence
+* Given two Strings, find the longest common subsequence?
+
+```java
+public String lcs(String a, String b){
+    if(TextUtils.isEmpty(a) || TextUtils.isEmpty(b))
+        return "";
+    else if(a.charAt(a.length()-1) == b.charAt(b.length()-1)){
+        return lcs(a.substring(0, a.length()-1), b.substring(0, b.length()-1)) + a.substring(a.length()-1);
+    } else {
+        return maxSequence(lcs(a.substring(0, a.length()-1), b.substring(0, b.length())),
+                lcs(a.substring(0, a.length()), b.substring(0, b.length()-1)) );
+    }
+}
+
+private String maxSequence(String firstSequence, String secondSequence){
+    if(firstSequence.length() > secondSequence.length()){
+        return firstSequence;
+    } else {
+        return secondSequence;
+    }
+}    
 ```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -104,7 +104,8 @@
  * [Android Build Process] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#android-build-process)
  * [Proguard] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#proguard)
  * [Multidex] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#multidex)
-
+* [Questions] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#questions)
+ * [Most frequent K words in a document] (https://gist.github.com/lawloretienne/6f7d7d92f72986f5ebd60f226d9044ee#most-frequent-k-words-in-a-document)
 
 ## Data Structures
 
@@ -1561,4 +1562,91 @@ WeakReference weakWidget = new WeakReference(widget);
 ### Multidex
 * Android application (APK) files contain executable bytecode files in the form of Dalvik Executable (DEX) files, which contain the compiled code used to run your app. 
 * The Dalvik Executable specification limits the total number of methods that can be referenced within a single DEX file to 65,536, including Android framework methods, library methods, and methods in your own code. 
-* Getting past this limit requires that you configure your app build process to generate more than one DEX file, known as a multidex configuration.
+* Getting past this limit requires that you configure your app build process to generate more than one DEX file, known as a multidex configuration.
+
+## Questions
+
+### Most frequent K words in a document
+* Given a word document as a String, find the K most frequent words in the document?
+
+```java
+private List<String> getMostFrequentWords(String document, int numOfWords){
+    List<String> mostFrequentWords = new ArrayList<>();
+
+    if(numOfWords<=0 || TextUtils.isEmpty(document)){
+        return mostFrequentWords;
+    }
+
+    String[] tokens = document.split("\\s*[^a-zA-Z']*?\\s+");
+
+    Map<String, Integer> wordFrequencies = new HashMap<>();
+    for(String token : tokens){
+        if(wordFrequencies.containsKey(token))
+            wordFrequencies.put(token, wordFrequencies.get(token) + 1);
+        else
+            wordFrequencies.put(token, 1);
+    }
+
+    PriorityQueue maxHeap = new PriorityQueue(wordFrequencies.size(), new Comparator<Object>() {
+        @Override
+        public int compare(Object lhs, Object rhs) {
+            int freq1 = ((Word)lhs).getFrequency();
+            int freq2 = ((Word)rhs).getFrequency();
+            if(freq1 < freq2){
+                return 1;
+            } else if(freq1 > freq2){
+                return -1;
+            } else {
+                return 0;
+            }
+        }
+    });
+
+    for ( String key : wordFrequencies.keySet() ) {
+        Word word = new Word(key, wordFrequencies.get(key));
+        maxHeap.add(word);
+    }
+
+    for(int i=0; maxHeap.size()>0 && i<numOfWords; i++){
+        Word word = (Word) maxHeap.poll();
+        mostFrequentWords.add(word.getText());
+    }
+
+    return mostFrequentWords;
+}
+
+private class Word{
+
+    // region Member Variables
+    private String text;
+    private int frequency;
+    // endregion
+
+    // region Constructors
+    public Word(String text, int frequency){
+        this.text = text;
+        this.frequency = frequency;
+    }
+    // endregion
+
+    // region Getters
+    public int getFrequency() {
+        return this.frequency;
+    }
+
+    public String getText() {
+        return this.text;
+    }
+    // endregion
+
+    // region Setters
+    public void setText(String text) {
+        this.text = text;
+    }
+
+    public void setFrequency(int frequency) {
+        this.frequency = frequency;
+    }
+    // endregion
+}
+```
diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1367,7 +1367,7 @@ WeakReference weakWidget = new WeakReference(widget);
 * An iterator over a collection.
 * The Iterator interface allows us to remove an element while traversing the Collection object. 
 * Iterator has remove() method which is not there in the Enumeration interface.
-* Iterator should be preferred over Enumeration, as "Iterator takes the place of Enumeration in the Java collections framework 
+* Iterator should be preferred over Enumeration, as Iterator takes the place of Enumeration in the Java collections framework. 
 
 ## Android
 

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1356,7 +1356,7 @@ WeakReference weakWidget = new WeakReference(widget);
 
 ### Unboxing
 * Converting an object of a wrapper type (Integer) to its corresponding primitive (int) value is called unboxing. 
-The Java compiler applies unboxing when an object of a wrapper class is passed as a parameter to a method that expects a value of the corresponding primitive type or assigned to a variable of the corresponding primitive type.
+* The Java compiler applies unboxing when an object of a wrapper class is passed as a parameter to a method that expects a value of the corresponding primitive type or assigned to a variable of the corresponding primitive type.
 
 ### Enumeration
 * Enumeration only traverses the Collection object. You can’t do any modifications to Collection while traversing the Collection using Enumeration.

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1335,7 +1335,8 @@ public class DataArtist {
 * A Strong reference is a normal reference that protects the referred object from collection by a garbage collector.
 
 ### Soft Reference
-* A Soft reference is a reference whose object is eligible for collection by a garbage collector until memory is not available.
+* Soft reference objects are cleared at the discretion of the garbage collector in response to memory demand. 
+* Soft references are most often used to implement memory-sensitive caches.
 * A soft reference is exactly like a weak reference, except that it is less eager to throw away the object to which it refers.
 * An object which is softly reachable will generally stick around for a while.
 

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1333,16 +1333,17 @@ public class DataArtist {
 
 ### Strong Reference
 * A Strong reference is a normal reference that protects the referred object from collection by a garbage collector.
-* A soft reference is exactly like a weak reference, except that it is less eager to throw away the object to which it refers. 
-* An object which is only weakly reachable (the strongest references to it are WeakReferences) will be discarded at the next garbage collection cycle, but an object which is softly reachable will generally stick around for a while.
 
 ### Soft Reference
 * A Soft reference is a reference whose object is eligible for collection by a garbage collector until memory is not available.
+* A soft reference is exactly like a weak reference, except that it is less eager to throw away the object to which it refers.
+* An object which is softly reachable will generally stick around for a while.
 
 ### Weak Reference
 * A Weak reference is a reference that does not protect the referenced object from collection by a garbage collector.
 * A weak reference is a reference that isn't strong enough to force an object to remain in memory. 
 * Weak references allow you to leverage the garbage collector's ability to determine reachability for you, so you don't have to do it yourself.
+* An object which is only weakly reachable (the strongest references to it are WeakReferences) will be discarded at the next garbage collection cycle.
 
 ```java
 WeakReference weakWidget = new WeakReference(widget);

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -981,7 +981,7 @@ Inside Square::draw() method.
 * A heap is a kind of a global memory pool. 
 * A function can allocate memory on the heap if it wants the data to live longer than the function itself. 
 * Objects allocated on the heap are accessible to all the functions, given they have the reference/address of the object to access it.
-* Java Heap space is used by java runtime to allocate memory to Objects and JRE classes. 
+* Java Heap space is used by Java runtime to allocate memory to Objects and JRE classes. 
 * Whenever we create any object, it’s always created in the Heap space. 
 * Garbage Collection runs on the heap memory to free the memory used by objects that don't have any reference. 
 * Any object created in the heap space has global access and can be referenced from anywhere in the application.
@@ -1199,7 +1199,7 @@ class Shapes{
 * A Java interface cannot contain an implementation of the methods, only the signature (name, parameters and exceptions) of the method. 
 * You can use interfaces in Java as a way to achieve polymorphism.
 * Interfaces cannot be instantiated—they can only be implemented by classes or extended by other interfaces.
-* An interface in java is a blueprint of a class. 
+* An interface in Java is a blueprint of a class. 
 * It has static constants and abstract methods only.
 * Interfaces can be used to achieve loose coupling.
 * Interface fields are public, static and final by default, and methods are public and abstract.

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1127,7 +1127,7 @@ waiting on another resource in the chain.
 * It is also called "information hiding".
 * An object has to provide its users only with the essential information for manipulation, without the internal details.
 * Encapsulation is wrapping, just hiding properties and methods. 
-* Encapsulation is used for hide the code and data in a single unit to protect the data from the outside the world.
+* Encapsulation means hiding the code and data in a single unit to protect the data from the outside the world.
 * Encapsulation is hiding the implementation details which may or may not be for generic or specialized behavior(s).
 
 ### Abstraction

diff --git a/Interview Topics.md b/Interview Topics.md
@@ -1378,7 +1378,7 @@ The Java compiler applies unboxing when an object of a wrapper class is passed a
 ### Fragment
 * Fragment class helps to better modularize code, build more sophisticated user interfaces for larger screens, and help scale their application between small and large screens.
 * A Fragment is a piece of an application's user interface or behavior that can be placed in an Activity.
-* Though Fragment defines its own lifecycle, that lifecycle is dependent on its'0000 activity: if the activity is stopped, no fragments inside of it can be started; when the activity is destroyed, all fragments will be destroyed.
+* Though Fragment defines its own lifecycle, that lifecycle is dependent on its activity: if the activity is stopped, no fragments inside of it can be started; when the activity is destroyed, all fragments will be destroyed.
 
 ### Service
 * An application component representing either an application's desire to perform a longer-running operation while not interacting with the user or to supply functionality for other applications to use.