Mathematical Problems in Algorithms (Summary)

Source: http://help.topcoder.com/data-science/competing-in-algorithm-challenges/algorithm-tutorials/mathematics-for-topcoders/

1: Prime Check

public boolean isPrime (int n)
{
   if (n<=1) return false;
   if (n==2) return true;
   if (n%2==0) return false;
   int m=Math.sqrt(n);

   for (int i=3; i<=m; i+=2)
      if (n%i==0)
         return false;

   return true;
}

2: Get All Primes

public boolean[] sieve(int n)
{
   boolean[] prime=new boolean[n+1];
   Arrays.fill(prime,true);
   prime[0]=false;
   prime[1]=false;
   int m=Math.sqrt(n);

   for (int i=2; i<=m; i++)
      if (prime[i])
         for (int k=i*i; k<=n; k+=i)
            prime[k]=false;

   return prime;
}

3: greatest common divisor (GCD)

Euclid's algorithm 

//assume that a and b cannot both be 0
public int GCD(int a, int b)
{
   if (b==0) return a;
   return GCD(b,a%b);
} 

4: lowest common multiple (LCM)

public int LCM(int a, int b)
{
   return b*a/GCD(a,b);
}

5: Rectangles Overlap

Suppose we have two rectangles R1 and R2. Let (x1, y1) be the location 
of the bottom-left corner of R1 and (x2, y2) be the location of its 
top-right corner. Similarly, let (x3, y3) and (x4, y4) be the respective
 corner locations for R2. The intersection of R1 and R2 will be a 
rectangle R3 whose bottom-left corner is at (max(x1, x3), max(y1, y3)) 
and top-right corner at (min(x2, x4), min(y2, y4)). If max(x1, x3) > 
min(x2, x4) or max(y1, y3) > min(y2, y4) then R3 does not exist, ie 
R1 and R2 do not intersect. 

6: Fractions

public int[] multiplyFractions(int[] a, int[] b)
{
   int[] c={a[0]*b[0], a[1]*b[1]};
   return c;
} 

What happened in Google Search?

Source:http://www.youtube.com/watch?v=modXC5IWTJI&feature=player_embedded

Why Gmail does not improve its left-side bar? I use it hundreds of time every week and suffer hundreds of time every week

How to find a Solution?

Source: How To Find a Solution @ http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=findSolution

1)
Straight-forward problems that don't require any special technique (e.g. simulation, searching, sorting, BST etc.)

2) 
Breadth First Search (BFS)
Problems that use BFS usually ask to find the fewest number of steps (or the shortest path) needed to reach a certain end point (state) from the starting one. & all of edges having the same cost of 1.

Example Leetcode:
1: Word Ladder

3)
Flood Fill
Sometimes you may encounter problems that are solved by the help of Flood Fill, a technique that uses BFS to find all reachable points. 

Example Leetcode:
1: Surrounded Regions
2: Binary Tree Level Order Traversal

4)
Brute Force
How does a brute force algorithm work? Actually, it tries all possible situations and selects the best one. It's simple to construct and usually simple to implement. If there is a problem that asks to enumerate or find all possible ways (situations) of doing a certain thing, and that doesn't have high limits - then it's most probably a brute force problem.

5)
Dynamic Programming
1: Optimal Subproblem
2: Repeated Computing

AND both the search space and the target are integers!!

Example Leetcode:
1: Unique Paths I & II
2: Climbing Stairs
3: Decode Ways

6) 
Greedy Algorithm
1: Optimal Subproblem
2: Repeated Computing
3: Greedy Property

7)
Recursion Method
Tree, String, Array

Example Leetcode:
1: Scramble String

8)
N-Scan Method

1. 2-round Scan
2. Fast-Slow Scan
3. Reversed Scan

9) 
Linear Programming
1: Objective Function
2: Constraints

Coding Strategy of Leetcode

Reverse Words in a String
Idea: Double Reverse

Evaluate Reverse Polish Notation
Idea: Typical Last-in-First-out problem, so should use Stack

Word Break I

Idea: DP

CanBreak[i] = CanBreak[k] && word.substr(k+1, i) in the Dictionary 

Word Break II

Idea: DP

Redundancy: Repeated checking all possibilities in a place

Solution: Pre-Calculate the list

Max Points on a Line

Idea: Slope -> HashMap

