Algorithms

Include the test-cases and the sketch of the algorithms for the common algorithm questions.

File Organization:

• basic: basic algorithms
• cc150: the problems in cracking the code interview
• dp: the popular dynamic programming problems, excluding the problems in cc150 and lc
• imagong: the problems on http://imagong.com/
• lc: the problems in leetcode
• recursive: the popular recursive problem, excluding the problems in cc150 and lc

#Problem List:

basic

• binary search
• binary tree
• binary tree inorder iterator
• binary tree postorder iterator
• binary search tree (BST)
• +-*/ expression calculation
• bubble sort
• Burrows Wheeler Transform
• circular buffer
• data structure that supports O(1) add, del, and getRandom
• counting sort
• deduplicate
• find kth smallest
• find kth smallest in sorted matrix
• get binary tree paths
• get most continuous repeated characters
• hashmap
• find primes in range of n
• heap sort
• insertion sort
• find largest square submatrix
• find max with random position
• median of stream
• merge sort
• most repeated number
• one edit distance
• prime factors
• prime within range n
• quicksort iterative
• quicksort recursive
• random shuffle
• read4K
• remove zeros from array
• reverse string
• reverse words in string
• selection sort
• stack with min
• strcmp
• subarray sum
• subarray with sum zero
• trie
• union find
• union of two sorted linked list

cc150

chapter 1 (Array)

• all unique character
• reverse string
• whether one string is the permutation of the other
• replace blank space with '%20'
• run-length encoding
• rotate image in place
• set matrix zeros
• check string rotation using substring

chapter 2 (Linked List)

• remove duplicate from unsorted linked list
• find the kth to the last from a singly linked list (needs improvement)
• delete the middle element from linked list (needs improvement)
• partition list
• add numbers
• detect the begining of the loop
• check whether a linked list is a palindrome (needs improvement)

chapter 3 (Stack and Queue)

• use an array to implement three stacks (not implemented)
• add 'push', 'pop', and 'min' operations for stack, all operations should be in O(1)
• set of stacks
• hanoi
• implement a queue with two stacks
• sort the elements in stack in ascending order
• animal shelter

chapter 4 (Tree and Graph)

• validate balanced binary tree
• check whether route exists in a directed graph (needs improvement)
• create minimal height binary tree
• traverse binary tree by level (needs improvement)
• validate binary search tree
• link the next sibling of binary tree
• lowest common ancestor (LCA)
• sub-tree matching
• find all paths in a binary tree that sum to a specific value (needs improvement)

chapter 5 (Bit Operation)

• insert bits M into N
• represent double in binary
• next number with same number of 1
• number of bits different between A and B
• swap odd and even bits in an integer
• find missing number with fetch operation

chapter 7 (Mathematic)

• Choose game
• probability of collision
• line intersection
• implement -, *, / with + only
• find line that evenly cuts two squares
• line passes the most points
• find the kth number consists of 3, 5, 7

chapter 9 (Dynamic Programming)

• climbing stairs
• unique paths
• find the magic index
• generate all permutations
• generate parenthesis
• paint fill
• find changes
• eight queens
• tallest stack

chapter 11

• merge two arrays
• anagram
• search in rotated array
• find string in an empty string interspersed array
• find element in sorted matrix
• get the rank of elements in stream

chapter 17

• Swap two numbers in place
• Validate tic-tac-toe
• Counts # of trailing 0's in n!
• Find max without comparison
• Find range to sort
• Max subarray
• Implements rand7 using rand5
• Two sum
• Convert BST to Doubly Linked List

chapter 18

