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

Data Structure -- 3. HashMap

Unlike other sequential data structure(List, Array, String), Hash is not sequential(no order) without direct index access. But it provides map access, which is O(1). And its mapping is very flexible and key can be many things.

HashMap does two important usecases

• translate original set to a different value set
• The value normally has certain designed pattern for comparison
• partition a large set into subgroup. each subgroup shared the same key/signature.
• The value/subgroup can be a set for storage, comparison, output

Sometimes, bi-directional HashMap(two) can solve binding problems.
The HashMap translate usages are duplicates in a set/string/array, Palindrome, StringIsAnagram
The HashMap subgroup usages are below HashMap can also run multiple scans or bi-directional to handle complex logic

Data Structure -- 4.2 Binary Search Tree

Binary Search Tree is a special binary tree, where

• left child contains only nodes with value less than the parent node
• right child only contains nodes with values greater than or equal to parent

It's good for searching

This page has many basic insertion/deletion algorithms http://blog.jobbole.com/79305/
IsValidBST is fundamental Lowest Common Ancester is interesting.

Data Structure -- 4. Binary Tree

Binary Tree is a tree with each node has UP TO TWO leaves

• Full/Strict, every node except leaf nodes have two children
• Complete, every level except the last(left justified) is completely filled
• Perfect, every node except the leaf nodes have two children and all level are completely filled

Binary Tree is common data structure and base for many advanced ones. 

DFS and BFS are two broad traversal algorithms.

• DFS is divided into pre-order, inorder, postorder.They can be implemented as recursive(very simple) and non-recursive.
• BFS is non-recursive using queue

The basic DFS with and without recursion is here
PATHSUM from rootToleaf or anyPath illustrates the DFS variations The basic BFS without and with recursion is here. Some similar level order problem can be solved with BFS
Bottomup Zigzag Rightview Right next pointer Some Binary Tree basic tools are useful like MaxDepth, MinDepth, Height, SameTree, isSymmetric isBalanced can be speeded up with the help of

Algorithm -- Two Pointers

Two pointers is an useful algorithm to deal with Array and String and Linked-List

• Actually, most linked list problem can be solved by this algorithm
• Two pointers is one basic algorithm and used widely. One typical origination is quickSort. 

A few subtypes

• two pointers move from left to right, slide window 
• two pointers move from left, right to middle 
• two pointers control two array or list, typically merging

Merge Two Sorted Array
Replicate Duplicates from Single Sorted Array
Reverse Words in a String
Rotate Array

Algorithm -- Binary Search

Binary search is one essential algorithm type. It operates on

• array
• sorted

Basic Binary Search has recursion and non recursion implementation. Normally, non recursion is simpler to control and vary for many derived problems

Here is the basic form


Search Insert Position
\ Search in Rotated Sorted Array
Find Square root of an integer
Search in a 2D matrix
Search for a range

[Leetcode] LRU Cache (Design)

[Problem]

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

[Algorithm]

hashmap + linkedlist(for fast LRU update)

[Code]

Python

Algorithm -- 101

Algorithm is one foundation of compute program.

The well known algorithm books are

• TAOCP: The art of computer programming
• https://en.wikipedia.org/wiki/The_Art_of_Computer_Programmin
• The algorithm design manual, 2nd
• http://www.algorist.com/ 
• Introduction to algorithms, 3rd
• https://mitpress.mit.edu/index.php?q=books/introduction-algorithms 
• Algorithm, 4th
• http://algs4.cs.princeton.edu/home/ 

And, of course, this concise and classic book:

• http://www.amazon.com/Programming-Pearls-2nd-Edition-Bentley/dp/0201657880

This small visualization tool helps a bit too

• http://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Algorithm Design Techniques

• Data structure based
• Algorithm based
• Modeling: the art of abstracting a real-world application into a clean probelm suitable for algorithmic attack

Data Structure

• Linked
• String, Array, http://beyondcoder.blogspot.com/2015/12/data-structure-string-array.html
• Linked List, http://beyondcoder.blogspot.com/2015/12/data-structure-linked-list.html
• Stack and Queue,
• Map, HashMap, TreeMap, http://beyondcoder.blogspot.com/2015/12/data-structure-hashmap.html
• Set
• Binary Tree, http://beyondcoder.blogspot.com/2015/12/algorithm-binary-tree.html
• Binary Search Tree, http://beyondcoder.blogspot.com/2015/12/algorithm-binary-search-tree.html
• Trie, https://www.blogger.com/blogger.g?blogID=2861811477507969695#allposts
• Priority queue, Heap
• Graph: undirected, directed, acyclic, http://beyondcoder.blogspot.com/2015/12/data-structure-5-graph.html
• Specialized data structure: like bloom filter

Algorithm classification

1. Divide-and-conquer
2. Dynamic Programming, http://beyondcoder.blogspot.com/2015/12/algorithm-dynamic-programming.html
3. Backtracking, http://beyondcoder.blogspot.com/2015/12/algorithm-backtracking.html
4. Greedy Algorithm, http://beyondcoder.blogspot.com/2015/12/algorithm-greedy.html
5. Randomized Algorithm