Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Code In JAVA:

Version 1:
    public int maxSubArray(int[] A) {
      int max = Integer.MIN_VALUE;
      int sum = 0;
      if (A.length == 0 || A == null) {
         return 0;
      }
      // if sum > 0, then keep on going, else < 0, then reset sum to 0
      for (int i = 0; i < A.length; i++) {
         sum += A[i];
         max = Math.max(max, sum);
         sum = Math.max(sum, 0);
      }
      return max;
   }

Remove Duplicates int Sorted Array (1 & 2)

Remove Duplicates from Sorted Array
For example:
Given input array A = [1,1,2];
Your function should return length = 2, and A is now [1,2].</ br>

Version 1:
public int removeDuplicates(int[] A) {
        if (A.length == 0 || A == null) {
            return 0;
        }
        int size = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != A[size]) {
                size++;
                A[size] = A[i];
            }
        }
        return size + 1;
        
}
Version 2:
public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int element = A[0];
        int index = 0;
        for (int i = 0; i < A.length; i++) {
            if (element != A[i]) {
                index++;
                A[index] = A[i];
                element = A[i];
            }
        }
        return index + 1;
        
}

What if duplicates are allowed at most twice?
For example:
Given sorted array A = [1,1,1,2,2,3];
Your function should return length = 5, and A is now [1,1,2,2,3].

Version 1:
public int removeDuplicates(int[] A) {
        if (A.length <= 2) {
            return A.length;
        }
        int prev = 1;
        int curr = 2;
        while (curr < A.length) {
            if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {
                curr++;
            } else {
                prev++;
                A[prev] = A[curr];
                curr++;
            }
        }
        return prev + 1;
        
}
Version 2:
public int removeDuplicates(int[] A) {
       if (A == null || A.length == 0) {
           return 0;
       }

       int size = 0;
       for (int i = 1; i < A.length; i++) {
           if (A[i] == A[size] && size > 0 && A[size - 1] == A[size]) {
               continue;
           }
           A[++size] = A[i];
       }
       return size + 1;
}

Remove Duplicates from Sorted List 1

Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Time complexity is O(n);

public class Remove_Duplicates_from_Sorted_List1 {
 public class ListNode{
  int val;
  ListNode next;
  ListNode(int x) {
   val = x;
   next = null;
  }
 }
 public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
         return null;
        }
        ListNode node = head;
        while (node.next != null) {
         if (node.val == node.next.val) {
          node.next = node.next.next;
         } else {
          node = node.next;
         }
        }
        return head;
    }
}

Find K-th Element in Two Sorted Arrays

Find K-th Element in Two Sorted Arrays

Solution 1:
Very straight thought:
1. merge two sorted array into new Array - C;
2. Get the kth element in C
I think the time complexity is O(n + m), where n is the length of array A, m is the length of Array B.

public class Find_kth_Element_in_Two_Sorted_Array {
 public int mergeGetKthNumber(int[] A, int[] B, int k) {
  int[] C = mergeTwoArrays(A, B);
  return C[k - 1];
 }
 
 public int[] mergeTwoArrays(int[] A, int[] B) {
  int[] C = new int[A.length + B.length];
  int i = 0, j = 0, k = 0;
  while (i < A.length && j < B.length) {
   if (A[i] <= B[j]) {
    C[k] = A[i];
    i++;
   } else {
    C[k] = B[j];
    j++;
   }
   k++;
  }
  while (i < A.length) {
   C[k] = A[i];
   i++;
   k++;
  }
  while (j < B.length) {
   C[k] = B[j];
   j++;
   k++;
  }
  return C;
 }
}

Solution 2
Compare the two arrays elements one by one;
if A[i] <= B[j], i++;
if A[i] > B[j], j++;
if A or B has no element left, then go through (k - i - j) elements in left Array.
I think the time complexity is also O(n + m), same as above.
Solution 3:
Use the binary search, there is something wrong with the code now......

Find Longest Chain of Consecutive Integers in Arrays

Find the length of the longest chain of consecutive integers in an unsorted map in linear time
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Solution 1: 
The key factors about a cluster is: lowest, highest, and length.
Map lowest and highest to length.
To merge two neighbor clusters, only need to update it's new lowest and highest, with new length.
For every a[i], checking its neighbor a[i]-1 and a[i]+1 is enough.

