Tips on Using Eclipse Effectively

Tips on Using Eclipse Effectively
Useful Eclipse Shortcut Keys



ALT + Left/Right ArrowMove backward/forward in the editor navigation history
CTRL+OShow the quick outline for the editor input
CTRL+KFind next item, no need to ctrl+f, type some words, then search
CTRL+1Activates the quick fix
CTRL+SHIFT+TOpen Type
CTRL+SPACEContent Assist
ALT+/Word completion
ALR+SHIFT+RRename the selected element
ALT+SHIFT+MExtract statements into a new method and use the new method
Ctrl + LGo To Line
CTRL+TShow quick hierarchy of the selected element
CTRL + SHIFT + FFormat code
CTRL+SHIFT+OOrganize imports
Ctrl+Shift+XChange the selection to upper case, useful in declare final variable
Ctrl+Shift+YChange the selection to lower case
Ctrl+Shift+HOpen a type in the type hierarchy view
Ctrl+Shift+SSave all current contents
Ctrl+Shift+WClose all editors
Ctrl+Shift+GSearch for references to the selected element in the workspace
CTRL+EShow a list of all open editors
CTRL + DDelete row
CTRL+MToggle maximize/restore state of active view or editor
Others:
CTRL+SHIFT+U    Shows the Occurrences in File quick menu
Ctrl+Shift+R        Open Resources
CTRL + I               Corrects indentation
Ctrl+M                  Maximize Active View or Editor
Ctrl+Shift+Space
Context Information, If typing a method call with several parameters use this to show the applicable parameter types.
Alt+Left/Right Backward/Forward History
CTRL + I         Corrects indentation
CTL + N            Open new type wizard
CTRL + J           Incremental search
CTRL + SHIFT + L Shows you a list of your currently defined shortcut keys
CTRL+F6          Use to move between open editors
CTRL+F7          Move between views
CTRL+F8          Move between perspectives
To configure the shortcut key, click Window --> Preferences --> General --> Keys


Associate editors with file types:
Window -> Preferences -> General -> Editors -> File Associations

Find: ^\s*\n
Replace with: (empty)



Eclipse plugins:
Code quality:
Checkstyle: http://eclipse-cs.sourceforge.net/update
It is used to enforce Coding Standards in Java Project, such as Naming conventions, Coding problems, Best Practices.


PMD http://pmd.sf.net/eclipse
PMD focuses more on preemptive defect detection.


FindBugs http://findbugs.cs.umd.edu/eclipse/
FindBugs concentrates on detecting potential bugs and performance issues.
Klocwork: http://developer.klocwork.com
Klocwork is aimed at improving software security, quality, and reliability. It is not free, but we can get 30 days free trail. And it is really very cool.


Mylyn: http://www.eclipse.org/mylyn/
Mylyn can integrate with issue management systems such as Bugzilla, and it also provides context management, which can hide much of the detail of projects that is irrelevant to the task at hand.
Mylyn is very helpful, especially your main job is to fix defects, or focus on one component of a big project.


ShellEd: http://sourceforge.net/projects/shelled/
EPIC - Perl Editor and IDE for Eclipse http://e-p-i-c.sf.net/updates
The PyDev Update Site http://pydev.sourceforge.net/updates/
Groovy Eclipse plugin http://dist.codehaus.org/groovy/distributions/update/
Aptana Studio http://update.aptana.com/install/studio/3.2/
http://www.aptana.com


Problem
Recently, I re-downloaded and reinstalled jdk, and Eclipse always shows this error:
'UnsupportedEncodingException: GBK'. After google search, on http://dev.eclipse.org/newslists/news.eclipse.tools/msg30710.html,
I found out this is because I installed a JRE only for US English, and I should choose to download and install Multi-language JRE.

Problem:
When we save file, it may print out the error "Some characters can not be mapped using GBK character encoding".
The solution is to change file encoding to 'utf-8':
Select Window -> Preferences ->General
Select  Workspace , set Text file encoding to 'utf-8'.
Select Content Types, set Default encoding to 'utf-8'

Ignore white space when compare two files in Eclipse IDE
When compare two files in Eclipse, many times lines differ only in white spaces, and we don't want to notice this minor difference.
Solution:
Select Window -> Preference -> Compare/Path, and in 'General' tab, select the checkbox --'Ignore white space'.


Reference:
http://www.javaprogrammingforums.com/eclipse/19-useful-eclipse-shortcut-keys.html
http://www.rossenstoyanchev.org/write/prog/eclipse/eclipse3.html
http://tkramar.blogspot.com/search/label/eclipse
Java Power tools safari online book

Hacking CMVC Eclipse Plugin

Hacking CMVC Eclipse Plugin

    I know CMVC is somewhat relic of last century, and little people use it now, even little knows what CMVC(Configuration Management Version Control) is and what it means. IBM has terminated CMVC sales and support after IBM acquired Rational Software.

    Unfortunately our project uses it, and CMVC Eclipse Plugin can’t work.

    When use CMVC plugin, and open "Error Log" view, we may see the exception “Unhandled event loop exception”, and click it; we will see a dialog opened, reporting:

javax.xml.parsers.FactoryConfigurationError: Provider org.apache.xerces.jaxp.SAXParserFactoryImpl not found

at javax.xml.parsers.SAXParserFactory.newInstance(Unknown Source)

at com.ibm.sdwb.cmvc.util.XMLSAXParser.<init>(XMLSAXParser.java:57)

at com.ibm.sdwb.cmvc.client.api.CommandXMLHandler.setupRpcParser(CommandXMLHandler.java:147)

at com.ibm.sdwb.cmvc.client.api.CommandXMLHandler.<init>(CommandXMLHandler.java:122)

at com.ibm.sdwb.cmvc.client.api.CommandFactory.<init>(CommandFactory.java:59)

at com.ibm.sdwb.cmvc.client.api.CommandFactory.getInstance(CommandFactory.java:86)

at com.ibm.sdwb.cmvc.client.api.PasswordAuthentication.login(PasswordAuthentication.java:304)


    This is because of eclipse peculiar classloader mechanism. com.ibm.sdwb.cmvc.client.api plugin can't load classes in xerces.jar, and also many other CMVC plugins need access classes in xerces.jar, so we need add xerces.jar to CMVC’s common plugin

– ‘com.ibm.sdwb.cmvc.client.api’ and ‘com.ibm.sdwb.cmvc.core’, which many other CMVC plugins include them in ‘Require-Bundle’ section, and then export packages of xerces.jar, so other CMVC plugin can use classes in xerces.jar.

     We can use org.apache.xerces_*.jar included in eclipse directly, add it to Require-Bundle section, and export its all packages in Export-Package section.

    So we need edit MANIFEST.MF of ‘com.ibm.sdwb.cmvc.client.api’. Just add the following red text to MANIFEST.MF of ‘com.ibm.sdwb.cmvc.client.api’.

