TIPs for coding
Practice is so helpful to improve one's coding skills. This github records the daily algorithm practice. In each directory, the java or python code and some tips are included. The following is some useful tips one would meet in these online coding.
common methods (must know):
brute force, dfs/bfs, sorting, dp, recursive, math, number theory, bit, probabilities, games, greedy, combinatorics, divide and conquer.
two pointer, Sweepline
string, tree, graph, hashing, matrices
-
dp: understand the optimization from brute force to memorization to dp, buttom-top method, top-buttom method.
-
gcd method to calculate greatest common divisor.
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}- Compare two tree, please first serialize and deserialize tree.
- While using DP, we may modify the dp array with another non-linear way.
- While use hashmap for char in string, use int[256] as HashMap instead.
- bit
// exchange x, y
x = x + y;
y = x - y;
x = x - y;
x = x^y; // 只能对int,char. 存不一样的bit位
y = x^y;
x = x^y;
// get the last 1.
// in bit, -diff is reverse every bit position and plus 1.
diff &= -diff;- for most substring problems. leetcode discussion
string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto c: t) map[c]++;
int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
while(end<s.size()){
if(map[s[end++]]-->0) counter--; //in t
while(counter==0){ //valid
if(end-begin<d) d=end-(head=begin);
if(map[s[begin++]]++==0) counter++; //make it invalid
}
}
return d==INT_MAX? "":s.substr(head, d);
}-
to find the one different char or int, use bit manipulation like 389
-
segment tree (307)
summarry
Recodes for some "Hard" questions
30 Substring with Concatenation of All Words. Two different method, the fast one is hard.
32 Longest Valid Parentheses DP, stack. hard problem but with many smart idea.
134 very good practice. Not so straightforward.
137 Single Number II, bit manipunation. very hard
146 LRU Cache LinkedHashMap
166 Fraction to Recurring Decimal, Math, corner cases.
218 The skyline problem. Use Sweepline method.
220 Contains Duplicate III, TreeSet
363 matrix sum, binary search, DP, TreeSet
368 DP, need some thought, have fun.
479 Largest Palindrome Product. Math
564 Find the Closest Palindrome. Hard. Becareful for corner cases.
659 Remove 9, Math,
Recodes for some "must do" questions
1 167 Two Sum and related two sum and other N sum questions. Must do!
11 42 Container With Most Water. Trapping Rain Water. Two pointers.
34 Search for a Range. very good practice for binary search.
Subsets, Permutations, Combination Sum, Palindrome Partioning backtrack problems
44 Wildcard Matching basic DP method
46 47 Very common question. Check discussion for a summary.
54 Spiral Matrix. Print maxtix problem. Practice the basic coding skill with edges.
72 Edit Distance. You will learn memorization and dp from this "hard" (actually easy) question.
76 Minimum Window Substring. hard, good practice for two pointers.
97 InterLeaving String. brute force > memorization > 2D dp > 1D dp
98 Binary search tree. Please practice with different methods. recursive with and without global variation, non recursive.
105 Tree preorder inorder. Very interesting and useful practice for backtrack.
116 Very good exercise for trees.
189 Easy but interesting, use as many methods as you can to rotate array. Must know the reverse method by two reverses.
202 Happy Number. Interesting problem with two solutions. One solution is similiar to the cycle detetion in linkedlist.
307 Range Sum Query - Mutable. Studey how to use segment tree
373 Find K Pairs with Smallest Sums. Use priority queue for questions about "Top K". This is a hard problem.
401 easy question. Attention: think more about each question. Every question has its own method.
404 Sum of Left Leaves. Many tree problems can be solved with iterative and recursive methods.
458 Poor Pigs.
581 Shortest Unsorted Continuous Subarray. Interesting easy problem with several kinds of solutions.
609 Find Duplicate File in System. Interesting, BFS/DFS for the follow up question about big files.
--
http://wiki.jikexueyuan.com/project/for-offer/question-three.html
Resources
www.glassdoor.ca www.careercup.com www.geeksforgeeks.com www.leetcode.com www.hackerrank.com www.topcoder.com
Mock Interviews
- groups of 2 or 3(max)
- Interviewee, ask questions, discuss approach, though as code
- Interviewer, pick question, guide if lost
刷题经历
- coursera Algorithm I, 学习java，看了大神如何分析。花了不少时间。
- （曲折）听了不少讲座，然而收效甚微
- 牛客网 直通BAT。从而建立基本的数据结构的概念
- cc150或者剑指offer。从lintcode上刷，建立起各种问题分析方法。于此同时查看cc150后面的OOD的几个经典内容
- 总结各种方法。（豁然开朗）
- leetcode一遍。(Not possible)。200 题之后应该快速过，保持速度与量，多思考，多总结。
- leetcode contest 强制自己思考和总结，认识不足，看牛人代码。
基础数据结构
数组
链表
堆栈
队列
树
图
HashTable
字符串
算法思想
贪心算法
动态规划
二分法
分治算法
双指针
滑动窗口
其他主题
位运算
大数据