public class Find_Longest_Consecutive_Integer_in_Array {
 public int findLonestConsequence(int[] array) {
  HashMap map = new HashMap();
  int max = 1;
  for (int num: array) {
   if (map.containsKey(num)) {
    continue;
   }
   map.put(num, 1);
   
   if (map.containsKey(num - 1)) {
    max = Math.max(max, merge(map, num - 1, num));
   }
   if (map.containsKey(num + 1)) {
    max = Math.max(max, merge(map, num, num + 1));
   }
  }
  return max;
 }
 
 public int merge(HashMap map, int left, int right) {
  int upper = right + map.get(right) - 1;
  int lower = left - (map.get(left) - 1);
  int len = upper - lower + 1;
  map.put(upper, len);
  map.put(lower, len);
  return len;
 }
}

Solution 2: 
We can use a HashSet to add and remove elements. HashSet is implemented by using a hash table. Elements are not ordered.
The add, remove and contains methods have constant time complexity O(1).
Time complexity is O(n*(m1+m2)), m is the average length of all consecutive sequences.

public class Find_Longest_Consecutive_Integer_in_Array {
 public int findLonestConsequence(int[] num) {
  Set set = new HashSet();
  int max = 1;
  for (int n : num) {
   set.add(n);
  }
  for (int n : num) {
   int left = n - 1;
   int right = n + 1;
   int count = 1;
   while (set.contains(left)) {
    count++;
    /* After the element is checked, it should be 
     *  removed from the set
     */
    set.remove(left);
    left--;
   }
   while (set.contains(right)) {
    count++;
    set.remove(right);
    right++;
   }
   max = Math.max(count, max);
  }
  return max;
 }
}

Same Binary Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

public class Same_Binary_Tree {
 public class TreeNode{
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) {
   val = x;
  }
 }
 public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
         return true;
        } else if (p != null && q != null) {
         if (p.val == q.val) {
          return isSameTree(p.left, q.left) &&
            isSameTree(p.right, q.right);
         }
        } else {
         return false;
        }
        return false;
        
    }
}

Valid String Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome. Solution 1:

public class Valid_Palindrome {
    public boolean isPalindrome(String s) {
        if (s == null) {return false;}
        if (s.length() < 2) {return true;}
        char[] charArray = s.toCharArray();
        int len = s.length();
        
        int i = 0, j = len - 1;
        while (i < j) {
            char left = charArray[i];
            char right = charArray[j];
            while (i < len - 1 && !isAlpha(left) && !isNum(left)) {
                i++;
                left = charArray[i];
            }
            while (j > 0 && !isAlpha(right) && !isNum(right)) {
                j--;
                right = charArray[j];
            }
            if (i >= j) {
                break;
            }
            left = charArray[i];
            right = charArray[j];
            if (!isSame(left, right)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    public boolean isAlpha(char c) {
        if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
            return true;
        } else {
            return false;
        }
    }
    public boolean isNum(char c) {
        if (c >= '0' && c <= '9') {
            return true;
        } else {
            return false;
        }
    }
 
    public boolean isSame(char a, char b) {
        if (isNum(a) && isNum(b)) {
            return a== b;
        } else if (String.valueOf(a).equalsIgnoreCase(String.valueOf(b))) {
            return true;
        } else {
            return false;
        }
    }
 
}

Solution 2:

public class Valid_Palindrome {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
 }
 int front = 0;
 int end = s.length() - 1;
 while (front < end) {
  while (front < s.length() && !isValid(s.charAt(front))) {
   front++;
  }
  // for empty string
  if (front == s.length()) {
   return true;
  }
  while (end >= 0 && !isValid(s.charAt(end))) {
   end--;
  }
  // compare char
  if (Character.toLowerCase(s.charAt(front)) != Character.toLowerCase(s.charAt(end))) {
   break;
  } else {
   front++;
   end--;
  }
 }
 return end <= front;
    }
 
    private boolean isValid(char c) {
 return Character.isLetter(c) || Character.isDigit(c);
    }
        
}

Insertion Sort List

Insertion Sort List Sort a linked list using insertion sort.

public class Insertion_Sort_List {
 public class ListNode{
  int val;
  ListNode next;
  ListNode(int x) {
   val = x;
   next = null;
  }
 }
 public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        while (head != null) {
         ListNode node = dummy;
         while (node.next != null && node.next.val < head.val) {
          node = node.next;
         }
         ListNode temp = head.next;
         head.next = node.next;
         node.next = head;
         head = temp;
        }
        return dummy.next;
        
    }
}