Manifest-Version: 1.0

……………..

Require-Bundle: org.apache.xerces

Export-Package: …

javax.xml.parsers,

org.apache.html.dom,

org.apache.wml,

org.apache.wml.dom,

org.apache.xerces.dom,

org.apache.xerces.dom.events,

org.apache.xerces.domx,

org.apache.xerces.framework,

org.apache.xerces.jaxp,

org.apache.xerces.msg,

org.apache.xerces.parsers,

org.apache.xerces.readers,

org.apache.xerces.utils,

org.apache.xerces.utils.regex,

org.apache.xerces.validators.common,

org.apache.xerces.validators.datatype,

org.apache.xerces.validators.dtd,

org.apache.xerces.validators.schema,

org.apache.xml.serialize,

org.w3c.dom,

org.w3c.dom.events,

org.w3c.dom.html,

org.w3c.dom.ranges,

org.w3c.dom.traversal,

org.xml.sax,

org.xml.sax.ext,

org.xml.sax.helpers

Eclipse-LazyStart: true


    Also please notice that eclipse plugin requires extra blank line in the end of MANIFEST.MF, don't delete it.

    Then run "eclipse -clean" in the command line to restart eclipse.

    When we open Help -> Software Updates -> Manage Configuration dialog in eclipse, we would see the following error dialogue:

    

    I am not sure whether this would affect CMVC functionality, but it is better to fix it.

    I found that this is due to the inconsistent plugin version declaration between CMVC Features and CMVC Plugins.

    In CMVC Plugins MANIFEST.MF declares plugin version as:"Bundle-Version: 5.3.3.qualifier", however In CMVC Features, feature.xml (under %Eclipse_Home%\CMVC_related_features\feature.xml) declares their included-plugins as :"< plugin version="5.3.3" id="com.ibm.sdwb.ui"/>",

Eclipse Plugin version is compared by all components-the major, minor, micro, and the qualifier, obviously it is inconsistent.

     The solution is to modify all the cmvc-related features' feature.xml file, change plugin version they include to "5.3.3.qualifier", and notice that some features-for example com.ibm.sdwb.cmvc.all_5.3.3 feature (<includes id="com.ibm.sdwb" version="5.3.3"/>)- includes other CMVC feature, don't change them.

     After this, the error dialogue should disappear.

     By the way when meet problems with eclipse, we can find logs in eclipse's Error Log view, or in %WorkSpace_Home%/.metadata/.log file.


Advanced Data Structures


Interval tree
http://www.davismol.net/2016/02/07/data-structures-augmented-interval-tree-to-search-for-interval-overlapping/
- augmented self-balancing bst: low, high, max
- logn: add/Remove(interval), overlapping(x)

Google – Toggle Problem
https://reeestart.wordpress.com/2016/06/24/google-toggle-problem/

Algorithm Problems Practices

logn
- bisection
- divide and conquer

X. DP
O(1) space - in place, reuse the input
-- multiple dp relations
- find sub-problems and relations
- dp: [i, j]; or dp[len-1] just start/or end
always think whether there is dp solution
dp[i] dp[i-1]
dp[i]  dp[j] 0<j<i
[], [][], or map

X. Kadane's algorithm
- dp, two pointers, scan, track and update local that includes a[i]
LeetCode 53 - Maximum Subarray
2. dp: dp(A, i) = dp(A, i - 1) > 0 ? dp(A, i - 1) : 0 + A[i];
the maxSubArray for A[0:i ] which must has A[i] as the end element
3. Divide and Conquer - nlogn

Maximum circular subarray sum

Max sum subsequence with non-consecutive elements
max_including(i) = max{max_excluding(i-1)+a[i], a[i]}
max_excluding(i) = max{max_including(i-1), max_excluding(i-1)}

Maximum Product Subarray
localMax, localMin, if(a[i] > 0) else


find the maximum number zeros in an array with one flip of a subarray allowed. A flip operation switches all 0s to 1s and 1s to 0s.

find maximum number of set bits after flipping a single contagious segment of bits

X. Knapsack
LeetCode 416 - Partition Equal Subset Sum
1. dp[target+1] or [nums.length+1][target+1]
dp[j] = dp[j] || dp[j - nums[i]]
https://discuss.leetcode.com/topic/62312/java-solution-similar-to-backpack-problem-easy-to-understand

X. DP
LintCode - Copy Books

LeetCode 474 - Ones and Zeroes
dp = new int[m + 1][n + 1];
dp[i][j] = Math.max(1 + dp[i-count[0]][j-count[1]], dp[i][j]);

LeetCode 446 - Arithmetic Slices II - Subsequence
- HashMap<Integer, Integer>[] dp
map[i].put(diff, map[i].get(diff)) + map[j].get(diff)) + 1);

LeetCode 375 - Wiggle Subsequencelink
return the length of the longest subsequence that is a wiggle sequence
up[i] - considering i​th element as the last element of the wiggle subsequence and ending with a rising wiggle.
down[i]
if nums[i] > nums[i-1] up[i] = down[i-1]+1 down[i]=down[i-1]
else if nums[i] < nums[i-1]  down[i]=up[i-1]+1 up[i] = up[i-1]
else down[i]= down[i-1] up[i] = up[i-1]
-- space optimization, only use up and down
2. Greedy

Leetcode 44 - Wildcard Matching
with support for '?' and '*'.
dp[s.length() + 1][p.length() + 1]
dp[i[j]: the first i characters in string s matches the first characters of string p.
dp[0][0] = true;
dp[i][0] = false;
dp[0][j] = dp [0][j - 1] if p.charAt(j - 1) == '*'
-- If p.charAt(j - 1) != '*', then dp[i][j] = dp[i - 1][j - 1] if s.charAt(i) == p.charAt(j) || p.charAt(j) == '?' (else false)
-- If p.charAt(j - 1) == '*', then
-- dp[i][j]
     = dp[i][j - 1] || // Match 0 character
     = dp[i - 1][j] // Match any sequence of characters
O(n) space - https://discuss.leetcode.com/topic/10794/my-java-dp-solution

LeetCode 10 - Regular Expression Matching: . and *
'*' Matches zero or more of the preceding element.
- DFS+Cache: dp[i][j] or DP
https://discuss.leetcode.com/topic/40371/easy-dp-java-solution-with-detailed-explanation
https://discuss.leetcode.com/topic/31974/java-4ms-dp-solution-with-o-n-2-time-and-o-n-space-beats-95
1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*': 
   here are two sub conditions:
               1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
               2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                              dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                           or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                           or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty

Leetcode 139 - Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
1. DP: O(n^2)
Get words minLen, maxLen
boolean [] dp = new boolean[n+1];
dp[0] = true ;
dp[i] = dp[j] && dict.contains(sentences.subString(j,i)) 0<j<i

// Use trie to check whether subString is a word
2. DFS + Cache
3. BFS:

Word Break II
https://leetcode.com/discuss/91894/java-6ms-simple-solution-beating-88%25
http://www.jiuzhang.com/solutions/word-break-ii/
- avoid to use substring
boolean[][] isWord
boolean[] possible

LeetCode 287 - Perfect Squares
dp(i) = min{1+dp(i-j*j)}
https://discuss.leetcode.com/topic/26400/an-easy-understanding-dp-solution-in-java
bfs -  q.offer(0); visited.add(0);
https://leetcode.com/discuss/58056/summary-of-different-solutions-bfs-static-and-mathematics

https://discuss.leetcode.com/topic/2545/a-solution-using-bfs/6
The vertices of the graph are simply the positions of the first characters of the words and each edge actually represents a word

Lintcode: K Sum I
http://www.cnblogs.com/yuzhangcmu/p/4279676.html
int[][][] D = new int[len + 1][k + 1][target + 1];
D[i][j][t] = D[i - 1][j][t];
if (t - A[i - 1] >= 0) {
    D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];
}

