Skip to main content

Top 10 Algorithms for Coding Interview

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

The following are top 10 algorithms related concepts in coding interview. I will try to illustrate those concepts though some simple examples. As understanding those concepts requires much more effort, this list only serves as an introduction. They are viewed from a Java perspective and the following concepts will be covered:
  • String
  • Linked List
  • Tree
  • Graph
  • Sorting
  • Recursion vs. Iteration
  • Dynamic Programming
  • Bit Manipulation
  • Probability
  • Combinations and Permutations
  • Other problems that need us to find patterns
I will keep updating this list to add more classic problems and problems from Leetcode.
1. String
Unlike in C++, a String is not a char array in Java. It is a class that contains a char array and other fields and methods. Without code auto-completion of any IDE, the following methods should be remembered.
toCharArray() //get char array of a String
Arrays.sort()  //sort an array
Arrays.toString(char[] a) //convert to 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
* Questions related with strings/arrays often require advanced algorithm to solve.
2. 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;
  } 
 }
}
It is worth to mention that Java standard library already contains a class called “Stack“, and LinkedListcan be used as a Queue. (LinkedList implements the Queue interface) If you directly need a stack or queue to solve problems in your interview, you can directly use them.
3. Tree
Tree here is normally 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
4. 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
Classic Problems: Clone Graph
5. 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)
In addition, here are some implementations/demos: MergesortQuicksortInsertionSort.
6. Recursion vs. Iteration
Recursion should be a built-in thought for programmers. It can be demonstrated by a simple example.
Question: there are n stairs, each time one can climb 1 or 2. How many different ways to climb the stairs.
Step 1: Finding the relationship before n and n-1.
To get n, there are only two ways, one 1-stair from n-1 or 2-stairs from n-2. If f(n) is the number of ways to climb to n, then f(n) = f(n-1) + f(n-2)
Step 2: Make sure the start condition is correct.
f(0) = 0;
f(1) = 1;
public static int f(int n){
 if(n <= 2) return n;
 int x = f(n-1) + f(n-2);
 return x;
}
The time complexity of the recursive method is exponential to n. There are a lot of redundant computations.
f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(2) + f(2) + f(1)
It should be straightforward to convert the recursion to iteration.
public static int f(int n) {
 
 if (n <= 2){
  return n;
 }
 
 int first = 1, second = 2;
 int third = 0;
 
 for (int i = 3; i <= n; i++) {
  third = first + second;
  first = second;
  second = third;
 }
 
 return third;
}
For this example, iteration takes less time. You may also want to check out Recursion vs Iteration.
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;
Classic Problems: Find Single Number.
9. Probability
Solving probability related questions normally requires formatting the problem well. Here is just a simple example of such kind of problems.
There are 50 people in a room, what’s the probability that two people have the same birthday? (Ignoring the fact of leap year, i.e., 365 day every year)
Very often calculating probability of something can be converted to calculate the opposite. In this example, we can calculate the probability that all people have unique birthdays. That is: 365/365 * 364/365 * 363/365 * … * 365-n/365 * … * 365-49/365. And the probability that at least two people have the same birthday would be 1 – this value.
public static double caculateProbability(int n){
 double x = 1; 
 
 for(int i=0; i<n; i++){
  x *=  (365.0-i)/365.0;
 }
 
 double pro = Math.round((1-x) * 100);
 return pro/100;
}
calculateProbability(50) = 0.97
10. Combinations and Permutations
The difference between combination and permutation is whether order matters.
Please leave your comment if you think any other problem should be here.
11. Others
Other problems need us to use observations to form rules to solve them.
Classic problems: Reverse Integer
Revision History
12/06/2013 – Add “Add Two Numbers”, “Binary Tree Traversal(pre/in/post-order)”, “Find Single Number”.
12/07/2013 – Add “Word Break”
12/08/2013 – Add “Reorder List”
12/10/2013 – Add “Edit Distance”, ” Reverse Integer”
12/14/2013 – Add “Copy List with Random Pointer”, “Evaluate Reverse Polish Notation”, “Word Ladder”.
References/Recommmended Materials:
1. Binary tree
2. Introduction to Dynamic Programming
3. UTSA Dynamic Programming slides
4. Birthday paradox
5. Cracking the Coding Interview: 150 Programming InterviewQuestions and Solutions, Gayle Laakmann McDowell
5. Counting sort

Comments

Popular posts from this blog

Stretch a row if data overflows in jasper reports

It is very common that some columns of the report need to stretch to show all the content in that column. But  if you just specify the property " stretch with overflow' to that column(we called text field in jasper report world) , it will just stretch that column and won't change other columns, so the row could be ridiculous. Haven't find the solution from internet yet. So I just review the properties in iReport one by one and find two useful properties(the bold highlighted in example below) which resolve the problems.   example:
<band height="20" splitType="Stretch"> <textField isStretchWithOverflow="true" pattern="" isBlankWhenNull="true"> <reportElement stretchType="RelativeToTallestObject" mode="Opaque" x="192" y="0" width="183" height="20"/> <box leftPadding="2"> <pen lineWidth="0.25"/> …

JasperReports - Configuration Reference

Spring - Operations with jdbcTemplate

This class manages all the database communication and exception handling using a java.sql.Connection that is obtained from the provided DataSource. JdbcTemplate is a stateless and threadsafe class and you can safely instantiate a single instance to be used for each DAO.


Use of Callback Methods
JdbcTemplate is based on a template style of programming common to many other parts of Spring. Some method calls are handled entirely by the JdbcTemplate, while others require the calling class to provide callback methods that contain the implementation for parts of the JDBC workflow. This is another form of Inversion of Control. Your application code hands over the responsibility of managing the database access to the template class. The template class in turn calls back to your application code when it needs some detail processing filled in. These callback methods are allowed to throw a java.sql.SQLException, since the framework will be able to catch this exception and use its built-in excepti…