Vectors, Lists, and Sequences

List:

such a list is useful for maintaining logs of frequently visited Web pages, which is the example we illustrate, as well as most viewed photographs or commonly used menu items in a graphical user interface.

Text Processing (notes)

String Operation

String class to represent immutable strings, which cannot be modified, and StringBuffer class to represent mutable strings, which can be modified.

StringBuffer:  sppend(Q):   insert(i, Q);   reverse();   charAt(i);

Pattern Matching Algorithms

1. Brute Force

The brute force algorithmic design pattern is a powerful techniques for algorithm design when we have something we wish to search for or when we wish to optimize some function. In applying this technique in a general situation we typically enumerate all possible configurations of the inputs involved and pick the best of all these enumerated configurations.

2. The Knuth-Morris-Pratt Algorithm

 

 

Comparison of Sorting Algorithms (notes)

1. Selection-Sort:

Certainly, the selection-sort algorithm is a poor choice in any application, since it runs in O(n^2) time even in the best-case.

2. Insertion-Sort

If implemented well, the running time of insertion-sort is O(n+m), where m is the number if inversions (the number of pairs of elements out of order). Thus, insertion-sort is an excellent algorithm for sorting small sequences (say, less than 50 elements), because small sequences necessarily have few inversions.

And also, insertion-sort is quite effective for sorting sequences that are already "almost" sorted.

But the O(n^2)-time performance of insertions-sort makes it a poor choice outside of these special contexts.

3. Merge-Sort

Merge-sort, on the other hand, runs in O(nlogn) time in the worst-case, which is optimal for comparison-based sorting methods.

Merge-sort is an excellent algorithms for situations where the input cannot all ft into main memory, but must be stored in blocks on an external memory device, such as disk. Thus, for external memory sorting, the merge-sort algorithm tends to minimize the total number of disk reads and writes needed, which makes the merge-sort algorithm superior in such context.

Java uses merge-sort for Object arrays and quick-sort for primitive arrays.

4. Quick-Sort

Experimental studies have shown that id an input sequence can fit entirely in main memory, then the in-place versions of quick-sort and heap-sort run faster than merge-sort.

Still, its O(n^2) time worst-case performance makes quick-sort a poor choice in real-time applications where we must guarantee on the time needed to complete a sorting operation.

5. Heap-Sort

In real-time scenarios where we have a fixed amount of time to perform a sorting operation and the input data can fit into main memory, the heap-sort algorithm is probably the best choice. It runs in O(nlogn) worst-case time and can easily be made to execute in-place.

6. Bucket-Sort and Radix-Sort

Finally, if our application involves sorting entries with small integer keys or d-tuples of small integer keys, then bucket-sort and radix-sort is an excellent choice, for it run in O(d(n+N)) time, where [0, N+1] is the range of integer keys (and d=1 for bucket sort). Thus, if d(n + N) is significantly "below" the nlogn function, then this sorting method should run faster than even quick-sort or heap-sort.

Sorting, Sets and Selection (notes)

Merge-Sort and Quick-Sort are based on recursion in and algorithmic design pattern called divide-and-conquer, and O(nlogn) time bound is the best possible for a comparison-based sorting algorithm.

Divide-and-Conquer:

1. Divide: if the input size is smaller than a certain threshold (say, one or two elements), solve the problem directly using a straightforward method and return the solution so obtained. Otherwise, devide the input data into two or more disjoint subsets.

2. Recur: Recursively solve the sub-problems associated with the subsets.

3. Conquer: Take the solutions to the sub-problems and "merge" them into a solution to the original problem.

Merge Two Sorted Arrays:

Merge-Sort

Runtime: Average and Worst-case: O(nlogn), Memory: depends

Quick-Sort

Runtime: Average: O(nlogn)l worst-case: O(n^2); Memory: O(logn)

1. Divide: x -> pivot, sort S

(1) L: Sorting the elements in S less than x;

(2) E: Sorting the elements in S equal to x;

(3) G: Sorting the elements in S greater than x.

2. Recur: Recursively sort sequence L and G

3. Conquer: Put back the elements into S in order by first inserting the elements of L, then those of E, and finally those of G.



Bucket-Sort

Radix-Sort

The radix-sort algorithm sorts a sequence of S of entries with keys that are pares, by applying a table bucket-sort on the sequence twice: first sort using the second component and then using the first component.

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