space op: int[][] D = new int[k + 1][target + 1];

Lintcode: k Sum II
- DFS

LeetCode 97 - Interleaving String
dp[i][j]  =
str3.charAt(i + j) == str1.charAt(i) && dp[ i - 1][j] ||
str3.charAt(i + j) == str2.charAt(j) && dp[i][j - 1]

LeetCode 132 - Palindrome Partitioning II
http://happycoding2010.blogspot.com/2015/10/leetcode-132-palindrome-partitioning-ii.html
Return the minimum cuts needed for a palindrome partitioning of s
isPal[i][j] store if s[i..j] is palindrome or not. res[j] is the min cut of s[0..j].

LeetCode 241 - Different Ways to Add Parentheses
DP: https://discuss.leetcode.com/topic/26076/java-recursive-9ms-and-dp-4ms-solution
- split string first
- dp[i][j] stores all possible results from the i-th integer to the j-th integer (inclusive)
- ArrayList<Integer>[][] dp
DFS: divide and conquer + cache
https://discuss.leetcode.com/topic/19901/a-recursive-java-solution-284-ms/12

LeetCode 446 - Arithmetic Slices II - Subsequence
T(i, d) = summation of (1 + T(j, d)) as long as 0 <= j < i && d == A[i] - A[j]
Map<Integer, Integer>[] map = new Map[A.length];

LintCode 395 - Coins in a Line II
dp[i] means the largest value you(the first player) can get when you start from values[i]
dp[i] = values[i] + Math.min(dp[i+2], dp[i+3]);
dp[i] = Math.max(dp[i], values[i] + values[i+1] + Math.min(dp[i+3], dp[i+4]));


LeetCode 73 - Unique Paths II
if some obstacles are added to the grids. How many unique paths would there be
dp[i][j] = dp[i−1][j]+dp[i][j−1] if grid[i][j]=0
O(1) space - in place, reuse the input
https://discuss.leetcode.com/topic/4987/java-solution-using-dynamic-programming-o-1-space
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
if(obstacleGrid[i][j] == 1)
    obstacleGrid[i][j] = 0;

LeetCode 72 - Edit Distance
f(i, j) = f(i - 1, j - 1)
f(i, j) = 1 + min { f(i, j - 1), f(i - 1, j), f(i - 1, j - 1) }

LeetCode - 403 Frog Jump
DP https://discuss.leetcode.com/topic/59423/simple-easy-to-understand-java-solution
map = new HashMap≪Integer, HashSet≪Integer>>(stones.length);
List≪HashSet≪Integer>> dp
DFS + cache
https://discuss.leetcode.com/topic/59439/straight-forward-9ms-7-line-c-solution-with-explanation

LeetCode 97 - Interleaving String
1. DP:
dp[0][0] = true;
dp[0][j] = str3.charAt(j) == str2.charAt(j)
dp[i][0] = str3.charAt(i) == str1.charAt(i)
2. BFS
https://discuss.leetcode.com/topic/6562/8ms-c-solution-using-bfs-with-explanation

X. BFS
When to use?
- to find minimum steps
- two-end BFS, multi-end bfs
- BFS + PriorityQueue

LeetCode 417 - Pacific Atlantic Water Flow
bfs or dfs
https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean
if (pacific[i][j] && atlantic[i][j]) res.add(new int[] {i, j});

LeetCode - Word Ladder I
find the length of shortest transformation sequence from start to end
Two-end BFS
https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms
beginSet.add(beginWord);
endSet.add(endWord);
HashSet≪String> visited
if (beginSet.size() > endSet.size()) beginSet, endSet = endSet, beginSet;
if (endSet.contains(target)) return len + 1;

LeetCode Word Ladder II
https://discuss.leetcode.com/topic/17975/super-fast-java-solution-two-end-bfs
http://www.jiuzhang.com/solutions/word-ladder-ii/
http://www.programcreek.com/2014/06/leetcode-word-ladder-ii-java/
LinkedList≪WordNode> queue
https://discuss.leetcode.com/topic/2857/share-two-similar-java-solution-that-accpted-by-oj
Map≪String,List≪String>> map: key is a word, the list is the word's pre words.
or:
unvisited = new HashSet≪String>(dict);
visited = new HashSet≪String>();

unvisited.removeAll(visited);
visited.clear();

LeetCode 407 - Trapping Rain Water II
https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue
BFS + PriorityQueue

LeetCode [317] Shortest Distance from All Buildings
- do not go into a land, if it is not accessible by at least one of previous buildings.

LeetCode 286 - Walls and Gates
Fill each empty room with the distance to its nearest gate.
- Multi end bfs - O(n^2)
- Naive BFS or dfs - O(n^4)

LeetCode 433 - Minimum Genetic Mutation
https://discuss.leetcode.com/topic/65780/java-solution-using-bfs

Leetcode 200: Find the number of islands
- bfs, dfs, union-find
- number of lakes
- different shapes of number Island
http://www.1point3acres.com/bbs/thread-175393-1-1.html

LeetCode 247 - Strobogrammatic Number II
Find all strobogrammatic numbers that are of length = n.
- Use char[] to avoid string concatenation
iterative, bfs - https://discuss.leetcode.com/topic/28990/simple-java-solution-without-recursion
dfs - https://discuss.leetcode.com/topic/21579/accepted-java-solution-using-recursion
https://discuss.leetcode.com/topic/20733/my-concise-java-solution-using-dfs
public void findStrobogrammaticHelper(List res, char[] a, int l, int r)

LeetCode 248 - Strobogrammatic Number III
Count the total strobogrammatic numbers that exist in the range of low <= num <= high
https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code

