英文版
以下从Java角度解释面试常见的算法和数据结构：字符串，链表，树，图，排序，递归 vs. 迭代，动态规划，位操作，概率问题，排列组合，以及一些需要寻找规律的题目。
1. 字符串和数组
字符串和数组是最常见的面试题目类型，应当分配最大的时间。关于字符串，首先需要注意的是和C++不同，Java字符串不是char数组。没有IDE代码自动补全功能，应该记住下面的这些常用的方法。
toCharArray() //获得字符串对应的char数组Arrays.sort() //数组排序Arrays.toString(char[] a) //数组转成字符串charAt(int x) //获得某个索引处的字符length() //字符串长度length //数组大小substring(int beginIndex) substring(int beginIndex, int endIndex)Integer.valueOf() //string to integerString.valueOf() /integer to string
字符串和数组本身很简单，但是相关的题目需要更复杂的算法来解决。比如说动态规划，搜索，等等。
经典题目：
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
30) Reverse Words in a String
31) Find Minimum in Rotated Sorted Array
32) Find Peak Element
33) Min Stack
34) Majority Element
35) Combination Sum (DFS)
36) Best Time to Buy and Sell Stock
36) Best Time to Buy and Sell Stock II
36) Best Time to Buy and Sell Stock III (DP)
2. 链表
在Java中，链表的实现非常简单，每个节点Node都有一个值val和指向下个节点的链接next。
class Node {int val;Node next;Node(int x) {val = x;next = null;}}
链表两个著名的应用是栈Stack和队列Queue。在Java标准库都都有实现，一个是Stack,另一个是LinkedList(Queue是它实现的接口)。
经典题目：
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
3. 树
这里的树通常是指二叉树，每个节点都包含一个左孩子节点和右孩子节点，像下面这样：
class TreeNode{int value;TreeNode left;TreeNode right;}
下面是与树相关的一些概念：
二叉搜索树：左结点 <= 中结点 <= 右结点
平衡 vs. 非平衡：平衡二叉树中，每个节点的左右子树的深度相差至多为1（1或0）。
满二叉树（Full Binary Tree）：除叶子节点以为的每个节点都有两个孩子。
完美二叉树（Perfect Binary Tree）：是具有下列性质的满二叉树：所有的叶子节点都有相同的深度或处在同一层次，且每个父节点都必须有两个孩子。
完全二叉树（Complete Binary Tree）：二叉树中，可能除了最后一个，每一层都被完全填满，且所有节点都必须尽可能想左靠。
经典题目：
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. 图
图相关的问题主要集中在深度优先搜索（depth first search）和广度优先搜索（breath first search）。深度优先搜索很简单，广度优先要注意使用queue. 下面是一个简单的用队列Queue实现广度优先搜索。
public class GraphTest {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);}}}}}
经典题目：
复制图(Clone Graph)
5. 排序
下面是不同排序算法的时间复杂度，你可以去wiki看一下这些算法的基本思想。
AlgorithmAverage TimeWorst TimeSpace
冒泡排序(Bubble sort)n^2n^21
选择排序(Selection sort)n^2n^21
插入排序(Insertion sort)n^2n^2
快速排序(Quick sort)n log(n)n^2
归并排序(Merge sort)n log(n)n log(n)depends
* 另外还有BinSort, RadixSort和CountSort 三种比较特殊的排序。
经典题目： Mergesort, Quicksort, InsertionSort.
6. 递归 vs. 迭代
对程序员来说，递归应该是一个与生俱来的思想（a built-in thought），可以通过一个简单的例子来说明。问题：
有n步台阶，一次只能上1步或2步，共有多少种走法。生活若剥去理想、梦想、幻想，那生命便只是一堆空架子
