Algorithm -- Greedy

Greedy algorithm is not global optimal. It tries to do local optimal and believes that's good enough(skip to examine other solutions). Only certain problems can be solved by Greedy. It's practically used for suboptimal solution, when global optimal solution costs too much time or is too complex.


Examples are MeetingRoom scheduling Jump Game GasStation

Data Structure -- 4.3 Trie

Trie is a special tree with multiple children and each node saves one char.
It's special for word insert/search with fast speed O(k), k is the word length.

Trie Tree Wrapper must implement AddWord and FindWord operations. Its algorithm are almost fixed. Trie Node can be represented as

• Hash
• Array

Hash Trie and its operations Array Trie and its operations

Data Structure --- 5. Graph

Graph is used widely for complex modeling.

• Undirected vs Directed
• Cylic vs Acylic 

Without cycle and isolated multiple trees(forest), Graph becomes tree.

Graph can be represented as matrix or adjancecy list. The latter is more programming friendly. The adjancecy list can be represented in several ways

• List<List<T_vertex_data>>
• Map<vertex_data, List<T_vertex>>
• List<Node>, where Node class has List<T_vertex_data>

, where Map is complete graph, not need to build

Graph has two basic algorithms

• DFS
• BFS

, which can be used for traversal, Find Connectivity/Path.

Undirected Graph is basic.
NoCycle+IsTree+Not forest ?
DAG is particular interesting And DAG's Topological sort is powerful to solve scheduler dependencies problem

Algorithm -- Backtracking

Backtracking is a brute-force search algorithm with pruning. The main algorithm often uses DFS to go deep to try if the solution can stay true till the end to meet target.

A typical framework is

• Need a result list and levelList for each result
• The major loop will do scan over available elements(like Array, a group of arrays, set. etc.)
• The recursion needs to transfer level/pos information to next level

Some variations are frequently used

1. original data has dup or no dup ?  --> use standard (i>0 && n[i]==n[i-1]) to skip dup 
2. original data order is significant ? --> use full scan loop or incremental scan from pos+1
3. final result should be be ordered like non-descending ? -- sort first 
4. result can have dup, no dup inside ? --> use levelList.contains() to uniquify
5. track the current used pool ? visited[] flag vs hashset()
6. result must include all elements ? --> subset/combination vs permutation 

Typical example is combination, subset permutation Some famous ones are NQueen Break IP address PhoneLetterCombination

Data Structure -- 1. String & Array

String and Array are sequential data structure with index and direct access. String is a fundamental representation in program and can be converted to various other structure like Array, linked list. So often a string algorithm becomes array algorithm The classic example is strStr Serialization is a useful concept LongestPalindromSubstring There could be an array of string/substring CompareVersionNumber LongestCommonPrefix String carries a lot of coding details like RegularExpression matching SimplifyPath Text Justification. This is tricky for the match calculation Array algorithm is not difficult, but needs drawing a picture to ensure index are manipulated correctly. Rotate image Spiral Matrix Interesting algorithm also exists

Algorithm -- Dynamic Programming

DP is efficient and provide O(n) operation without recursion.

 It requires state transition equation to be identified (from n-2, n-1 to n) as well as correct base case (n=0, n=1). It's like Math induction.

It's often applied to combinatorics problem asking for total number.

DP has 1-DP, one dimension and 2-DP, two dimension transfer function.

Typical 1-D DP examples are climb stairs max subArray paint fence Typical 2-D examples are MinimumPathSum Unique path for robots Paint house Famous ones are Edit Distance Word Break

Data Structure -- 2. Linked List

Linked List is a sequence data structure like Array. It doesn't have index for fast query, but more flexible for insertion/deletion than Array. Single linked list is asked often as double linked list is more expensive even easier to do some manipulation.
Basic Linked List operations are find/insert/remove/shift/reverse/rotate.
Dummy Node is very useful for Java to retain the head.
remove remove N from end Rotate Reverse(whole, subchain, everyK etc.) IsPalindrome Swap More advanced operations are
find insertion of two linked list Detect Cycle Copy linked list with random pointers inside