전체 페이지뷰

2017년 5월 7일 일요일

top-10-algorithms-for-coding-interview

http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

Top 10 Algorithms for Coding Interview

 
The following are the common subjects in coding interviews. As understanding those concepts requires much more effort, this tutorial only serves as an introduction. The subjects that are covered include: 1) String/Array/Matrix, 2) Linked List, 3) Tree, 4) Heap, 5) Graph, 6) Sorting, 7) Dynamic Programming, 8) Bit Manipulation, 9) Combinations and Permutations, and 10) Math Problems. I highly recommend you to read "Simple Java" first, if you need a brief review of Java basics. If you want to see code examples that show how to use a popular API, you can use JavaSED.com.
1. String/Array
An algorithm problem's input is often a string or array. Without auto-completion of any IDE, the following methods should be remembered.
toCharArray() //get char array of a String
charAt(int x) //get a char at the specific index
length() //string length
length //array size 
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf()//string to integer
String.valueOf()/integer to string
Arrays.sort()  //sort an array
Arrays.toString(char[] a) //convert to string
Arrays.copyOf(T[] original, int newLength)
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
Classic problems:
--Two Pointers--
1) Rotate Array, Reverse Words in a String
2) Evaluate Reverse Polish Notation (Stack)
3) Isomorphic Strings
4) Word Ladder (BFS), Word Ladder II (BFS)
5) Median of Two Sorted Arrays
5) Kth Largest Element in an Array
6) Wildcard Matching, Regular Expression Matching
7) Merge Intervals, Insert Interval
9) Two Sum, Two Sum II, Two Sum III, 3Sum, 4Sum
10) 3Sum Closest
11) String to Integer
12) Merge Sorted Array
13) Valid Parentheses
13) Longest Valid Parentheses
14) Implement strStr()
15) Minimum Size Subarray Sum
16) Search Insert Position
17) Longest Consecutive Sequence
18) Valid Palindrome
19) ZigZag Conversion
20) Add Binary 
21) Length of Last Word
22) Triangle
24) Contains Duplicate: I, II, III
25) Remove Duplicates from Sorted Array: I, II, Remove Element , Move Zeroes
27) Longest Substring Without Repeating Characters
28) Longest Substring that contains 2 unique characters [Google]
28) Substring with Concatenation of All Words
29) Minimum Window Substring
31) Find Minimum in Rotated Sorted Array: I, II
32) Search in Rotated Array:I, II
33) Min Stack
34) Majority Element: I, II
35) Bulls and Cows 
36) Largest Rectangle in Histogram
37) Longest Common Prefix [Google]
38) Largest Number
39) Simplify Path
40) Compare Version Numbers
41) Gas Station
44) Pascal's Triangle: I, II
45) Container With Most Water
45) Candy [Google]
45) Trapping Rain Water
46) Count and Say
47) Search for a Range
48) Basic Calculator, Basic Calculator II
49) Group Anagrams
50) Shortest Palindrome
51) Rectangle Area
52) Summary Ranges
53) Increasing Triplet Subsequence
54) Get Target Using Number List And Arithmetic Operations 
55) Reverse Vowels of a String 
56) Flip Game, Flip Game II
57) Missing Number, Find the duplicate number, First Missing Positive 
58) Valid Anagram, Group Shifted Strings
59) Top K Frequent Elements
60) Find Peak Element
61) Word Pattern, Word Pattern II
62) H-Index , H-Index II
63) Palindrome Pairs
64) One Edit Distance
65) Scramble String
66) First Bad Version
67) Integer to English Words
68) Text Justification 
69) Remove Invalid Parentheses
70) Intersection of Two Arrays, Intersection of Two Arrays II
71) Sliding Window Maximum, Moving Average from Data Stream
72) Guess Number Higher or Lower
2. Matrix
Common methods to solve matrix related problem include DFS, BFS, dynamic programming, etc.
3. Linked List
The implementation of a linked list is pretty simple in Java. Each node has a value and a link to next node.
class Node {
 int val;
 Node next;
 
 Node(int x) {
  val = x;
  next = null;
 }
}
Two popular applications of linked list are stack and queue.
Stack
class Stack{
 Node top; 
 
 public Node peek(){
  if(top != null){
   return top;
  }
 
  return null;
 }
 
 public Node pop(){
  if(top == null){
   return null;
  }else{
   Node temp = new Node(top.val);
   top = top.next;
   return temp; 
  }
 }
 
 public void push(Node n){
  if(n != null){
   n.next = top;
   top = n;
  }
 }
}
Queue
class Queue{
 Node first, last;
 
