Article translation. The Best Algorithms for Writing Code

The Best Algorithms for Writing Code

This will be a large article, the original of which can be found here The article contains a number of problems with typical solutions. For most tasks, various solution algorithms are given, which we will update together, and, of course, we will try to track additions and code changes on the original site. This is my first translation, which, it seems to me, needs to be translated not just “head on”, but with some text adjustments and the addition of a small amount of water, do not judge strictly. An inquisitive reader is simply obliged to pay attention to the fact that the translation of the table of contents of the article already contains changes relative to the original - this is due to the fact that there are far from 10 algorithms in the article. it happened, not 10 either, so just accept it and move on. I will be glad if readers supplement the code with new solutions and / or correct the translation of the article.Well, let's get started ... Below are general sections containing typical problems and classical algorithms for solving these problems. The author of the original article notes that a deep understanding of these algorithms requires much more effort than just reading or copy-pasting the code, and this electronic tutorial serves only to provide general coverage of various options for solving the most common problems. The topics we will try to cover are: 1) String/Array/Matrix, 2) Linked List, 3) Tree & Heap, 4) Graph, 5) Sorting, 6) Recursion vs. Iteration, 7) Dynamic Programming, 8) Bit Manipulation, 9) Probability, 10) Combinations and Permutations 11) Math This article is intended to be read by people who already know the basics of the language and want to expand their knowledge of algorithmics a bit.heaps , trees, depth-first search , dynamic programming

1. String/Array/Matrix

In Java, strings are stored as an array of char characters, which allows a string to be treated as a simple sequence of characters. Later in the article there is a list of non-complete methods to remember that are used in all IDEs, which I find a bit odd because the article itself assumes the reader knows the methods of the classes. The methods of the String class can be found here , and the methods of the Arrays class can be found here Strings in Java are very easy to understand, but dealing with tasks often requires the use of complex algorithms, such as dynamic programming, recursion, and others. Standard tasks on the topic:

1. Reordering an array.
2. Recognition of reverse Polish notation .
3. Finding the longest palindrome substring
4. Word recognition
5. Word recognition 2
6. Search for matches by regular expressions
7. Merging Intersecting Intervals
8. Merging intervals by merging interval
9. Sum of two array numbers
10. Sum of two array numbers 2
11. Sum of two array numbers 3
12. The sum of three numbers is 0
13. The sum of four numbers is equal to an arbitrary number
14. The sum of three numbers is close to an arbitrary number
15. Convert string to number

s Triangle 45) Container With Most Water 46) Count and Say 47) Repeated DNA Sequences 48) House Robber 49) Dungeon Game (DP) 2. Linked List The implementation of a linked list is pretty simple in Java. Each node has a value and a link to the 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 the 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 10) Intersection of Two Linked Lists 3. Tree & Heap 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 (eg, 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 [Palantir] 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 14) Symmetric Tree 15) Binary Search Tree Iterator 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 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: 1) Clone Graph 5. Sorting Time complexity of different sorting algorithms. You can go to wiki to see the 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. 4) Maximum Gap (Bucket Sort) 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 solved 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]; } Classic problems: 1) Edit Distance 2) Longest Palindromic Substring 3) Word Break 3) Word Break II 4) Maximum Subarray 4) Maximum Product Subarray 5) Palindrome Partitioning 6) Candy [Google] 7) Jump Game 8) Best Time to Buy and Sell Stock III (DP) 8) Best Time to Buy and Sell Stock IV (DP) 9) Dungeon Game (DP) 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) public static boolean getBit(int num, int i){ int result = num & (1<