X. DFS
- Backtrack: don't forget to clear state
- dfs+cache
LeetCode 247 - Strobogrammatic Number II
Find all strobogrammatic numbers that are of length = n.
iterative, bfs - https://discuss.leetcode.com/topic/28990/simple-java-solution-without-recursion
Use char[] to avoid string concatenation
dfs - https://discuss.leetcode.com/topic/21579/accepted-java-solution-using-recursion
https://discuss.leetcode.com/topic/20733/my-concise-java-solution-using-dfs
public void findStrobogrammaticHelper(List<String> res, char[] a, int l, int r)

LeetCode 248 - Strobogrammatic Number III
Count the total strobogrammatic numbers that exist in the range of low <= num <= high
https://discuss.leetcode.com/topic/44718/java-1ms-solution-with-comments-in-the-code
if (i== low_len || i== high_len) strobogrammaticInRangeSameDigits(i, 0, i-1, 0); else strobogrammaticDigit+=counts(i,i);

LeetCode 212 - Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
- dfs + trie
https://discuss.leetcode.com/topic/33246/java-15ms-easiest-solution-100-00/
- pass TrieNode

LeetCode 395 - Longest Substring with At Least K Repeating Characters
- split by badChars and dfs
https://tech.liuchao.me/2016/09/leetcode-solution-395/
https://discuss.leetcode.com/topic/57265/java-d-c-solution

Leetcode 291 Word Pattern II
Map<Character, String> forwardMap, invertedMap

LeetCode124 - Word Search
find if the word exists in the grid
https://discuss.leetcode.com/topic/7907/accepted-very-short-java-solution-no-additional-space/39

LeetCode 22 – Generate Parentheses
generate all combinations of well-formed parentheses.
helper(List res, StringBuilder sb, int open, int close, int n)
DFS: https://discuss.leetcode.com/topic/5866/my-accepted-java-solution
-- dfs(ArrayList<String> result, String s, int left, int right)
DFS+cache
https://discuss.leetcode.com/topic/33127/java-easy-to-understand-recursive-dp-method-with-explanations/
helper(int n, List<String>[] lists)

BSF, DP
f(n) = (f(0))f(n-1) + (f(1))f(n-2) + ... + (f(n-2))f(1) + (f(n-1))f(0)
https://discuss.leetcode.com/topic/3474/an-iterative-method

LeetCode 320 - Generalized Abbreviation
DFS/Backtracking
https://discuss.leetcode.com/topic/32765/java-14ms-beats-100
Divide &Conquer
Bit String/Mark
- 2^n combinations

LeetCode 329. Longest Increasing Path in a Matrix
- DFS+Cache: dfs(int[][] matrix, int i, int j, int[][] memo)

LeetCode 267 - Palindrome Permutation II
void getPerm(List<Character> list, String mid, boolean[] used, StringBuilder sb, List<String> res)
private void helper(char[] array, List<String> result, Map<Character, Integer> map, int left, int right)

LeetCode - Subsets
res = new ArrayList<List>();
3. bit string
Math.pow(2, n)
if (((1 << j) & i) != 0) subset.add(nums[j]);

LeetCode 46 - Permutations
LeetCode 47 - Permutations II
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

Google interview - max vacation days
Google – Get Some Beer
https://reeestart.wordpress.com/2016/06/28/google-get-some-beer/

X. Divide and Conquer
- subproblems
LeetCode 50 - Pow(x, n)
Google – Power Sum
return sum of n^0 + n^1 + … + n^n.
https://reeestart.wordpress.com/2016/06/10/google-power-sum/

X. merge sort
need one extra array - no need to create tmp array every time
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Sorting%20Algorithms/code/MergeSort.java
void merge(Comparable[ ] a, Comparable[ ] tmp, int left, int right, int rightEnd )

LeetCode 218 - The Skyline Problem
LeetCode 315 - Count of Smaller Numbers After Self
LeetCode 327 - Count of Range Sum

Count Inversions in an array

Maximum Sum Path in Two Arrays
result += max(sum1, sum2); sum1=sum2=0;

Merge k sorted array
Find a permutation that causes worst case of Merge Sort

X. Quick sort/select
LeetCode 215 - Kth Largest Element in an Array
LeetCode 148 - Sort List
quick sort - partition, sort, concat
merge sort - findMiddle sort left/right, merge
http://www.chenguanghe.com/quicksort-for-linklist/

X. Slide Window
LeetCode 424 - Longest Repeating Character Replacement
you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters
https://discuss.leetcode.com/topic/63494/java-12-lines-o-n-sliding-window-solution-with-explanation
https://discuss.leetcode.com/topic/63471/java-sliding-window-easy-to-understand
(length of substring - number of times of the maximum occurring character in the substring) <= k
if(count(ch) > k){  ch[str[j] - 'A']--; break; }

LeetCode 30 - Substring with Concatenation of All Words
https://discuss.leetcode.com/topic/6617/an-o-n-solution-with-detailed-explanation/11
countMap, curMap, foundCount,
toFindMap, foundMap
O(KN)
2. trie

LeetCode 3 - Longest Substring Without Repeating Characters
https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation/
HashMap<Character, Integer> map - chracter -> last position
if (map.containsKey(s.charAt(i))) start = Math.max(start,map.get(s.charAt(i))+1);

LeetCode 340 - Longest Substring with At Most K Distinct Characters
https://discuss.leetcode.com/topic/41671/15-lines-java-solution-using-slide-window
follow up - stream
https://discuss.leetcode.com/topic/48827/java-o-nlogk-using-treemap-to-keep-last-occurrence-interview-follow-up-question

LeetCode 438 - Find All Anagrams in a String
- map = new int[256]; int count


LeetCode 67 - Minimum Window Substring
Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).
https://leetcode.com/discuss/90376/o-n-5ms-java-solution-beats-93-18%25
Map<Character, Integer> needToFill, hasFound

http://www.geeksforgeeks.org/find-zeroes-to-be-flipped-so-that-number-of-consecutive-1s-is-maximized


X. Two pointers
3Sum
- presort, O(N^2)
- how to avoid duplicate results
https://discuss.leetcode.com/topic/28857/easiest-java-solution

3Sum Smaller
https://discuss.leetcode.com/topic/23421/simple-and-easy-understanding-o-n-2-java-solution
nums[i] + nums[j] + nums[k] < target
count += right-left;

3Sum Closest
if (sum <= target) j++; else k--;

X. Trie
- use trie so no need to scan every candidate(O(n))
LeetCode 421 - Maximum XOR of Two Numbers in an Array
- use bit trie for int
- children = new Trie[2];
https://discuss.leetcode.com/topic/63207/java-o-n-solution-using-trie
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
2. 32n
https://discuss.leetcode.com/topic/63213/java-o-n-solution-using-bit-manipulation-and-hashmap
if(set.contains(tmp ^ prefix)) max = tmp;