Careful: Vertical - Same x location;

Careful: Same Location: Repeated node;

Sort List

Idea: Merge Sort O(nlgn) and Constant Space
Careful: define new head node when merging;

Insertion Sort List

 

Idea: find the location from the head and always keep its previous node;

LRU Cache

Idea: hashmap + list

get: O(1) need a Hashmap<key, Object*>

       Also, need to insert to front of the list;

set: O(1) need a Hashmap and then add to top or re-insert to top;

Binary Tree Postorder Traversal

Idea: Magic two-stacks version

Or

Idea: one-Stack-prev-curr version

Binary Tree Preorder Traversal

Idea: Stack + Right-First-In-Stack

Binary Tree Inorder Traversal
Idea: Code attached.
while(current != NULL || mystack.empty() == false) {

if(current != NULL) {

mystack.push(current);

current  = current -> left;

}

else {

printf("%d,", mystack.top()->key);

current  = mystack.top() -> right;

mystack.pop();

}

}

Reorder List

Idea: partial re-order and then merge lists

Linked List Cycle I && II

 

Idea: fast-slow traversal algorithms

Copy List with Random Pointer

Idea: std::unordered_map<RandomListNode*, RandomListNode*> a_hash_map

Single Number I

Idea: Feature of bitwise operation XOR: cancel each other

Single Number II

Idea: Count and check the sum of each bit % 3, is 0 or not? 

If Yes, the missing number has 0 in the location, If No, set the location as 1. like: n = n | (1 << l)

Candy

Idea: Two-round Scanning and Double-check correctness

Gas Station

Idea: Greedy Search the first location until the sum to end is always positive

Clone Graph

Idea: std::unordered_map<RandomListNode*, RandomListNode*> a_hash_map

Palindrome Partitioning

Idea: DP & Pre-Calculating Post-ward Palindrome Array

Palindrome Partitioning II

Idea: Same with I but keep a updated parameter

Surrounded Regions

Idea: Queue & O -> Y firstly and then O -> X && Y -> O;

Sum Root to Leaf Numbers

Idea: Recursive Method

Longest Consecutive Sequence

Idea: std::unordered_set & check surrounding

Word Ladder

Idea: shortest path

Word Ladder II

Idea: output all paths (loops processing) + std::unordered_set<bool> processed 

Valid Palindrome
Idea: Clean String and Scan

Best Time to Buy and Sell Stock
Idea: maintain the min value and max profit

Best Time to Buy and Sell Stock II
Idea: Aggregate all benefits

Best Time to Buy and Sell Stock III
Idea: DP and two-round scan

Triangle

Idea: Recursive Algorithm and re-used vector (Too Costly)
Idea: Post-Order Scan

Pascal's Triangle I & II

Idea: Purely Logic, no complex algorithm

Populating Next Right Pointers in Each Node I & II

Idea: BFS, level by level processing; Instead of using transitional queues, use pointers and next; 

Flatten Binary Tree to Linked List

Idea: Post-order processing and connect left to right

Path Sum I & II

Idea: Recursive Algorithm

Minimum Depth of Binary Tree 

Idea: Recursive Algorithm and Cut Branch

Balanced Binary Tree

Idea: Recursive Get Height and Compare. (BFS, DFS [P/I/P-order] are mostly enough)

Convert Sorted Array to Binary Search Tree

 

Idea: Recursively find the middle and new a node;

Convert Sorted List to Binary Search Tree

Idea: Build a BSF with N nodes and then set the value using In-order traversal method

Binary Tree Level Order Traversal I && II

Idea: use two-queue method; Reverse the vector in the end;

Construct Binary Tree from Inorder and Postorder Traversal

 

Construct Binary Tree from Preorder and Inorder Traversal

 

Idea: Recursive Method and HashTable for seaching locations

Construct Binary Tree from given preorder and postorder traversals

No unique tree if no more constraints.

Maximum Depth of Binary Tree
Idea: Recursive method

Binary Tree Zigzag Level Order Traversal
Idea: Two stacks + Flag: leftToRight

Symmetric Tree
Idea: Level by Level + Check Symmetric 

Same Tree
Idea: Post-Order Scan

Recover Binary Search Tree
Idea: 
1: In-Order Traversal -> Find the first node violating ascending order
2: Reversed In-Order Traversal -> Find the first node violating descending order
3: Swap

