Summary of top 10 algorithm concepts commonly used in Java programming interviews

The following are the top 10 algorithm-related concepts in programming interviews. I will illustrate these concepts through some simple examples. Since fully mastering these concepts requires more effort, this list is intended only as an introduction. This article will look at the problem from a Java perspective, including the following concepts:

1. String

If the IDE does not have the code auto-completion function, you should remember the following methods.

toCharArray() // 获得字符串对应的char数组
Arrays.sort()  // 数组排序Arrays.toString(char[] a) // 数组转成字符串
charAt(int x) // 获得某个索引处的字符
length() // 字符串长度
length // 数组大小

2. Linked list

In Java, the implementation of linked list is very simple. Each node Node has a value val and a link next pointing to the next node.

class Node {
    int val;
    Node next;
    Node(int x) {
        val = x;
        next = null;
    }
}

Two famous applications of linked lists 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;
        }
    }
}

3. Tree

The tree here usually refers to a binary tree. Each node contains a left child node and a right child node, like the following:

class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;
}

The following is the tree with Some related concepts:

Balanced vs. Unbalanced: In a balanced binary tree, the depth difference between the left and right subtrees of each node is at most 1 (1 or 0).

Full Binary Tree: Every node except the leaf nodes has two children.

Perfect Binary Tree: It is a full binary tree with the following properties: all leaf nodes have the same depth or are at the same level, and each parent node must have two children.

Complete Binary Tree: In a binary tree, every level except maybe the last one is completely filled, and all nodes must be as close to the left as possible.

Translator’s Note: A perfect binary tree is also vaguely called a complete binary tree. An example of a perfect binary tree is the ancestry graph of a person at a given depth, since every person must have two biological parents. A complete binary tree can be thought of as a perfect binary tree that can have a number of additional leaf nodes leaning to the left. Question: What is the difference between a perfect binary tree and a full binary tree? (Reference: http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html)

4. Graph

Graph-related issues are mainly focused on depth first search (depth first search) and breadth first search (breath first) search).

The following is a simple implementation of graph breadth first search.

1) Define 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 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) Use queue Queue to implement breadth-first search

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:

1 value: 2 value: 3 value: 5 Find value: 5

2 value: 4

5. Sorting

The following is the time complexity of different sorting algorithms. You can go to the wiki to take a look at the basic ideas of these algorithms.

Also, here are some implementations/demos: Counting sort, Mergesort, Quicksort, InsertionSort.

"Visually intuitive experience of 7 commonly used sorting algorithms"

"Video: 6-minute demonstration of 15 sorting algorithms"

6. Recursion vs. Iteration

For programmers, recursion should be an innate A built-in thought can be illustrated with a simple example.

Question: There are n steps, and you can only go up 1 or 2 steps at a time. How many ways are there?

Step 1: Find the relationship between the first n steps and the first n-1 steps.

In order to walk up n steps, there are only two ways: climb 1 step from n-1 steps to get there or climb 2 steps from n-2 steps to get there. If f(n) is the number of ways to climb to the nth step, then f(n) = f(n-1) + f(n-2).

Step 2: Make sure the start conditions are 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 in n, because there are many redundant calculations, as follows:

f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

The direct idea is to Convert 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 take a look at Recursion vs Iteration.

7. Dynamic Programming

Dynamic programming is a technique for solving problems of the following nature:

A problem can be solved by solving smaller sub-problems (Translator’s Note: The optimal solution to the problem contains its sub-problems The optimal solution, that is, the optimal substructure properties).

The solutions to some sub-problems may need to be calculated multiple times (Translator’s Note: This is the overlapping nature of sub-problems).

The solutions to the subproblems are stored in a table, so that each subproblem only needs to be calculated once.

Requires extra space to save time.

The step climbing problem completely conforms to the above four properties, so it can be solved by dynamic programming method.

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 operations

Bit operators:

获得给定数字n的第i位：(i从0计数并从右边开始)

public static boolean getBit(int num, int i){
    int result = num & (1<<i);
    if(result == 0){
        return false;
    }else{
        return true;
    }

例如，获得数字10的第2位：

i=1, n=10
1<<1= 10
1010&10=10
10 is not 0, so return true;

9. 概率问题

解决概率相关的问题通常需要很好的规划了解问题（formatting the problem），这里刚好有一个这类问题的简单例子：

一个房间里有50个人，那么至少有两个人生日相同的概率是多少？（忽略闰年的事实，也就是一年365天）

计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里，我们可以计算所有人生日都互不相同的概率，也就是：365/365 * 364/365 * 363/365 * … * (365-49)/365，这样至少两个人生日相同的概率就是1 – 这个值。

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. 排列组合

组合和排列的区别在于次序是否关键。

如果你有任何问题请在下面评论。

参考/推荐资料：
1. Binary tree
2. Introduction to Dynamic Programming
3. UTSA Dynamic Programming slides
4. Birthday paradox
5. Cracking the Coding Interview: 150 Programming Interview Questions and Solutions, Gayle Laakmann McDowell