public class Longest_common_prefix {
 public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
         return "";
        }

        int len = findShortestStr(strs);
        String result = "";
        boolean flag = true;
        for (int i = 0; i < len; i++) {
         char tmp = strs[0].charAt(i);
         result += tmp;
         for (String word: strs) {
          if (word.charAt(i) != tmp) {
           result = result.substring(0, i);
           flag = false;
           return result;
          }
         }
        }
        if (flag) {
         return result;
        }
        return "";
        
    }
 
 public int findShortestStr(String[] strs) {
  int len = strs[0].length();
  for (int i = 0; i < strs.length; i++) {
   if (strs[i].length() < len) {
    len = strs[i].length();
   }
  }
  return len;
 }
 
}

Dynamic Programming - Find words in Dictionary

Given an input string and a dictionary of words, find out if the input string
can be segmented into a space-separated sequence of dictionary words. See following examples for more details.
This is a famous Google interview question, also being asked by many other companies.

Examaple:

Consider the following dictionary
{ i, like, sam, sung, samsung, mobile, ice,
cream, icecream, man, go, mango}

Input:  ilike
Output: Yes
The string can be segmented as "i like".

Input:  ilikesamsung
Output: Yes
The string can be segmented as "i like samsung" or "i like sam sung".

Codes in java:

public class Find_words_in_dictionary {

    //compare with dictionary by word
     public boolean dictionaryContains(String word) {
  
         String[] dict = {"mobile", "samsung", "sam", "sung", "man", "mango",
                          "icecream", "and", "go", "i", "like", "ice", "cream"};
         int size = dict.length;
         for (int i = 0; i < size; i++) {
             if (dict[i].compareTo(word) == 0) {
             return true;
             }
         }
         return false;
     }

     // Break the str into words
     @SuppressWarnings("unchecked")
     public boolean breakWords(String str) {
         if (str == null || str.length() == 0) {
             return true;
         }
         boolean wb[] = new boolean[str.length()];
         @SuppressWarnings("rawtypes")
         // compare str[0, i) and str[i, j)
         HashMap map = new HashMap();

         for (int i = 1; i < str.length(); i++) {
             if (wb[i - 1] == false && dictionaryContains(str.substring(0, i))) {
                 wb[i - 1] = true;
                 map.put(str.substring(0, i), 1);
                 System.out.println("aaaa " + str.substring(0, i));
             }
             for (int j = i; j <= str.length(); j++) {
                 if (wb[j - 1] == false && dictionaryContains(str.substring(i, j))) {
                     wb[j - 1] = true;
                     map.put(str.substring(i, j), 1);
                     System.out.println("bbbb " + str.substring(i, j));
                 }
             }
         }
        
        // check if wb[] contains false
        for (int i = 0; i < str.length(); i++) {
            if (wb[i]) {
                return true;
            }
        }
        return false;
  
 }
 
    public static void main(String[] args) {
        Find_words_in_dictionary f = new Find_words_in_dictionary();
        boolean flag = f.breakWords("likesamsungmancreamice");
        System.out.println(flag);
  
    }
}

The Output:

bbbb i
aaaa like
bbbb sam
bbbb samsung
bbbb man
bbbb cream
bbbb i
bbbb ice
true

Binary Search Tree (notes)

 Binary Search:

Worst-case: O(h). h = height of the tree; Best-case: O(1)

AVL Tree: (height balanced property)

Height- Balanced Property: For every internal node v of T, the heights of the children of  v differ at most 1.

Proposition: The height of an AVL tree sorting n entries is O(logn)



a way to achieve logarithmic time for the fundamental dictionary operations.

Slay Tree

Stack, Queues & Recursion

Stack

/*Runtime exception thrown when one tries to perform operation top or pop on an empty stack*/

Method         Time

size                 O(1)

isEmpty         O(1)

top                 O(1)

push               O(1)

pop                O(1)

Stacks in the Java Virtual Machine

A java program is typically compiled into a sequence of byte codes that are defined as "machine" instructions for a well-defined model - the JAVA VIRTUAL MACHINE (JVM).

The definition of JVM is at the heart of the definition of the java language itself.

By compiling java code into the JVM bytes codes, rather than the machine language of a specific CPU, a java program can be run on any computer, such as a personal computer or a server, that has a program that can evaluate the JVM.

Interestingly, the stacks data structure plays a central role in the definition of the JVM.