 public void enqueue(Node n){
  if(first == null){
   first = n;
   last = first;
  }else{
   last.next = n;
   last = n;
  }
 }
 
 public Node dequeue(){
  if(first == null){
   return null;
  }else{
   Node temp = new Node(first.val);
   first = first.next;
   return temp;
  } 
 }
}
The Java standard library contains a class called "Stack". Another class from Java SDK is LinkedList, which can be used as a Queue (add() and remove()). (LinkedList implements the Queue interface.) If a stack or queue is required to solve problems during your interview, they are ready to be used.
4. Tree, Heap and Trie
A tree normally refers to a binary tree. Each node contains a left node and right node like the following:
class TreeNode{
 int value;
 TreeNode left;
 TreeNode right;
}
Here are some concepts related with trees:
  1. Binary Search Tree: for all nodes, left children <= current node <= right children
  2. Balanced vs. Unbalanced: In a balanced tree, the depth of the left and right subtrees of every node differ by 1 or less.
  3. Full Binary Tree: every node other than the leaves has two children.
  4. Perfect Binary Tree: a full binary tree in which all leaves are at the same depth or same level, and in which every parent has two children.
  5. Complete Binary Tree: a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible
Heap is a specialized tree-based data structure that satisfies the heap property. The time complexity of its operations are important (e.g., find-min, delete-min, insert, etc). In Java, PriorityQueue is important to know.
4.1 Tree
1) Binary Tree Traversal: Preorder, Inorder, Postorder, Level Order, Level Order II, Vertical Order
2) Invert Binary Tree
3) Kth Smallest Element in a BST
4) Binary Tree Longest Consecutive Sequence
5) Validate Binary Search Tree
6) Flatten Binary Tree to Linked List
7) Path Sum (DFS or BFS)
7) Path Sum II (DFS) 
8) Construct Binary Tree from Inorder and Postorder Traversal
8) Construct Binary Tree from Preorder and Inorder Traversal
9) Convert Sorted Array to Binary Search Tree [Google]
10) Convert Sorted List to Binary Search Tree [Google]
11) Minimum Depth of Binary Tree
12) Binary Tree Maximum Path Sum *
13) Balanced Binary Tree
14) Symmetric Tree
15) Binary Search Tree Iterator 
16) Binary Tree Right Side View
17) Lowest Common Ancestor of a Binary Search Tree
18) Lowest Common Ancestor of a Binary Tree
19) Verify Preorder Serialization of a Binary Tree
20) Populating Next Right Pointers in Each Node 
21) Populating Next Right Pointers in Each Node II 
21) Unique Binary Search Trees (DP)
21) Unique Binary Search Trees II (DFS)
22) Sum Root to Leaf Numbers (DFS)
23) Count Complete Tree Nodes 
24) Closest Binary Search Tree Value
25) Binary Tree Paths
26) Maximum Depth of Binary Tree
27 Recover Binary Search Tree
28) Same Tree
29) Serialize and Deserialize Binary Tree
30) Inorder Successor in BST
31) Find Leaves of Binary Tree
32) Largest BST Subtree
4.2 Heap
4.3 Trie
4.4 Segment Tree
5. Graph
Graph related questions mainly focus on depth first search and breath first search. Depth first search is straightforward, you can just loop through neighbors starting from the root node.
Below is a simple implementation of a graph and breath first search. The key is using a queue to store nodes.
breath-first-search
1) Define a GraphNode
class GraphNode{ 
 int val;
 GraphNode next;
 GraphNode[] neighbors;
 boolean visited;
 
 GraphNode(int x) {
  val = x;
 }
 
 GraphNode(int x, GraphNode[] n){
  val = x;
  neighbors = n;
 }
 
 public String toString(){
  return "value: "+ this.val; 
 }
}
2) Define a Queue
class Queue{
 GraphNode first, last;
 
 public void enqueue(GraphNode n){
  if(first == null){
   first = n;
   last = first;
  }else{
   last.next = n;
   last = n;
  }
 }
 
 public GraphNode dequeue(){
  if(first == null){
   return null;
  }else{
   GraphNode temp = new GraphNode(first.val, first.neighbors);
   first = first.next;
   return temp;
  } 
 }
}
3) Breath First Search uses a Queue
public class GraphTest {
 