• Add two numbers withoug +
• Random suffling
• m out of n reservoir sampling
• Count # 2's in range 0 to n
• Find smallest 1 million in 1 billion
• Find the longest word made of other words in dictionary
• [Batched substring match] (https://github.com/yxjiang/algorithms/blob/master/src/main/java/algorithm/cc150/chapter18/Question8.java)
• Find the median of a sequence of data
• [Word Ladder] (https://github.com/yxjiang/algorithms/blob/master/src/main/java/algorithm/cc150/chapter18/Question10.java)
• [Maximal submatrix with black pixel borders] (https://github.com/yxjiang/algorithms/blob/master/src/main/java/algorithm/cc150/chapter18/Question11.java)
• Maximal submatrix

dp

• find # distinct ways to reach score
• longest common substring (LCA)
• longest increasing subsequences (LIS)

imagong

• edit distance II
• reverse polish
• generate reverse polish
• LCA of binary search tree

lc (java) (python)

• Add Binary (java)
• Add Two Numbers (python) (java)
• Anagram (python)
• Balanced Binary Tree (python) (java)
• Best Time to Buy and Sell Stock (python) (java)
• Best Time to Buy and Sell Stock 2 (python) (java)
• Binary Tree Level Order Traversal (python) (java)
• Binary Tree Level Order Traversal II (python) (java)
• Binary Tree Inorder (python) (java)
• Binary Tree Inorder (python) (java)
• Binary Tree Maximum Path Sum (python) (java)
• Binary Tree Postorder (python) (java)
• Binary Tree Preorder (python) (java)
• Climb Stairs (python) (java)
• Combinations (python) (java)
• Construct Binary Tree from Inorder and Postorder Traversal (python) (java)
• Construct Binary Tree from Preorder and Inorder Traversal (python) (java)
• Copy List With Random Pointer (python) (java)
• Container with Most Water (python) (java)
• Convert Sorted Array to BST (python) (java)
• Convert Sorted List to BST (python) (java)
• Distinct Subsequences (python) (java)
• Find Minimum in Rotated Sorted Array (python) (java)
• Flatten Binary Tree to Linked List (python) (java)
• Four Sum (python) (java)
• Gas Station (python) (java)
• Generate Parentheses (python) (java)
• Integer to Roman (python) (java)
• Insertion Sort List (python) (java)
• Interleaving String (java)
• Intersection of Two Linked Lists (java)
• Jump Game (python) (java)
• Jump Game II (python) (java))
• Largest Rectangle in Histogram (python) (java)
• Linked List Cycle (python) (java)
• Linked List Cycle II (python) (java)
• Longest Common Prefix (python) (java)
• Longest Consecutive Sequence (python) (java)
• Longest Substring without Repeating Character (python) (java)
• Max Depth of Binary Tree (python) (java)
• Maximal Rectangle (python) (java)
• Maximum Subarray (python) (java)
• Maximum Product Subarray (python) (java)
• Merge K Sorted Lists (python) (java)
• Merge Two Sorted Lists (python) (java)
• Minimum Depth of Binary Tree (python) (java)
• Minimum Path Sum (python) (java)
• Multiply String (python) (java)
• Next Permutation (python) (java)
• N-Queens (python) (java)
• N-Queens II (python) (java)
• Number of Unique Binary Search Tree (python)
• Palindrome Partition (python) (java)
• Pascal Triangle (python) (java)
• Pascal Triangle II (python) (java)
• Path Sum (python) (java)
• Path Sum II (python) (java)
• Permutation (python) (java)
• Permutation II (python) (java)
• Permutation Sequence (python) (java)
• Plus One (python) (java)
• Populating Next Right Point in Each Node (python) (java)
• Populating Next Right Point in Each Node II (python) (java)
• Pow (python) (java)
• Recover Binary Search Tree (python) (java)
• Regular Expression Matching (python) (java)
• Remove Duplicates from Sorted List (python) (java)
• Remove Duplicates from Sorted List II (python) (java)
• Remove Duplicates from Sorted Array (python) (java)
• Remove Duplicates from Sorted Array II (python) (java)
• Remove Element (python) (java)
• Reorder List (python) (java)
• Reversed Linked List II (python) (java)
• Reverse Int (python) (java)
• Reverse Word In a String (python) (java)
• Roman to Int (python) (java)
• Rotate Image (python) (java)
• Rotate List (python) (java)
• Same Tree (python) (java)
• Search A 2D Matrix (python) (java)
• Search Insert Position (python)
• Set Matrix Zeros (python) (java)
• Single Number (python) (java)
• Single Number II (python) (java)
• Sort Color (python) (java)
• Sort List (python) (java)
• Spiral Matrix (python) (java)
• Spiral Matrix II (python) (java)
• Sqrt (python) (java)
• Subset (python) (java)
• Substring with Concatenation of All Words (python) (java)
• Sum Root to Leaf Numbers (python) (java)
• Swap Nodes in Pairs (python) (java)
• Symmetric Tree (python) (java)
• Three Sum (python) (java)
• Three Sum (python) (java)
• Triangle (python) (java)
• Two Sum (python) (java)
• Unique Binary Search Tree (python) (java)
• Unique Binary Search Tree (python) (java)
• Unique Paths (python) (java)
• Unique Paths II (python) (java)
• Validate BST (python) (java)
• Valid Palindrome (python) (java)
• Valid Parenthesis (python) (java)
• Valid Sudoku (python) (java)
• Wildcard Matching (python) (java)
• Word Break (python) (java)
• Word Search (python) (java)

recursive

• lowest common ancestor
• closest element in BST
• next palindrome
• number of zero groups
• generate all valid parenthesis consists of (, [, {, }, ], )

gongxiangzuche

• best time to buy and sell

guge

• max distance in array
• most repeated key in BST
• find anagram in dict
• find first missing
• find right deepest in binary tree
• plus minus expression calculation
• power of 3
• satisfied pairs
• satisfied triples
• substring anagram
• two dimensional trapping rain water
• weird sort

lingying

• array element multiplication
• upside down binary tree
• nested list weighted sum
• depth of string representation

qichuangzaocan

• burglarizing house
• coin change
• upper/lowercase permutation
• K Edit Distance
• Parse CSV

tuding

• maximal subsection
• print matrix diagonal
• weighted random sampling