Frames: during the execution of a java program, the JVM maintains a stack whose elements are descriptors of the currently active invocations of methods. These descriptions are called frames.

Program Counter: The JVM keeps a spectial variables, called the program counter, to maintain the address of the statement the JVM id currently executing in the program.

Running Method: At the top of the java stack is the frame of the running method, that is, the method that currently has control of the execution.

Suspended Methods: The methods that have invoked another method and are currently waiting for it to return control to them upon its termination.

When a new method is invoked, a frame for this method is pushed onto the stack. When it terminates, its frames is popped from the stack and the JVM resumes the processing of the previously suspended method.

Methods for Manipulating Arrays (notes)

It will be much convenient for us to use Arrays methods to deal with some problems, and here I will summarize some Arrays (java.util.Arrays) knowledge.

1. The java.util.Arrays class offers the following method for representing int arrays as strings

(1) Method: toString(int[] a)

input:

int [] a = {1,3,5};
System.out.println( Arrays.toString(a) );

output: [[I@1c78e57, [I@5224ee]

(2) Method: deepToString(int[] a)

input:

int [][] a = {
{1,2},
{3,4}
};
System.out.println( Arrays.deepToString(a) );

output: [[1, 2], [3, 4]]



2. The java.util.Arrays class offers the following method for sorting int arrays in non-decreasing order.

(1) Method: sort(int[] a)

input:

int [] a = { 3, 1, 5 };
Arrays.sort( a );
System.out.println( Arrays.toString(a) );

output:[1, 3, 5]

(2) Method: binarySearch(int[] a, int key)

input:

int [] a = { 1, 2, 3, 4, 5 };
System.out.print( Arrays.binarySearch( a, 2 ) );
System.out.println( Arrays.binarySearch( a, 6 ) );

output: 1, -6

Some Notes for Algorithms

Time complexity - Omega of algorithms

a) if statement - O(n) [Omega times n]
b) for loop - O(n) [Omega times n]
c) for loop with a for loop - O(n*n) [Omega times n squared]
d) for loop within a if loop, this if loop is within a for loop - O(n + n*n) [n plus n squared omega]
e) while loop - O(n) [Omega times n]
f) MergeSort - O(nlogn) [Omega n time logarithmic n]
g) HeapSort - O(nlogn) [Omega n time logarithmic n]
h) KMP algorithm - O(m+n) [m plus n omega]

Checklist before selecting the right data structure for a given problem

(i) Analysis the problem in order to determine resource constraints
(ii) Determine the basic operations that need to be supported, such as Insert/Remove/Search
(iii) Now, select the data structure that has minimum cost/benefits to support the required operations

Operation time complexity for a LINKED LIST

The time complexity of handling the operations in a data structure like a LINKED LIST are as follows:

i. Most of the operations are O(n) [i.e. omega times n]
ii. Remove/Insert operations that handles element between elements require O(1) [i.e. omega times one] this is due to references/pointers on both the ends of the list, hence the elements don't require to be shifted. However, due to the references/pointers this data structure requires additional memory!

Operation time complexity for an ARRAY

The time complexity of handling the operations in a data structure like an ARRAY are as follows:

i. Almost all the operations are O(1) [i.e. omega times one]
ii. Remove/Insert operations that handles element between elements require O(n) [i.e. omega times n] because the elements need to be shifted.
Note! Hence, an array as a data structure is used where remove/insert operations are not required.

Binary tree traversal: Preorder, Inorder, and Postorder

We take this picture as an example to illustrate the binary tree traversal



First, Pre-order Traversal:
(1) Visit the root;
(2) Traverse the left subtree;
(3) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10
Code in java:

public void preOrder(Node root) {
    if (node == null) {
        return null;
    }
    System.out.println(root.data);
    preOrder(root.left);
    preOrder(root.right);
}

Second, In-Order Traversal:
(1) Traverse the left most subtree starting at the left external node;
(2) Visit the root;
(3) Traverse the right subtree starting at the left external node.
Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Code in java:

public void inOrder(Node root) {
    if (node == null) {
        return null;
    }
    inOrder(root.left);
    System.out.println(root.data);
    inOrder(root.right);
}

Third, Post-Order Traversal:
(1) Traverse all the left external nodes
(2) Traverse the right subtree starting at the end left external node from (1)
(3) Visit the root
Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
Code in java:

