http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/
The following are top 10 algorithms related topics for coding interviews. As understanding those concepts requires much more effort, this list below only serves as an introduction. They are viewed from a Java perspective and the following topics will be covered: String/Array/Matrix, Linked List, Tree, Heap, Graph, Sorting, Recursion vs. Iteration, Dynamic Programming, Bit Manipulation, Probability, Combinations and Permutations, and other problems that need us to find patterns.
1. String/Array/Matrix
First of all, String in Java 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.
Strings/arrays are easy to understand, but questions related to them often require advanced algorithm to solve, such as dynamic programming, recursion, etc.
Classic problems:
1) Evaluate Reverse Polish Notation
2) Longest Palindromic Substring
3) Word Break
4) Word Ladder
5) Median of Two Sorted Arrays
6) Regular Expression Matching
7) Merge Intervals
8) Insert Interval
9) Two Sum
9) 3Sum
9) 4Sum
10) 3Sum Closest
11) String to Integer
12) Merge Sorted Array
13) Valid Parentheses
14) Implement strStr()
15) Set Matrix Zeroes
16) Search Insert Position
17) Longest Consecutive Sequence
18) Valid Palindrome
19) Spiral Matrix
20) Search a 2D Matrix
21) Rotate Image
22) Triangle
23) Distinct Subsequences Total
24) Maximum Subarray
25) Remove Duplicates from Sorted Array
26) Remove Duplicates from Sorted Array II
27) Longest Substring Without Repeating Characters
28) Longest Substring that contains 2 unique characters
29) Palindrome Partitioning
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.
Two popular applications of linked list are stack and queue.
Stack
Queue
It is worth to mention that Java standard library already contains a class called “Stack“, and LinkedListcan be used as a Queue (add() and remove()). (LinkedList implements the Queue interface) If you need a stack or queue to solve problems during your interview, you can directly use them.
Classic Problems:
1) Add Two Numbers
2) Reorder List
3) Linked List Cycle
4) Copy List with Random Pointer
5) Merge Two Sorted Lists
6) Merge k Sorted Lists *
7) Remove Duplicates from Sorted List
8) Partition List
9) LRU Cache
3. Tree & Heap
Tree here is normally binary tree. Each node contains a left node and right node like the following:
Here are some concepts related with trees:
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.
Classic problems:
1) Binary Tree Preorder Traversal
2) Binary Tree Inorder Traversal
3) Binary Tree Postorder Traversal
4) Word Ladder
5) Validate Binary Search Tree
6) Flatten Binary Tree to Linked List
7) Path Sum
8) Construct Binary Tree from Inorder and Postorder Traversal
9) Convert Sorted Array to Binary Search Tree
10) Convert Sorted List to Binary Search Tree
11) Minimum Depth of Binary Tree
12) Binary Tree Maximum Path Sum *
13) Balanced Binary Tree
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.
1) Define a GraphNode
2) Define a Queue
3) Breath First Search uses a Queue
Output:
Classic Problems:
1) Clone Graph
5. Sorting
Time complexity of different sorting algorithms. You can go to wiki to see basic idea of them.
Algorithm | Average Time | Worst Time | Space |
Bubble sort | n^2 | n^2 | 1 |
Selection sort | n^2 | n^2 | 1 |
Insertion sort | n^2 | n^2 | |
Quick sort | n log(n) | n^2 | |
Merge sort | n 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.
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;
The time complexity of the recursive method is exponential to n. There are a lot of redundant computations.
It should be straightforward to convert the recursion to iteration.
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:
The problem of climbing steps perfectly fit those 4 properties. Therefore, it can be solve by using dynamic programming.
Classic problems:
1) Edit Distance
2) Longest Palindromic Substring
3) Word Break
4) Maximum Subarray
8. Bit Manipulation
Bit operators:
OR (|) | AND (&) | XOR (^) | Left Shift (<<) | Right Shift (>>) | Not (~) |
1|0=1 | 1&0=0 | 1^0=1 | 0010<<2=1000 | 1100>>2=0011 | ~1=0 |
Get bit i for a give number n. (i count from 0 and starts from right)
For example, get second bit of number 10.
Classic Problems:
1) Find Single Number
2) Maximum Binary Gap
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.
calculateProbability(50) = 0.97
10. 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?
Class Problems:
1) Permutations
2) Permutations II
3) Permutation Sequence
11. Others
Other problems need us to use observations to form rules to solve them.
Classic problems:
1) Reverse Integer
2) Palindrome Number
3) Pow(x,n)
4) Subsets
5) Subsets II
References/Recommended 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
6. Counting sort
7. LeetCode Online Judge
来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/591258/viewspace-1140259/，如需转载，请注明出处，否则将追究法律责任。