Interleaving String
Idea: Recursive Algorithm is too costly, for cases like:s1=aa*, b=aa*, c=aaaa**;
Idea: Use 2-D Dynamic Programming; 
M[i][j] = (M[i][j-1] && b[j] == c[i+j]) || (M[i-1][j] && a[i] == c[i+j]);

Unique Binary Search Trees I && II
Idea: Recursively pick the middle node; For II, copy for each branch;

Restore IP Addresses
idea: BFS and cut branch
Reverse Linked List II
Idea: Find and Reverse, careful the border cases

Subsets I && II
Idea: Sort and then 2-level Scan

Decode Ways
Idea: BFS but careful on the special cases, 0

Merge Sorted Array
Idea: Scan the array from the back to the front

Scramble String

Idea: DFS and cut branch

Partition List
Idea: maintain a pointer to the next place to insert, like quick sort.

Maximal Rectangle
Idea: Pre-Process 2-D Matrix to keep the number of 1s in the same row before it.

Largest Rectangle in Histogram
Idea 1: Surrounding Search O(n^2)
Idea 2: Divide and Conquer O(nlgn);
Idea 3: Stack O(n)

Remove Duplicates from Sorted List I && II
Idea: Logic, no algorithms

Sort Colors
Idea 1: Counting Sort
Idea 2: Swap, but be careful on the left side and right side (different)
Search a 2D Matrix
Idea: Two Binary Search, care special cases.

Set Matrix Zeroes
Idea: Two vectors to keep the rows and cols that need to set to 0.

Climbing Stairs
Idea 1: BFS, but costly, O(2^n)
Idea 2: DP. N[n] = N[n-1] + N[n2], O(n)
Idea 3: Fibonacci Optimization Algorithm, O(lgn) 

Sqrt(x)

Idea: Binary Check (min, max), careful overflow.

Plus One

Idea: addition (a, b, carry_bit), no algorithm

Add Binary

Idea: Similar to Plus One

Merge Two Sorted Lists

Idea: Logic, no algorithm

Spiral Matrix II

Idea: Spiral Scan Matrix, Each Time Scan 4 Border

Pow(x, n)

Idea: Recursive and Re-use

Rotate Image

Idea: Spiral Scan Matrix, Each Time Scan 4 Border

Permutations

 

Idea: swap for each possibility

First Missing Positive

idea: swap, careful special cases, duplicate values.

Count and Say
Idea: Logic, no algorithm
Remove Element
Idea: Logic, no algorithm
Remove Duplicates from Sorted Array
Idea: Similar with Remove Element

Valid Parentheses
Idea: Stack

Remove Nth Node From End of List
Idea: two-index method

3Sum & 3Sum Closest
Idea: Sort and Hash; Sort and 2-Index Scan

Longest Common Prefix

Idea: Logic, No Algorithm

Roman to Integer
Idea: Logic, No Algorithm

Regular Expression Matching
Idea: Star or not

Palindrome Number
Idea: First (%(10^Bits)) == Last (&1)

String to Integer (atoi)
Idea: Logic, Many Special Cases

Reverse Integer
Idea: Logic, care special cases, overflow and 0.

Longest Palindromic Substring

Idea: Pick any element as a center

Add Two Numbers

Idea: Logic, no algorithm

Longest Substring Without Repeating Characters

Idea: hash_map and maintain the max_length

Median of Two Sorted Arrays

Idea: Recursive Algorithm

WHAT Google Doc should improve - 2014-June

I am expecting MS Word 2013, but Google Docs is just functional unacceptable.

1: Format
There should have tools like:
1) copy without format ( a new feature is "Clear format", that's useful)
2) copy format of words
3) more configurations (size of Tab and Space, etc)

2: Draw (or Picture Support)
Different from Word, which is more like formal word processing software for reports. Google Doc is for sharing ideas on-line with people around the world.
Picture is always better to explain the idea when words are not sufficient or efficient.
I am not expecting a prefect software like Photoshop, but a simply draw is much better than nothing.

3: UI
Too draft version. The functions are not classified and grouped correctly. Each time, I want to find a function, I have to scan all the functions. The cost is O(n). That's bad.

4: Background
Does it has to be gray?

5: Remember users' operation history and make it more efficient
Like: Remember my last use color. No need to choose color each time;

TBA

LeetCode Question Difficulty Distribution