public void postOrder(Node root) {
    if (node == null) {
        return null;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.println(root.data);
}

Recursive Complexity - Fibonacci

The factorial - a simple recursive

N! = N * (N-1) * (N-2) * .....*2 * 1

This is a very simple recursive program:

int Factorial(int n){

if(n == 0){

return i;

}else{

return n * Factorial(n-1);

}

}

Not all Recursive method are very efficient, such as the recursive in Fibonacci:

Fibonacci: F(n) = F(n-1) + F(n-2), n > 1

       We can see that we have to calculate each F(n) for many times, for example, if we want to get F(5), we have to calculate F(3) for two times, and calculate the F(2) for three times.

So for some aspects, recursive is not always a good way, it depends on the problems you want to solve.

 

 

Find the next higher number which has the exact same set of digits as the original number

Given a number, find the next higher number which has the exact same set of digits as the original number.
For example: given 382765 return 385267

 

Anagrams

Write a program to sort an array of strings so that all anagrams are next to each other.

public class Anagrams {
	public List anagrams(String[] strs) {
		ArrayList result = new ArrayList();
		if (strs == null || strs.length == 0) {
		    return result;
		}
                HashMap> map = 
        		new HashMap>();
                for (String str: strs) {
        	    String newStr = sortChar(str);
        	    if (!map.containsKey(newStr)) {
        		map.put(newStr, new ArrayList());
        	    }
        	ArrayList anagrams = map.get(newStr);
        	anagrams.add(str);
                }
        
                for (String key: map.keySet()) {
        	    ArrayList anagrams = map.get(key);
        	    if (anagrams.size() > 1) {
        		    // or it will return [""], but expected []
        		    result.addAll(anagrams);
        	    }
        	
                }
                return result;
        
        }
	// Sort each str
	public String sortChar(String str) {
		char[] chr = str.toCharArray();
		java.util.Arrays.sort(chr);
		return new String(chr);
	}
	
}

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.


• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Code in JAVA:

public class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
       if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
           return false;
       }
       int m = matrix.length; 
       int n = matrix[0].length;
       int start = 0;
       int end = m * n - 1;

       while (start <= end) {
           int mid = (start + end) / 2;
           int midX = mid / n;
           int midY = mid % n;

           if (matrix[midX][midY] == target) {
               return true;
           }
           if (matrix[midX][midY] < target) {
               start = mid + 1;
           } else {
               end = mid - 1;
           }

       }
       return false;

    }
}

Find out if any two numbers that array add up to a target

write a function that finds out if any two numbers within that array add up to a target

Target: 17
array: 2, 23, 21, 3, 5, 7, 10, 12 ,8, 11
sort the array: 2, 3, 5, 7, 8, 10, 11, 12, 21, 23
index start and the end, calculate the sum;
if the sum < target, increment the start,  sum > target, decrement  the end;

public void findTarget(int[] array, int target) {
    int start = 0;
    int end = array.length - 1;
    //Complexity of sort -> O(nlogn)
    java.util.Arrays.sort(array);
    while (start < end) {
        if (array[start] + array[end] == target) {
            System.out.println(array[start] + array[end]);
            return;
        } else if (array[start] + array[end] < target) {
            start++;
        } else {
            end--;
        }
    }
}

Two Sum

Given an array of N distinct integers, write a program to find if there exists any pair of integers whose sum is x. This is popularly addressed as 2-SUM problem.

O(n^2) approach: Time complexity in worst case: O(n^2).

public static int[] twoSum(int[] numbers, int target) {
 int[] ret = new int[2];
 for (int i = 0; i < numbers.length; i++) {
  for (int j = i + 1; j < numbers.length; j++) {
   if (numbers[i] + numbers[j] == target) {
    ret[0] = i + 1;
    ret[1] = j + 1;
   }
  }
 }
 return ret;
}

HashMap version, Time complexity: O(n)

public int[] twoSum(int[] numbers, int target) {

        int a[] = new int[2];
        Hashtable<Integer, Integer> nums = new Hashtable<>();
        for(int i = 0;i < numbers.length;i++){
            Integer n = nums.get(numbers[i]);

            if (n==null) nums.put(numbers[i], i); //subtract array element from target number
            n = nums.get(target-numbers[i]); 
            if (n!=null && n<i)
            {//if such number exists in the table return the indicies
                a[0]=n+1;
                a[1]=i+1;
                return a;
            }
        }//end for loop
     return a;