LeetCode 212 - Word Search II

logN related
X. Binary search/BiSection
- use bisection when it's difficult to find correct value, but easy to verify whether a value is correct
- split to half
LeetCode 222 -  Count Complete Tree Nodes
O(log(n)^2) https://discuss.leetcode.com/topic/15533/concise-java-solutions-o-log-n-2

LeetCode 287 - Find the Duplicate Number
1. nlogn - binary search/bisection
https://discuss.leetcode.com/topic/25580/two-solutions-with-explanation-o-nlog-n-and-o-n-time-o-1-space-without-changing-the-input-array/2
2. O(n)
- graph: index -> as graph
- find cycle in linkedlist
http://keithschwarz.com/interesting/code/?dir=find-duplicate
https://discuss.leetcode.com/topic/18864/simple-java-solution-in-o-n-without-extra-space
3. 32n
https://discuss.leetcode.com/topic/38493/o-32-n-solution-using-bit-manipulation-in-10-lines

LeetCode 410 - Split Array Largest Sum
minimize the largest sum among these m subarrays.
bisection - https://discuss.leetcode.com/topic/61324/clear-explanation-8ms-binary-search-java

LeetCode 287 - Find the Duplicate Number
1. bisection - long*n
https://discuss.leetcode.com/topic/25580/two-solutions-with-explanation-o-nlog-n-and-o-n-time-o-1-space-without-changing-the-input-array
2. O(n)
- index->value graph subproblem
- find cycle in linkedlist
http://keithschwarz.com/interesting/code/?dir=find-duplicate
https://discuss.leetcode.com/topic/25685/java-o-n-time-and-o-1-space-solution-similar-to-find-loop-in-linkedlist

