# 软件工程师必须要知道的算法和数据结构(来自quora)

1: Sorting Algorithms
Sorting Algorithm – Bubble Sort (Sorting Algorithm – Bubble Sort)
Sorting Algorithm – Selection Sort (Sorting Algorithm – Selection Sort)
Sorting Algorithm – Insertion Sort (Sorting Algorithm – Insertion Sort)
Sorting Algorithm – Heap Sort (Sorting Algorithm – Heap Sort)
Sorting Algorithm – Merge Sort (Sorting Algorithm – Merge Sort)
Pancake Sorting (Pancake Sorting)

Reverse a Linked List – Iterative (Reverse a Linked List – Iterative)
Reverse a Linked List – Recursive (Reverse a Linked List – Recursive)
Merge two sorted linked lists (

Find intersection of two Linked Lists (Find intersection of two Linked Lists)
Find intersection of two Linked Lists – O(m + n) Time Complexity and O(1) Space Complexity (Find intersection of two Linked Lists – O(m + n) Time Complexity and O(1) Space Complexity)
Detect a loop in a linked list and find the node where the loop starts. (Detect a loop in a linked list and find the node where the loop starts.)
Convert a binary tree to doubly linked list (Convert a binary tree to doubly linked list)
Convert a sorted Doubly Linked List to Balanced Binary Search Tree (Convert a sorted Doubly Linked List to Balanced Binary Search Tree)
LRU Cache Implementation (LRU Cache Implementation)

3: Algorithms on  Arrays
Count frequencies of array elements in range 1 to n (Count frequencies of array elements in range 1 to n)
Find all permutations of a String (Find all permutations of a String)
Binary Search in a Sorted Array (Binary Search in a Sorted Array)
Find a Peak Element in an array (Find a Peak Element in an array)
Find pivot in a sorted rotated array (Find pivot in a sorted rotated array)
Find an element in a sorted rotated array (Find an element in a sorted rotated array)
Find element in sorted rotated array without finding pivot (Find element in sorted rotated array without finding pivot)
Find duplicates in an integer array (Find duplicates in an integer array)
Maximum average subarray (Maximum average subarray)
Maximum subarray sum (Maximum subarray sum)
Next greater element in an array (Next greater element in an array)
Fibonacci Number (Fibonacci Number)
Rotate an Array (Rotate an Array)
Find Majority Element in an Array (Find Majority Element in an Array)
Find median of two sorted arrays (Find median of two sorted arrays)
First non-repeating character in a string (First non-repeating character in a string)
Re-arrange elements in an array to put positive and negative elements in alternate order (Re-arrange elements in an array to put positive and negative elements in alternate order)
Find the next greater number using same digits (Find the next greater number using same digits)
Longest Substring with non-Repeating Characters (Longest Substring with non-Repeating Characters)
Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence (Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence)
Find minimum cost path in a matrix (Find minimum cost path in a matrix)
Find the length of longest increasing subsequence in an array (Find the length of longest increasing subsequence in an array)
Find the longest increasing subsequence in an array O(n logn) (Longest Increasing Subsequence O(n logn))
Find the length of longest bitonic subsequence in an array (Find the length of longest bitonic subsequence in an array)
Find total number of ways to make change using given set of coins (Find total number of ways to make change using given set of coins)
Minimum number of coins to make change (Minimum number of coins to make change)
Count all possible decodings of a given digit sequence – (Count all possible decodings of a given digit sequence)
Find increasing sub-sequence of length three having maximum product (Find increasing sub-sequence of length three having maximum product)
Find increasing sub-sequence of length three having maximum product | Optimized approach (Find increasing sub-sequence of length three having maximum product | Optimized approach)
Find index of 0 to replace to get longest continuous sequence of 1s (Find index of 0 to replace to get longest continuous sequence of 1s)
O(n) time approach to find index of 0 to replace to get longest continuous sequence of 1s (O(n) time approach to find index of 0 to replace to get longest continuous sequence of 1s)
Find an integer array corresponding to the string specifying increase-decrease transitions (Find an integer array corresponding to the string specifying increase-decrease transitions)
Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence (Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence)
Merge two sorted arrays without using extra space (Merge two sorted arrays without using extra space)
0-1 Knapsack Problem (0-1 Knapsack Problem)
The Skyline Problem (The Skyline Problem)
Search a sorted matrix (Search a sorted matrix)
Buy and sell stocks – 1 (Buy and sell stocks – 1)
Buy and sell stocks – 2 (Buy and sell stocks – 2)
Gold Mine Problem (Gold Mine Problem)
Distribute Chocolates Problem (Distribute Chocolates Problem)
Trapping Rain Water between Towers (Trapping Rain Water between Towers)
Find Minimum Length Sub Array With Sum K (Find Minimum Length Sub Array With Sum K)

5: Algorithms on Trees
Check if a binary tree is a binary search tree (Check if a binary tree is a binary search tree)
Check if two nodes are cousins in a Binary tree (Check if two nodes are cousins in a Binary tree)
Remove all nodes which lie on path having sum less than k (Remove all nodes which lie on path having sum less than k)
Binary Search tree | Insertion and Search (Binary Search tree | Insertion and Search)
Binary Search tree | Deletion (Binary Search tree | Deletion)
Binary Tree Level Order Traversal (Binary Tree Level Order Traversal)
Print bottom view of a binary tree (Print bottom view of a binary tree)
Print bottom view of a binary tree using level order traversal (Print bottom view of a binary tree using level order traversal)
Check if a binary tree is balanced or not (Check if a binary tree is balanced or not)
Check if a binary tree is sub-tree of another binary tree in space O(1) (Check if a binary tree is sub-tree of another binary tree in space O(1))
Check if a binary tree is sub-tree of another binary tree in time O(n) (Check if a binary tree is sub-tree of another binary tree in time O(n))
Check if all internal nodes of BST have only one child without building tree (Check if all internal nodes of BST have only one child without building tree)
Check if a given binary tree is symmetric tree or not (Check if a given binary tree is symmetric tree or not)
Check if two binary search trees are identical given their array representations (Check if two binary search trees are identical given their array representations)
Check if two binary search trees are identical given their array representations | Set 2 (Check if two binary search trees are identical given their array representations | Set 2)
Check if the given n-ary tree is symmetric tree or not (Check if the given n-ary tree is symmetric tree or not)
Check if two binary trees are identical (Check if two binary trees are identical)
Convert a binary tree to doubly linked list (Convert a binary tree to doubly linked list)
Convert a sorted Doubly Linked List to Balanced Binary Search Tree (Convert a sorted Doubly Linked List to Balanced Binary Search Tree)
Create a balanced Binary Search Tree from a sorted array (Create a balanced Binary Search Tree from a sorted array)
Check whether a binary tree is complete or not (Check whether a binary tree is complete or not)
Check whether a binary tree is a full binary tree or not (Check whether a binary tree is a full binary tree or not)
Construct binary tree from inorder and postorder traversals (Construct binary tree from inorder and postorder traversals)
Construct binary tree from inorder and preorder traversals (Construct binary tree from inorder and preorder traversals)
Construct the binary tree from its parent array representation (Construct the binary tree from its parent array representation)
AVL tree | Basics (AVL tree | Basics)
AVL tree | Insertion (AVL tree | Insertion)
AVL tree | Deletion (AVL tree | Deletion)
Convert binary tree to binary search tree (Convert binary tree to binary search tree)
Find depth of deepest odd level leaf node (Find depth of deepest odd level leaf node)
Diagonal Sum of a Binary Tree. (Diagonal Sum of a Binary Tree.)
Find height of the binary tree from its parent array representation (Find height of the binary tree from its parent array representation)
Find sum of all left leaves of a binary tree (Find sum of all left leaves of a binary tree)
Find floor and ceiling of an element from given dataset using binary search tree (Find floor and ceiling of an element from given dataset using binary search tree)
Recover a Binary Search Tree if positions of two nodes are swapped. (Recover a Binary Search Tree if positions of two nodes are swapped.)
In-order Successor of a Node in a Binary Tree (In-order Successor of a Node in a Binary Tree)
In-order Traversal of a Binary Tree (In-order Traversal of a Binary Tree)
Print left view of a binary tree (Print left view of a binary tree)
Lowest Common Ancestor of 2 nodes in a Binary Tree (Lowest Common Ancestor of 2 nodes in a Binary Tree)
Minimum Depth of a Binary Tree (Minimum Depth of a Binary Tree)
Convert a binary tree to its mirror tree (Convert a binary tree to its mirror tree)
Convert the given n-ary tree to its mirror image (Convert the given n-ary tree to its mirror image)
Trie Data Structure | Insert and search (Trie Data Structure | Insert and search)
Trie Data Structure | Delete (Trie Data Structure | Delete)
Pattern matching using Trie (Pattern matching using Trie)
Longest Prefix Matching using Trie (Longest Prefix Matching using Trie)
Post-order Traversal of a Binary Tree (Post-order Traversal of a Binary Tree)
Pre-order Traversal of a Binary Tree (Pre-order Traversal of a Binary Tree)
Print all Root to Leaf paths of a Binary Tree (Print all Root to Leaf paths of a Binary Tree)
Print binary tree in vertical order (Print binary tree in vertical order)
Print all nodes of a binary tree that do not have sibling (Print all nodes of a binary tree that do not have sibling)
Remove all the half nodes from a given binary tree (Remove all the half nodes from a given binary tree)
Remove the nodes of binary search tree which are outside the given range (Remove the nodes of binary search tree which are outside the given range)
Print right view of a binary tree (Print right view of a binary tree)
Serialize and Deserialize a binary search tree using post order traversal (Serialize and Deserialize a binary search tree using post order traversal)
Serialize and Deserialize a binary search tree (Serialize and Deserialize a binary search tree)
Find the size of largest BST in a binary tree (Find the size of largest BST in a binary tree)
Print top view of a binary tree using level order traversal (Print top view of a binary tree using level order traversal)
Print top view of a binary tree (Print top view of a binary tree)
Total number of possible Binary Search Trees with n keys (Total number of possible Binary Search Trees with n keys)
Given a sequence of words, group together all anagrams and print them. (Given a sequence of words, group together all anagrams and print them.)

7: Algorithms on Strings
Word Break Problem (Word Break Problem)
Reverse words in a string (Reverse words in a string)
Find all permutations of a String (Find all permutations of a String)
Find minimum edit distance between given two strings (Find minimum edit distance between given two strings)
To print maximum number of As using given four keys. (To print maximum number of As using given four keys.)
Check balanced parentheses in a string (Check balanced parentheses in a string)
Distinct binary strings of length n with no consecutive 1s (Distinct binary strings of length n with no consecutive 1s)
Finding 10 letter repeated DNA sequences. (Finding 10 letter repeated DNA sequences.)
First non-repeating character in a string (First non-repeating character in a string)
Group all anagrams together from a given array of strings | Set 1 (Group all anagrams together from a given array of strings | Set 1)
Longest Common Subsequence (Longest Common Subsequence)
Longest Common Substring (Longest Common Substring)
Longest Palindromic Subsequence (Longest Palindromic Subsequence)
Longest Palindromic Substring (Longest Palindromic Substring)
Longest Substring with non-Repeating Characters (Longest Substring with non-Repeating Characters)
Palindrome Min Cut (Palindrome Min Cut)
Shortest Palindrome (Shortest Palindrome)
The longest prefix suffix array computation in KMP pattern matching algorithm. (The longest prefix suffix array computation in KMP pattern matching algorithm.)
The Knuth Morris Pratt algorithm for pattern matching. (The Knuth Morris Pratt algorithm for pattern matching.)

8: Algorithms on Graphs
Bellman-Ford Algorithm (Bellman-Ford Algorithm)
Dijkstra’s Shortest Path algorithm (Dijkstra’s Shortest Path algorithm)
Friend Circles Problem – Graph Theory (Friend Circles Problem – Graph Theory)
Topological Sorting of a Directed Acyclic Graph. (Topological Sorting of a Directed Acyclic Graph.)

10: Dynamic Programming Algorithms
Word Break Problem (Word Break Problem)
Find minimum cost path in a matrix (Find minimum cost path in a matrix)
Maximum subarray sum (Maximum subarray sum)
Find total number of ways to make change using given set of coins (Find total number of ways to make change using given set of coins)
Minimum number of coins to make change (Minimum number of coins to make change)
Find the length of longest increasing subsequence in an array (Find the length of longest increasing subsequence in an array)
Find the length of longest bitonic subsequence in an array (Find the length of longest bitonic subsequence in an array)
Count all possible decodings of a given digit sequence (Count all possible decodings of a given digit sequence)
To print maximum number of As using given four keys. (To print maximum number of As using given four keys.)
Find minimum edit distance between given two strings (Find minimum edit distance between given two strings)
Total number of possible Binary Search Trees with n keys (Total number of possible Binary Search Trees with n keys)
0-1 Knapsack Problem (0-1 Knapsack Problem)
Longest Common Subsequence (Longest Common Subsequence)
Longest Common Substring (Longest Common Substring)
Longest Increasing Subsequence O(n logn) (Longest Increasing Subsequence O(n logn))
Longest Palindromic Subsequence (Longest Palindromic Subsequence)
Longest Palindromic Substring (Longest Palindromic Substring)
Fibonacci Number (Fibonacci Number)
Palindrome Min Cut (Palindrome Min Cut)
Shortest Palindrome (Shortest Palindrome)
Subset Sum Problem (Subset Sum Problem)Gold Mine Problem (Gold Mine Problem)