 public static void main(String[] args) {
  GraphNode n1 = new GraphNode(1); 
  GraphNode n2 = new GraphNode(2); 
  GraphNode n3 = new GraphNode(3); 
  GraphNode n4 = new GraphNode(4); 
  GraphNode n5 = new GraphNode(5); 
 
  n1.neighbors = new GraphNode[]{n2,n3,n5};
  n2.neighbors = new GraphNode[]{n1,n4};
  n3.neighbors = new GraphNode[]{n1,n4,n5};
  n4.neighbors = new GraphNode[]{n2,n3,n5};
  n5.neighbors = new GraphNode[]{n1,n3,n4};
 
  breathFirstSearch(n1, 5);
 }
 
 public static void breathFirstSearch(GraphNode root, int x){
  if(root.val == x)
   System.out.println("find in root");
 
  Queue queue = new Queue();
  root.visited = true;
  queue.enqueue(root);
 
  while(queue.first != null){
   GraphNode c = (GraphNode) queue.dequeue();
   for(GraphNode n: c.neighbors){
 
    if(!n.visited){
     System.out.print(n + " ");
     n.visited = true;
     if(n.val == x)
      System.out.println("Find "+n);
     queue.enqueue(n);
    }
   }
  }
 }
}
Output:
value: 2 value: 3 value: 5 Find value: 5
value: 4
6. Sorting
Time complexity of different sorting algorithms. You can go to wiki to see basic idea of them.
AlgorithmAverage TimeWorst TimeSpace
Bubble sortn^2n^21
Selection sortn^2n^21
Insertion sortn^2n^2
Quick sortn log(n)n^2
Merge sortn log(n)n log(n)depends
* BinSort, Radix Sort and CountSort use different set of assumptions than the rest, and so they are not "general" sorting methods. (Thanks to Fidel for pointing this out)
Here are some implementations/demos, and in addition, you may want to check out how Java developers sort in practice.
1) Mergesort
2) Quicksort
3) InsertionSort.
4) Maximum Gap (Bucket Sort)
5) Sort Colors (Counting Sort)
7. Dynamic Programming
Dynamic programming is a technique for solving problems with the following properties:
  1. An instance is solved using the solutions for smaller instances.
  2. The solution for a smaller instance might be needed multiple times.
  3. The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
  4. Additional space is used to save time.

The problem of climbing steps perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming.
public static int[] A = new int[100];
 
public static int f3(int n) {
 if (n <= 2)
  A[n]= n;
 
 if(A[n] > 0)
  return A[n];
 else
  A[n] = f3(n-1) + f3(n-2);//store results so only calculate once!
 return A[n];
}
8. Bit Manipulation
Bit operators:
OR (|)AND (&)XOR (^)Left Shift (<<)Right Shift (>>)Not (~)
1|0=11&0=01^0=10010<<2=10001100>>2=0011~1=0
Get bit i for a give number n. (i count from 0 and starts from right)
public static boolean getBit(int num, int i){
 int result = num & (1<<i);
 
 if(result == 0){
  return false;
 }else{
  return true;
 }
}
For example, get second bit of number 10.
i=1, n=10
1<<1= 10 1010&10=10 10 is not 0, so return true;
9. Combinations and Permutations
The difference between combination and permutation is whether order matters.
Example 1:
Given 5 numbers - 1, 2, 3, 4 and 5, print out different sequence of the 5 numbers. 4 can not be the third one, 3 and 5 can not be adjacent. How many different combinations?
Example 2:
Given 5 banaba, 4 pear, and 3 apple, assuming one kind of fruit are the same, how many different combinations?
10. Math
Solving math problems usually require us to find regularities or repeated pattern from the observations. List the results for a small set of numbers first, if you do not have any ideas.
UPDATE: I decided to add more categories below.
11. HashMap
Additional Resources
1. Share your code to Github/BitBucket
작성자: 시간:
라벨:

댓글 3개:

  1. tachjava2018년 4월 3일 오전 5:58

    Great article. Links mentioned in your blog were very useful. Thanks for sharing.

    Cheers,
    http://www.flowerbrackets.com/how-to-implement-quick-sort-in-java-program/

    답글삭제
  2. tachjava2018년 4월 25일 오전 7:51

    Awesome!!! The algorithms mentioned in your article were very useful. Thanks for sharing.

    Cheers,
    http://www.flowerbrackets.com/pascal-triangle-in-java/

    답글삭제
  3. tachjava2018년 5월 4일 오전 6:57

    Nice explanation with appropriate links. Thanks for sharing.

    Cheers,
    http://www.flowerbrackets.com/palindrome-number-in-java/

    답글삭제

피드 구독하기: 댓글 (Atom)