LintCode - Copy Books
Divide A into k or fewer partitions, such that the maximum sum over all the partitions is minimized.
http://sidbai.github.io/2015/07/25/Copy-Books/
http://www.geeksforgeeks.org/find-minimum-time-to-finish-all-jobs-with-given-constraints/
K people to copy books with different pages, return the number of smallest minutes need to copy all the books.
1. dp - minutes[i][j] = min( max( minutes[i-1][t], sum(t+1, j) )
- O(n^2 * k)
2. dp - O(n * k)
3. bisection - nlg(sum/k)
https://github.com/iFighting/Lintcode/blob/master/Java/Copy-Books.java

Codility: Lesson 12 Min Max Division
https://codility.com/programmers/lessons/14-binary_search_algorithm/
int left = max, right = sum;

Jobdu-1534
kth sum pairs from array a and b
http://www.acmerblog.com/offer-google-2-1173.html

X. Using Binary search tree
LeetCode 327 - Count of Range Sum
Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
1. Merge Sort
2. Binary search tree
private class TreeNode {
    long val = 0;
    int count = 1;
    int leftSize = 0;
    int rightSize = 0;
    TreeNode left = null;
    TreeNode right = null;
    countSmaller(TreeNode root, long val)
    countLarger(TreeNode root, long val)
    private int rangeSize(TreeNode root, long lower, long upper) {
        int total = root.count + root.leftSize + root.rightSize;
        int smaller = countSmaller(root, lower);    // Exclude everything smaller than lower
        int larger = countLarger(root, upper);      // Exclude everything larger than upper
        return total - smaller - larger;
    }
}
for(int i = 1; i < sums.length; i++) {
    output += rangeSize(root, sums[i] - upper, sums[i] - lower);
    insert(root, sums[i]);
}

LeetCode 315 - Count of Smaller Numbers After Self
1. Binary search tree
https://leetcode.com/discuss/73762/9ms-short-java-bst-solution-get-answer-when-building-bst
class TreeNode{
    int smallerCount;
    int val;
    TreeNode left;
    TreeNode right;
}
2. Merge sort
http://algobox.org/count-of-smaller-numbers-after-self/
class Tuple {
    public int val;
    public int idx;
}
3. Use TreeSet
https://discuss.leetcode.com/topic/31422/easiest-java-solution/12

Binary search
LeetCode 153 - Find the minimum element in a sorted and rotated array
mid = low + (high - low) / 2;
Compare num[mid] with num[high]

LeetCode 33 - Searching an Element in a Rotated Sorted Array

LeetCode 162 - Find Peak Element: num[i] ≠ num[i+1]
- Compare mid with mid+1
nums[left - 1] < nums[left] && nums[right] > nums[right + 1]
while (right - left > 1) {
    int mid = left + (right - left) / 2;
    if (nums[mid] < nums[mid + 1]) {
        left = mid + 1;
    } else {
        right = mid;
    }
}
return (left == N - 1 || nums[left] > nums[left + 1]) ? left : right;

Bisection
Given a result, it is easy to test whether it is valid or not.
LeetCode 410 - Split Array Largest Sum
- binary(nums, m, sum, max);
LeetCode 367 - Valid Perfect Square

X. Interval
- First sort these intervals somehow
- Think as different events - start, end
- sort interval + greedy
- merge interval

LeetCode 218 - The Skyline Problem
- (start/end, height) tuple, set the start segment as negative height or Edge:(x, height, isStart)
- sort interval
- TreeMap<Integer, Integer> heightMap: key is the height, value is the count
- prevHeight, currHeight = heightMap.firstKey();
heightMap = new TreeMap<>(Collections.reverseOrder());
heightMap.put(0,1);
pq = new PriorityQueue<>((a, b) -> (b - a));
pq.offer(0);
https://discuss.leetcode.com/topic/38065/java-solution-using-priority-queue-and-sweepline/
http://www.programcreek.com/2014/06/leetcode-the-skyline-problem-java/
https://discuss.leetcode.com/topic/22482/short-java-solution

LeetCode 56 - Merge Intervals
- Sort the intervals based on increasing order of starting time
- if prev.end >= curr.start  prev = merged else result.add(prev); prev = curr;

LeetCode 253 - Meeting Rooms II
https://discuss.leetcode.com/topic/35253/explanation-of-super-easy-java-solution-beats-98-8-from-pinkfloyda
- int[] starts, ends

Use TreeMap to store intervals
LeetCode 352 - Data Stream as Disjoint Intervals
- TreeMap<Integer, Interval> treeMap: key is the start point
- lowerKey(), higherKey()

LettCode 452 - Minimum Number of Arrows to Burst Balloons
- sort interval and greedy
https://discuss.leetcode.com/topic/66709/c-easy-understood-solution-sort/

LeetCode 435 - Non-overlapping Intervals
- sort interval by end
https://discuss.leetcode.com/topic/65828/java-solution-with-clear-explain

LeetCode 436 - Find Right Interval
TreeMap<Integer, Integer> intervalMap: key is the start, value is the index
- first put all intervals to the map: sorted by start
- intervalMap.ceilingEntry(intervals[i].end);

Google – Maximum Time Range Overlaps
https://reeestart.wordpress.com/2016/07/02/google-maximum-time-range-overlaps/

Google - remove alarm
https://reeestart.wordpress.com/2016/06/30/google-remove-alarm/
hash map - map priority to set of alarm id
max priority heap - PriorityQueue<Integer>

Google – Find a Path Among Circles
O(n^2) - https://reeestart.wordpress.com/2016/07/02/google-find-a-path-among-circles/


Bucket
LeetCode - 220 Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
slide window + bucket
https://leetcode.com/discuss/38206/ac-o-n-solution-in-java-using-buckets-with-explanation
https://discuss.leetcode.com/topic/27608/java-python-one-pass-solution-o-n-time-o-n-space-using-buckets/
https://leetcode.com/discuss/68090/easy-ac-solution-using-treeset-long-in-java

X. Ordered Stack
LeetCode 42 - Trapping Rain Water
1. Two Pointers
comapre height[left] and height[right]
2. Left and right array
int[] leftMax, rightMax
3. Ordered Stack - decreasing
s.push(i++); - store index
result += stack.isEmpty()? 0:(Math.min(A[stack.peek()],A[i])-A[bot])*(i-stack.peek()-1);

Next Greater Element
http://www.ideserve.co.in/learn/next-great-element-in-an-array

X. Stack
LeetCode 456 - 132 Pattern
Stack to maintain min-max: max after min till current element
https://discuss.leetcode.com/topic/68193/java-o-n-solution-using-stack-in-detail-explanation

TreeMap
Use TreeMap/TreeSet instead of PriorityQueue if it works and you need remove item from them

X. Union Find
http://algs4.cs.princeton.edu/15uf/UF.java.html
need know size of the nodes to init union-find
- Weighted Quick-Union and path compression
- O(1) ops: union, find, count, maxUnionCount, getHighestRank
- flattened parent tree
- no need to build/store graph (from edges array)

LeetCode 261 - Graph Valid Tree
1. uf
2. dfs
  boolean hasCycle(List<List<Integer>> adjList, int currentId, boolean[] visited, int parentId)
  if ((visited[v] && parentId != v) || (!visited[v] && hasCycle(adjList, neighborId, visited, currentId))) return hasCycle=true
3. bfs

LeetCode 130 - Surrounded Regions
1. dfs, bfs
find all 'O' not surrounded by 'X' (at or connected to the edge of the board ) and changed to '#'
flip the remain 'O' into X
flip the '#' back to 'O'
2. uf - union all the 'O' nodes on the boundry to a dummy node

LeetCode 128 - Longest Consecutive Sequence
1. use hashset, then check left and right
- but doesn't work for stream
https://discuss.leetcode.com/topic/17980/another-accepted-java-o-n-solution
2. https://discuss.leetcode.com/topic/9088/o-n-hashmap-java-solution
Map<Integer, Integer> map:  keep track of the sequence length and store that in the boundary points of the sequence.
3. uf: maxUnion or getHighestRank
https://discuss.leetcode.com/topic/29286/my-java-solution-using-unionfound
Map<Integer,Integer> map: value -> index
if(map.containsKey(nums[i]+1)) uf.union(i,map.get(nums[i]+1));

Detect Cycle in a an Undirected Graph
Number of Islands
LeetCode 323 - Number of Connected Components in an Undirected Graph
LeetCode 261 - Graph Valid Tree
LeetCode 305 - Number of Islands II
Group Contacts

X. Graph algorithm - O(V+E)
- Map<Integer, List<Integer>> map
- List<List<Integer>> adjList

topological sort
-- Put indegree=0 nodes to queue, iterate queue,  and decrease indegree of the node's neighbors by 1, if indegree is now 0, put into queue
- time complexity O(V+E), space O(V)
Leetcode 310 - Minimum Height Trees
List<Set<Integer>> adj
LeetCode 210 - Course Schedule II
LeetCode 269 -  Alien Dictionary
https://discuss.leetcode.com/topic/32900/java-bfs-solution
- build graph
dfs
https://discuss.leetcode.com/topic/33565/3ms-clean-java-solution-dfs
visited[i] = -1. Not even exist.
visited[i] = 0. Exist. Non-visited.
visited[i] = 1. Visiting.
visited[i] = 2. Visited.

LeetCode 444 - Sequence Reconstruction
https://discuss.leetcode.com/topic/65948/java-solution-using-bfs-topological-sort/5
- build the edge for adjacent ints in the array
Map<Integer, List<Integer>> graph
Map<Integer, Integer> indegree

Eulerian path/circuit
LeetCode 332 - Reconstruct Itinerary
https://discuss.leetcode.com/topic/36370/short-ruby-python-java-c
public List<String> findItinerary(String[][] tickets) {
    for (String[] ticket : tickets)
        targets.computeIfAbsent(ticket[0], k -> new PriorityQueue()).add(ticket[1]);
    visit("JFK");
    return route;
}
Map<String, PriorityQueue<String>> targets = new HashMap<>();
List<String> route = new LinkedList();
void visit(String airport) {
    while(targets.containsKey(airport) && !targets.get(airport).isEmpty())
        visit(targets.get(airport).poll());
    route.add(0, airport);
}

X. Binary tree
- usually expected runtime for tree is O(n)
- PreOrder/InOrder/PostOrder/LevelOrder traverse
- Use PostOrder Traverse
Leetcode 124 - Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum. The path may start and end at any node in the tree.
private int maxPathDown(TreeNode node) {
    if (node == null) return 0;
    int left = Math.max(0, maxPathDown(node.left));
    int right = Math.max(0, maxPathDown(node.right));
    maxValue = Math.max(maxValue, left + right + node.val);
    return Math.max(left, right) + node.val;
}
LeetCode 437 - Path Sum III
Find the number of paths that sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go downwards
https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method
- preorder tree traverse
- use hashmap to track: the prefix sum -> how many ways get to this prefix sum
- map.put(sum, map.get(sum)-1); // Remove the current node so it wont affect other path

LeetCode 250: Count Univalue Subtrees
- post order
Remove the paths from root to leaf whose sum is not equal to given K.
http://algorithmsandme.in/2014/03/remove-all-nodes-in-binary-tree-which-dont-lie-in-path/

LeetCode 230 - Find k-th smallest element in BST
- inorder search, return when count decrease to 0 from k
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently?

LeetCode 298 - Binary Tree Longest Consecutive Sequence
- preorder: count = (root.val - val == 1)?count+1:1;

LeetCode 107 - Binary Tree Level Order Traversal II
- bottom-up level order

LeetCode 103 - Printing a Binary Tree in Zig Zag Level-Order
If we only need print, it's easier to first get all level nodes in correct order then print
X. bfs https://discuss.leetcode.com/topic/42184/java-easy-understand-recursive-methods-beats-96-attach-easy-bfs-methods
Queue<TreeNode>, boolean leftToRight = !leftToRight;
if(leftToRight) levelNodes.add(n.val); else levelNodes.addFirst(n.val);
x. dfs - https://discuss.leetcode.com/topic/3413/my-accepted-java-solution
ArrayList<LinkedList<Integer>> result
x. 2 stacks
https://discuss.leetcode.com/topic/3318/my-ac-java-code
https://discuss.leetcode.com/topic/32427/java-double-stack-solution
Stack<TreeNode> oddSt, evenSt

X. Binary search tree
LeetCode 333 - Largest BST Subtree
class Wrapper{
    int size;
    int lower, upper;
    boolean isBST;
}

LeetCode 95 - Unique Binary Search Trees II
DFS - divide and conquer

X. Tree with only parent node
Google – Sum of Subtree with Only Parent Pointer
https://reeestart.wordpress.com/2016/06/23/google-sum-of-subtree-with-only-parent-pointer/
- reconstruct parent -> child
Map<TNode, List<TNode>> tree

X. Bit trick
- 23n, loop and check very bit
LeetCode 287 - Find the Duplicate Number
LeetCode 421 - Maximum XOR of Two Numbers in an Array

X. Game theory
If a player is able to move to a losing position then he is in a winning position.
If a player is able to move only to the winning positions then he is in a losing position.
LeetCode flip game II
DFS + Cache (top-down)
- use it's dp(bottom-up) to time complexity
- Map<String, Boolean> winMap
- if(!canWin(opponent, map))

Google – Initialize Board
radom + backtrack - https://reeestart.wordpress.com/2016/07/01/google-initialize-board/

Math
LeetCode 60 - Permutation Sequence
Given n and k, return the kth permutation sequence.
k--;
mod = mod / (n - i);
int curIndex = k / mod;
k = k % mod;
builder.append(list.remove(groupIndex));

X. Random
LeetCode 398 - Random Pick Index
https://discuss.leetcode.com/topic/58301/simple-reservoir-sampling-solution
if (rnd.nextInt(++count) == 0) result = i;

X. Misc
LeetCode 158 - Read N Characters Given Read4 II
https://discuss.leetcode.com/topic/6402/clean-accepted-java-solution

char[] buffer, int offset, remaining, boolean isEndOfFile

LeetCode 289 - Game of Life
use 2 bits: [2nd bit, 1st bit] = [next state, current state]

LeetCode 361 - Bomb Enemy
1. v1[i][j] + v2[i][j] + v3[i][j] + v4[i][j]
2.
rowhits, colhits[n]
for (int k=j; k<n && grid[i][k] != 'W'; k++)
    rowhits += grid[i][k] == 'E';
for (int k=i; k<m && grid[k][j] != 'W'; k++)
    colhits[j] += grid[k][j] == 'E';
result = max(result, rowhits + colhits[j]);

LeetCode 300 - Longest Increasing Subsequence
1.
int i = Collections.binarySearch(dp, num);
dp.set((i<0) ? -i-1 : i, num);
-- O(nlogn)
2. DP O(N^2)

4Sum
https://discuss.leetcode.com/topic/12368/clean-accepted-java-o-n-3-solution-based-on-3sum
http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/
O(N^3)
HashMap<Integer, ArrayList<Pair>> hashMap

LeetCode 454 - 4Sum II
https://discuss.leetcode.com/topic/67593/clean-java-solution-o-n-2

Leetcode 370 - Range Addition
https://discuss.leetcode.com/topic/49691/java-o-k-n-time-complexity-solution
res[start] += value;
res[end+1] -= value;

LeetCode 406 - Queue Reconstruction by Height
1. sort + insert: by height then index
https://discuss.leetcode.com/topic/60394/easy-concept-with-python-c-java-solution

Rearrange Positive and Negative Numbers of Array On Each Side with­out chang­ing their respec­tive order
- use reverse to avoid extra tmp array

Google – Shortest Words Contain Input String
- Inverted Index
Map<Character, List<String>> invertedIndex
set.retainAll(invertedIndex.get(c));

Hash - feature key
Google – Plate and Dictionary
- prime product as string key

LCA
-- Node to Node Binary Tree Path

Checklist to Solve Algorithm Problems

logn
- bisection
- divide and conquer

X. Quick select to find kth O(n) - compare with heap nlog(k)


X. DP
- find sub-problems and relation
- dp: [i, j]; or dp[len-1] just start/or end
X. BFS
- Model it as a graph
X. DFS

X. Divide and Conquer
- find subproblems and relations
X. Bisection/Binary search
O(nlogn) - logn*n(merge sort) or n*logn(3 sum) binary search/bisection

X. Merge sort
X. Slide Window
X. Two pointers

Data Structures
X. Trie
- use trie so no need to scan every candidate(O(n))
X. Binary search tree
X. ordered stack/stack
X. Union Find
Data structures
X. augmented tree
X. bst
TreeSet, TreeMap
X. heap, map

X. Bit trick
- O(32n) - loop and check every bit
- bit trie, use xor

X. Interval
- First sort these intervals somehow
- Think as different events - start, end
- sort interval + greedy
- merge interval

X. Game theory

Palindrome
-- Scan from center

Graph - O(V+E)
- topological sort
- Eulerian path/circuit

Save space
- reuse input
- rolling array for dp

Common tricks
check last loop
whether we need do extra things after loop
Use char[] to avoid string concatenation

Backtrack
- Don't forget to clear state

Binary tree
- usually expected runtime for tree is O(n)

ask
- sorted?
- can we change input, use extra space



How to Solve Algorithm Problems

Brainstorm list
bit trick
O(32n) - loop and check every bit

O(nlogn) - logn*n(merge sort) or n*logn(3 sum) binary search/bisection

Save space
- reuse input
- rolling array for dp

1. Clarify the question
Listen Carefully and Ask Questions
Make sure you hear the problem correctly

Ask questions about anything you're unsure about.
- do we need threadsafe?
- can we change the input?
- all positive?
Understand and list any unique/key information in the problem.

Ask yourself if you've used all the information in the problem.
Write the pertinent information on the whiteboard

Cut out all the "fluff" to this problem

Use concrete example to help clarify the problem.

Some interviewers writes down one example, but erases it later.
- if possible, keep the example in the whiteboard

Ask
Whether all numbers are unique, positive, sorted?
Whether there are duplicate numbers?
For string - character range, ascii only?
What's the expected time and space complexity?
How frequently these apis are called?

Draw an Example
-Specific, Sufficiently large, Not a special case

State a Brute Force and iterative refinement

Think about the best conceivable runtime

Before start to write code
-- make sure your algorithm works - in speical case
-- test your algorithm with examples and different cases
-- test with corner cases

-- List basic steps

When write code
-- We can start with simple case or complex case
- based on how much time left, if there is no much time left, start with complex case to show that u can solve it

Implement
Modularized code

What Good Coding Looks Like
- Correct, Efficient, Simple, Readable, Maintainable
Use Data Structures Generously
Use/Create other classes/structs where appropriate
- StartEndPair class instead of a two-dimensional array
Modular
Appropriate Code Reuse
Flexible and Robust
Good variable/function names
Error checks - add to-do comments to remind you and the interviewer

Focus on the top-level algorithm/code
--add //TODO comments


Don't Give Up! Get excited to solve hard problems

If you see something you can improve later on: either a different approach or code refactor, explain it to your interviewer.

How to test?
Start with a "conceptual"test.
Weird looking code.
Hot spots.
Small test cases.
Special cases.
Finding patterns

Optimize
X. Look for BUD
Bottlenecks
Unnecessary work/space
Duplicated work
-- Use cache

X. DIY (Do It Yourself)
Try working it through intuitively on a real example

Simplify and Generalize

Base Case and Build - Recursive

Best Conceivable Runtime (BCR)
Derive, don't guess the runtime.

Data Structure Brainstorm
- HashMap, HashSet
- Trie
- Union Find
-- Example: LeetCode [305] Number of Islands II

- Heap, PriorityQueue
- Deque(LinkedList, ArrayDeque)
LeetCode 239 - Sliding Window Maximum

- Binary tree, binary search tree
- Augmented binary tree
- TreeMap, TreeSet
LeetCode 352 - Data Stream as Disjoint Intervals
-- Sorted, O(logn) insert/delete

- Graph
Graph modeling

Algorithm Brainstorm
- BFS, DFS
-- Multi-End BFs
-- LeetCode 286 - Walls and Gates,

DFS/Recursive

Be excited about hard problems
Listen (for clues)
Draw an Example
(A) Look for BUD
Bottlenecks
Unnecessary work
Duplicated work


Cracking the Coding Interview (College) -  Gayle McDowell
Scope, Key components, identify issues, repair
Scope the Problem
Ask questions
Make appropriate assumptions
Define Key Components
Can be somewhat naïve
Identify Issues
Bottlenecks, tradeoffs
Repair & Redesign

Run through your algorithm meticulously before coding.
Modularize your code first.
Don't crowd your code.

Review your code conceptually.
Review error hot spots.
Test against a small example.
Pinpoint potential issues.
Test error cases.
Point out the mistake, and carefully analyze why the bug is occurring.

Pattern matching means to relate a problem to similar ones, and figure out if you can modify the solution to solve the new problem.

SIMPLIFY AND GENERALIZE
DATA STRUCTURE BRAINSTORM

Handle your special cases just once
- step through code and focus on dataflow and logic

- DFS/BFS + Cache - (Compared with DP)
https://www.hrwhisper.me/leetcode-longest-increasing-path-matrix/
LeetCode 329. Longest Increasing Path in a Matrix

-- Divide and conquer
-- Find subproblems

Backtrack
Recursive
-- LeetCode [267] Palindrome Permutation II
-- What info to maintain
Leetcode 124 - Binary Tree Maximum Path Su
private class maxPathResult {
    int maxSinglePath;
    int maxPath;
}

- DP
-- multiple dp relations (LeetCode 375 - Wiggle Subsequence)
-- space optimization
from O(NM) space to O(N)
X. rolling array

what is known, unknown
whether we used all known


Common Tricks
Presum

check last loop
whether we need do extra things after loop

backtrack
Don't forget to clear state

Binary tree
- usually expected runtime for tree is O(n)

Palindrome
-- Scan from center

space save
- rolling array in dp
- use/modify origin input

Graph
Eulerian path/circuit

Labels

Java (159) Lucene-Solr (110) All (60) Interview (59) J2SE (53) Algorithm (37) Eclipse (35) Soft Skills (35) Code Example (31) Linux (26) JavaScript (23) Spring (22) Windows (22) Web Development (20) Tools (19) Nutch2 (18) Bugs (17) Debug (15) Defects (14) Text Mining (14) J2EE (13) Network (13) PowerShell (11) Chrome (9) Continuous Integration (9) How to (9) Learning code (9) Performance (9) UIMA (9) html (9) Design (8) Dynamic Languages (8) Http Client (8) Maven (8) Security (8) Trouble Shooting (8) bat (8) blogger (8) Big Data (7) Google (7) Guava (7) JSON (7) Problem Solving (7) ANT (6) Coding Skills (6) Database (6) Scala (6) Shell (6) css (6) Algorithm Series (5) Cache (5) IDE (5) Lesson Learned (5) Miscs (5) Programmer Skills (5) System Design (5) Tips (5) adsense (5) xml (5) AIX (4) Code Quality (4) GAE (4) Git (4) Good Programming Practices (4) Jackson (4) Memory Usage (4) OpenNLP (4) Project Managment (4) Python (4) Spark (4) Testing (4) ads (4) regular-expression (4) Android (3) Apache Spark (3) Become a Better You (3) Concurrency (3) Eclipse RCP (3) English (3) Firefox (3) Happy Hacking (3) IBM (3) J2SE Knowledge Series (3) JAX-RS (3) Jetty (3) Restful Web Service (3) Script (3) regex (3) seo (3) .Net (2) Android Studio (2) Apache (2) Apache Procrun (2) Architecture (2) Batch (2) Build (2) Building Scalable Web Sites (2) C# (2) C/C++ (2) CSV (2) Career (2) Cassandra (2) Distributed (2) Fiddler (2) Google Drive (2) Gson (2) Html Parser (2) Http (2) Image Tools (2) JQuery (2) Jersey (2) LDAP (2) Life (2) Logging (2) Software Issues (2) Storage (2) Text Search (2) xml parser (2) AOP (1) Application Design (1) AspectJ (1) Bit Operation (1) Chrome DevTools (1) Cloud (1) Codility (1) Data Mining (1) Data Structure (1) ExceptionUtils (1) Exif (1) Feature Request (1) FindBugs (1) Greasemonkey (1) HTML5 (1) Httpd (1) I18N (1) IBM Java Thread Dump Analyzer (1) JDK Source Code (1) JDK8 (1) JMX (1) Lazy Developer (1) Mac (1) Machine Learning (1) Mobile (1) My Plan for 2010 (1) Netbeans (1) Notes (1) Operating System (1) Perl (1) Problems (1) Product Architecture (1) Programming Life (1) Quality (1) Redhat (1) Redis (1) Review (1) RxJava (1) Solutions logs (1) Team Management (1) Thread Dump Analyzer (1) Troubleshooting (1) Visualization (1) boilerpipe (1) htm (1) ongoing (1) procrun (1) rss (1)

Popular Posts