转自：https://docs.google.com/spreadsheet/pub?key=0Aqt--%20wSNYfuxdGxQWVFsOGdVVWxQRlNUVXZTdEpOeEE&output=html

LeetCode Question Difficulty Distribution: Very Useful

	ID	Question	Diff	Freq	Data Structure	Algorithms

	1	Two Sum	2	5	array	sort
					set	Two Pointers
	2	Add Two Numbers	3	4	linked list	Two Pointers
						Math
	3	Longest Substring Without Repeating Characters	3	2	string	Two Pointers
					hashtable
	4	Median of Two Sorted Arrays	5	3	array	Binary Search
	5	Longest Palindromic Substring	4	2	string
	6	ZigZag Conversion	3	1	string
	7	Reverse Integer	2	3		Math
	8	String to Integer (atoi)	2	5	string	Math
	9	Palindrome Number	2	2		Math
	10	Regular Expression Matching	5	3	string	Recursion
						DP
	11	Container With Most Water	3	2	array	Two Pointers
	12	Integer to Roman	3	4		Math
	13	Roman to Integer	2	4		Math
	14	Longest Common Prefix	2	1	string
	15	3Sum	3	5	array	Two Pointers
	16	3Sum Closest	3	1	array	Two Pointers
	17	Letter Combinations of a Phone Number	3	3	string	DFS
	18	4Sum	3	2	array
	19	Remove Nth Node From End of List	2	3	linked list	Two Pointers
	20	Valid Parentheses	2	5	string	Stack
	21	Merge Two Sorted Lists	2	5	linked list	sort
						Two Pointers
						merge
	22	Generate Parentheses	3	4	string	DFS
	23	Merge k Sorted Lists	3	4	linked list	sort
					heap	Two Pointers
						merge
	24	Swap Nodes in Pairs	2	4	linked list
	25	Reverse Nodes in k-Group	4	2	linked list	Recursion
						Two Pointers
	26	Remove Duplicates from Sorted Array	1	3	array	Two Pointers
	27	Remove Element	1	4	array	Two Pointers
	28	Implement strStr()	4	5	string	Two Pointers
						KMP
						rolling hash
	29	Divide Two Integers	4	3		Binary Search
						Math
	30	Substring with Concatenation of All Words	3	1	string	Two Pointers
	31	Next Permutation	5	2	array	permutation
	32	Longest Valid Parentheses	4	1	string	DP
	33	Search in Rotated Sorted Array	4	3	array	Binary Search
	34	Search for a Range	4	3	array	Binary Search
	35	Search Insert Position	2	2	array
	36	Valid Sudoku	2	2	array
	37	Sudoku Solver	4	2	array	DFS
	38	Count and Say	2	2	string	Two Pointers
	39	Combination Sum	3	3	array	combination
	40	Combination Sum II	4	2	array	combination
	41	First Missing Positive	5	2	array	sort
	42	Trapping Rain Water	4	2	array	Two Pointers
						Stack
	43	Multiply Strings	4	3	string	Two Pointers
						Math
	44	Wildcard Matching	5	3	string	Recursion
						DP
						greedy
	45	Jump Game II	4	2	array
	46	Permutations	3	4	array	permutation
	47	Permutations II	4	2	array	permutation
	48	Rotate Image	4	2	array
	49	Anagrams	3	4	string
					hashtable
	50	Pow(x, n)	3	5		Binary Search
						Math
	51	N-Queens	4	3	array	DFS
	52	N-Queens II	4	3	array	DFS
	53	Maximum Subarray	3	3	array	DP
	54	Spiral Matrix	4	2	array
	55	Jump Game	3	2	array
	56	Merge Intervals	4	5	array	sort
					linked list	merge
					red-black tree
	57	Insert Interval	4	5	array	sort
					linked list	merge
					red-black tree
	58	Length of Last Word	1	1	string
	59	Spiral Matrix II	3	2	array
	60	Permutation Sequence	5	1		permutation
						Math
	61	Rotate List	3	2	linked list	Two Pointers
	62	Unique Paths	2	3	array	DP
	63	Unique Paths II	3	3	array	DP
	64	Minimum Path Sum	3	3	array	DP
	65	Valid Number	2	5	string	Math
	66	Plus One	1	2	array	Math
	67	Add Binary	2	4	string	Two Pointers
						Math
	68	Text Justification	4	2	string
	69	Sqrt(x)	4	4		Binary Search
	70	Climbing Stairs	2	5		DP
	71	Simplify Path	3	1	string	Stack
	72	Edit Distance	4	3	string	DP
	73	Set Matrix Zeroes	3	5	array
	74	Search a 2D Matrix	3	3	array	Binary Search
	75	Sort Colors	4	2	array	sort
						Two Pointers
	76	Minimum Window Substring	4	2	string	Two Pointers
	77	Combinations	3	4		combination
	78	Subsets	3	4	array	Recursion
						combination
	79	Word Search	3	4	array	DFS
	80	Remove Duplicates from Sorted Array II	2	2	array	Two Pointers
	81	Search in Rotated Sorted Array II	5	3	array	Binary Search
	82	Remove Duplicates from Sorted List II	3	3	linked list	Recursion
						Two Pointers
	83	Remove Duplicates from Sorted List	1	3	linked list
	84	Largest Rectangle in Histogram	5	2	array	Stack
	85	Maximal Rectangle	5	1	array	DP
						Stack
	86	Partition List	3	3	linked list	Two Pointers
	87	Scramble String	5	2	string	Recursion
						DP
	88	Merge Sorted Array	2	5	array	Two Pointers
						merge
	89	Gray Code	4	2		combination
	90	Subsets II	4	2	array	Recursion
						combination
	91	Decode Ways	3	4	string	Recursion
						DP
	92	Reverse Linked List II	3	2	linked list	Two Pointers
	93	Restore IP Addresses	3	3	string	DFS
	94	Binary Tree Inorder Traversal	4	3	tree	Recursion
					hashtable	morris
						Stack
	95	Unique Binary Search Trees II	4	1	tree	DP
						DFS
	96	Unique Binary Search Trees	3	1	tree	DP
	97	Interleaving String	5	2	string	Recursion
						DP
	98	Validate Binary Search Tree	3	5	tree	DFS
	99	Recover Binary Search Tree	4	2	tree	DFS
	100	Same Tree	1	1	tree	DFS
	101	Symmetric Tree	1	2	tree	DFS
	102	Binary Tree Level Order Traversal	3	4	tree	BFS
	103	Binary Tree Zigzag Level Order Traversal	4	3	queue	BFS
					tree	Stack
	104	Maximum Depth of Binary Tree	1	1	tree	DFS
	105	Construct Binary Tree from Preorder and Inorder Tr	3	3	array	DFS
					tree
	106	Construct Binary Tree from Inorder and Postorder T	3	3	array	DFS
					tree
	107	Binary Tree Level Order Traversal II	3	1	tree	BFS
	108	Convert Sorted Array to Binary Search Tree	2	3	tree	DFS
	109	Convert Sorted List to Binary Search Tree	4	3	linked list	Recursion
						Two Pointers
	110	Balanced Binary Tree	1	2	tree	DFS
	111	Minimum Depth of Binary Tree	1	1	tree	DFS
	112	Path Sum	1	3	tree	DFS
	113	Path Sum II	2	2	tree	DFS
	114	Flatten Binary Tree to Linked List	3	3	tree	Recursion
						Stack
	115	Distinct Subsequences	4	2	string	DP
	116	Populating Next Right Pointers in Each Node	3	3	tree	DFS
	117	Populating Next Right Pointers in Each Node II	4	2	tree	DFS
	118	Pascal's Triangle	2	1	array
	119	Pascal's Triangle II	2	1	array
	120	Triangle	3	1	array	DP
	121	Best Time to Buy and Sell Stock	2	1	array	DP
	122	Best Time to Buy and Sell Stock II	3	1	array	greedy
	123	Best Time to Buy and Sell Stock III	4	1	array	DP
	124	Binary Tree Maximum Path Sum	4	2	tree	DFS
	125	Valid Palindrome	2	5	string	Two Pointers
	126	Word Ladder II	1	1
	127	Word Ladder	3	5	graph	BFS
						shortest path
	128	Longest Consecutive Sequence	4	3	array
	129	Sum Root to Leaf Numbers	2	4	tree	DFS
	130	Surrounded Regions	4	3	array	BFS
						DFS
	131	Palindrome Partitioning	3	4	string	DFS
	132	Palindrome Partitioning II	4	3	string	DP