The key of the question
The most important thing during interview is to know the key of the question.
The key is to:
-- for system design or data structure question:
design and find a good data structure?
what's the time complexity for each operation?
it's about algorithm, coding, what's your current solution's time complexity? what's the expected tc? can you make your solution faster?
It's hard to succeed in the interview without getting the right answer to the key question.
Explain your solution, and explain the time/space complexity, make sure the interviewer is ok with it.
If you are not sure, or can't find optimal solution, ask whether there is better solution
-- mark & sweep, 可以联想展开, 和类似的经典的design 算法思路
List the main steps - simple pseudo code/text
Write the main function first
Extract sub function, write sub functions later
Write important sub functions first
--
What states we need track? what data structure to use for it.
Don't use two data structure if it can be done with one ???
Map<Integer, Boolean>: node -> needRemove
It's better than two sets: Set<Integer> toKeep, toRemove;
--
Recursive: what will change during each step - use it as argument.
1. try to use memorization to avoid re-computation.
2. need Set<boolean> visisted?
What kind of data structure we can use?
-- multiple level data structure
design mini search app:
Map<String, List<List<Integer>> word -> docid1:pos1,pos2 | docid2: |
Use multiple data structure:
Hashmap with array
Some data structures that can maintains kind of order
TreeSet, TreeMap
-- We can also maintain multiple level order
Class: WordPosition
{
int docid,
int position
}
PriorityQueue(Min/Max Heap)
Trie
Binary Search Tree
When learn algorithm/data structure, expand it, and ask how you can optimize space, time complexity etc. whether there is better solution.
Trie -> to save space -> ternary trie -> or radix trie
Union find -> compress path
Common bugs:
1. forget base condition
2. forget init the data
always think what's the initial value: 0, -1, or MIN/MAX_VALUE
dp[][]
3. handle first case i=0(n-1) specially
4. last element - whether we need do extra stuff after loop
http://javahungry.blogspot.com/2014/06/algorithm-problem-solving-techniques-or-approaches-for-software-programmer.html
1. Examplify : Create the example of the algorithm
First use the simplest case.
Simplify the example.
2. Pattern Matching
We have to consider what problems the algorithm is similar to , we need to figure out if we can modify the solution to develop an algorithm for the given problem .
3. Simplify and Generalize
Changing constraint (e.g size,length,data type) to simplify the problem.For example changing the data type from double to int , make the problem smaller.
4. Base case and Build
This approach is most widely used in the recursive algorithm .
Solve the algorithm first for a base case (e.g., just one element). Then, try to solve it for elements one and two, assuming that we have the answer for element one. Then, try to solve it for elements one, two and three, assuming that we have the answer to elements one and two.
5. Data Structure Brainstorm
This is tiresome method and based on hit and trial method . Simply , run through a list of data structures and try to apply each one.
Heap(PriorityQueue), HashMap(Set), Trie, BitSet, Binary Search Tree
Double End Queue
https://dzone.com/articles/cracking-coding-interview-12
#2 Write code WITHOUT tools
#3 Have a portfolio
#4 Think out loud
#5 Don’t argue, blame or make excuses
#6 Don’t give up
#7 Test your code
So, pretend like your code might be capable of having errors and test through it before you tell the interviewer that you are done.
paper test it. (That means walk through the code with possible inputs, line-by-line.)
#8 Name things clearly
#9 Ask for feedback
it doesn’t hurt to ask the interviewer their opinion on your code and your solution to the problem.
Yes, I know they are going to say some irrelevant bull-crap, but remember what I said about making them feel important? You know that unobtainable standard of perfection that you don’t want to project?
Ask them for feedback. Especially if you don’t know the answer to a problem and they’ve timed you out.
Show that you are interested in learning and that you don’t just want to get the answer right, but you want to understand it.
I guarantee it won’t make you look stupid.
#10 Don’t rush
It’s about being thoughtful, analytical, careful and accurate.
Be the guy who takes his time, tests his code and makes sure it works, before he throws it over to the interviewer and says he’s done.
#11 Practice mock interviews and take notes
#12 Ask questions
Don’t just start coding the solution to a problem. Even if you think you understand it.
Ask the interviewer some questions to confirm.
The point isn’t to run off and code the right answer, the point is to simulate how you’d behave in a real-world environment.
If you don’t ask clarifying questions about your assignment in a coding interview, the interviewer is likely to assume that you wouldn’t ask questions in a real-world situation either.
http://horicky.blogspot.com/2010/06/strategy-for-software-engineering.html
https://dzone.com/articles/strategy-software-engineering
This can help you to make sure you fully understand the question and clarify if there is any hidden assumptions you have made. Repeat the question "slowly" also gives you more time to think.
From the interview perspective, he/she can see clearly the candidate's ability to digest a problem.
2. Construct a Visual model of the problem
Use a whiteboard, or paper (if this is a phone interview) to diagram the problem that you perceive. Our brain is good in understanding picture than words so having a diagram will be very useful to come up with solution ideas.
From an interview's perspective, he/she can see a clear picture how you analyze the problem.
3. Use a special, simple case to guide you
Never try to tackle the general problem at first, start with a super-simple, special case, and think how you would solve this simple case first. This is very helpful to reduce the amount of things that you need to consider and let you focus in the core part of the problem.
4. Start with a very naive solution as a baseline
Tell the interviewer that you want to start with a very naive solution to establish a baseline. The naive solution can usually be constructed using a brute-force approach (try all combination until you find a matched solution). After that analyze the complexity of this naive solution as a baseline for future comparison.
5. Improve your solution
At this stage, you need to evolve and improve your solution. Here are some general techniques.
Don't wait until you fully figure out the answer. Keep talking while you are thinking about the solution so the interviewer understand how you analyzing things, and you are also showing how well you can express your thoughts. It is also easier for the interviewer to guide you or give you hints. And finally you may impressed the interviewer even you cannot get to the exact answer.
7. Generalize your solution for the final answer
After you find a working solution for the simple case, extend the simple case to see how you would solve it. See if you can find a general pattern how the solution would look like. Once you find it, generalize your solution for the general problem
From the interview's perspective, he/she can assess if the candidate can think in different levels of abstraction, and the ability to apply a solution in a broader scope of problem.
8. Remember the interview hasn't ended at the office building
You always have the chance to think through the question that you haven't given satisfactory answer after you walk out from the office. Submit a solution via email once you get back home (do it ASAP though), along with a thank you note to the interviewer.
http://www.cnblogs.com/yrbbest/p/5136729.html
http://www.1point3acres.com/bbs/thread-79646-1-1.html
我觉得如果一点算法和数据结果都不知道的话，要先学一门算法和数据结构的课，里面复杂的数学推导和证明可以不管，但是一定要会分析时间和空间复杂度，这是面试必问的。
有了数据结构和算法的基础，之后我推荐Programming Interview Exposed，里面有大段分析，讲一个怎样分析一个问题，然后想出BF方案，再优化的过程，我觉得讲的非常好。这本书看完，就可以刷CC150或者Leetcode了。不过不管是看书还是刷Leetcode里面的题，一定要自己想结果，一个题至少要想个十几分钟乃至几小时，如果实在想不出来，再去看答案，如果想出了方案，再自己想想怎么能优化不？之后再看答案，对比一下自己为什么没想到最优方案，然后一定要彻底理解这个最优方案，如此下来遇到同样甚至变形的题才会有思路。
强调一下：直接看答案或者只想很短时间就看答案收获是比较小的，只有自己仔细想了，收获才最大！
http://selfboot.cn/2015/11/03/howto_find_algorithm/
刘未鹏在跟波利亚学解题上有一个不错的观点：好问题即测试一个人思维的习惯的题目，通常考察你的联想能力、类比能力、抽象能力、演绎能力、归纳能力、观察能力、发散能力等。
http://www.1point3acres.com/bbs/thread-130162-2-1.html
要把做过的题目联系起来，然后总结方法。寻求为什么这么做，而不是怎么做。否则，不通过举一反三，而寄希望于在考试／面试时出现做过的内容，那就真是“以有崖求无崖，殆哉矣”。这里，我只谈方法。给个实例：
大家可能都觉得，算法题中动态规划是比较麻烦的问题。但当你碰到这类问题时，仔细总结过方法么？考虑过题目为什么要用动态规划么？动归和递归的区别在哪里？
我觉得，从子问题解决原问题, 无非是两种方法，自底向上(Bottom-Up)与自顶向下(Top-Down)，形式上前者对应iteration，利用循环将结果存在数组里，从数组起始位置向后计算；后者对应recursion，即利用函数调用自身实现，如果不储存上一个状态的解，则为递归，否则就是DP。举个斐波那契数列(0,1,1,2,3,5…)的例子：
1) 自底向上
int array[n] = {0};
array[1] = 1;
for (int i = 2; i < n; i++)
array = array[i-1] + array[i-2];
事实上，额外空间可以进一步缩小到O(1)：利用几个变量记录之前的状态即可。由于记录了子问题的解，故给出的方法就是DP。事实上，自底向上的方式往往都是通过动态规划实现。
2) 自顶向下
int Fibonacci(int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
为计算Fibonacci的第n个元素，我们先自顶向下地计算子问题：第n-1个元素和第n-2个元素。由于没有储存子问题的运算结果，给出的方法是递归。然而，Fibonacci(n-1)与Fibonacci(n-2)包含很多重复的子问题，所以DP效率更高。如果用一个全局数组，将子问题的解储存到数组的对应位置，在重复计算的时候直接读取计算结果，那么就是DP的解法。
动态规划的核心在于，如果通往一个问题的solution，subproblem被重复计算，那么就可以利用记录中间结果，达到用空间换取时间的目的。在递归过程中用hash table记录中间计算结果的DP，称作Memoization。
Memoization的一般形式是: 建立以input为key，以output为value的hash table：
T func(N node, HashTable<N, T>& cache) {
If (cache.contains(node)) {
return cache.get(node);
}
…
T sub_res = func(next_node, cache);
…
T res = G( sub_res … ); //当前子问题的解，依赖于更小的子问题(s)
cache.set(node, res);
return res;
}
从解决问题的角度来说，用Bottom-Up的DP，固然通常可以节省递归本身的空间开销，但有很多缺点和局限：较难理解，边界条件较难处理，只适用于问题的节点空间是离散的整数空间，必须一步步邻接、连续地计算(无论是不是每一个节点的结果都会被用到)。而Memoization，则灵活得多：可以从递归形式轻易修改得到，也更符合普遍的思维过程，并且没有上面说的这些局限，子问题只有在被需要的时候才会被计算。尤其是在某些情况下，不仅需要aggregate的结果，还需要获得achieve这个结果的路径，这时候就算用Bottom-Up的DP，也需要记录prev节点，最后需要递归回溯得到路径，那么节省递归空间开销的优势，也荡然无存了。
那么Bottom-Up的DP可以解决哪类问题？我说，DP适用于解决“收敛结构问题”。所谓的“收敛结构问题”是指关于特解，或数量的问题（例如，第n个元素，第n步有多少种方法等）。这些问题都可以用整数坐标映射所有节点（即DP状态），且当前节点的解只依赖于前驱节点(无论是顺序还是倒序)。那么，这类问题往往可以用DP解决。解决的关键是建立subproblem的解之间的递推关系：
f(n) = G[f(n-1), f(n-2), … , f(1)] 或
f(i, j) = G[f(i-1, j-1), f(i, j -1), f(i-1,j)]
其中G[ ]表示子问题到原问题的映射关系，例如对于斐波那契数列，有递推式：
f(n) = G[f(n-1), f(n-2)] = f(n-1) + f(n-2)
但如果出现类似于“所有解”，“所有路径”等关键词，则用Top-down方法更为直接。
举一道简单的题目： Suppose we have a ladder which has n steps. Each time you can either climb 1 or 2 steps. Please write a function to calculate how many distinct ways that can you climb to the top?
解题分析：本问题描述了一个数量问题，属于前述的强收敛(聚合)性问题，可以用DP。DP的核心在于递推关系：当前节点的值可以由前驱走一步到达，或者前前驱走两步到达，即CountOfWays(n) = CountOfWays(n–1) + CountOfWays(n-2)；由于当前节点只与紧邻的两个节点决定，所以只需要2个临时变量来表示前驱节点的解即可，而不用DP table，因为更老的解我们不需要关心。在实现时，往往边界条件直接用if…then return value的形式，成为递归的出口。
因此，当理解到了一定的深度，真不是特别在乎做了多少题目。与之相关的另一个问题是，准备周期得有多长？这里，我只谈事实。看过我之前文章的朋友也知道，我本来是考虑转博的，但后来打算直接工作。我那时一月底开始准备，二月底投简历，到四月底一共onsite了12家公司拿了10个offer。不否认我的基础还算不错，科研也和软件相关，但也不算科班出身，硕士是ECE（在面试google的时候也暴露了CS知识面不够广的问题，所以G家也是我唯一技术上没过的公司）。
但是，我们准备的时候极其认真，效率远远超过现在工作。特别是他为了节约时间，一天只吃固定东西：中午越南粉，晚上Jack in the box或者互换。谈事实的目的就是，如果真正投入加仔细思考方法，几个月搞定心仪的工作也不是不可能。就看你理解的有多深。
大家可以比较下思考的深度。他笔记里的思想后来成了我们书的原型。
只练不想还有两个问题：
1. 看到类似的题目就硬套方法。当面试官要求换个思路时会感觉很困难
2. 看到没见过的题目有时就会慌，结果连正常水平也没发挥出来。
总而言之，希望大家能换个方向看刷题，与其做上两遍，三遍，不如花相同的时间认真总结下适合自己的方法。
https://www.zybuluo.com/smilence/note/76
Books
http://lbv-pc.blogspot.com/p/advice-for-beginners.html
The most important thing during interview is to know the key of the question.
The key is to:
-- for system design or data structure question:
design and find a good data structure?
what's the time complexity for each operation?
it's about algorithm, coding, what's your current solution's time complexity? what's the expected tc? can you make your solution faster?
It's hard to succeed in the interview without getting the right answer to the key question.
So don't start to code until you are sure you figure out the right answer to the key.
If you can't find the right answer, and are forced to start code - still think about it.
Explain your solution, and explain the time/space complexity, make sure the interviewer is ok with it.
If you are not sure, or can't find optimal solution, ask whether there is better solution
-- mark & sweep, 可以联想展开, 和类似的经典的design 算法思路
List the main steps - simple pseudo code/text
Write the main function first
Extract sub function, write sub functions later
Write important sub functions first
--
What states we need track? what data structure to use for it.
Don't use two data structure if it can be done with one ???
Map<Integer, Boolean>: node -> needRemove
It's better than two sets: Set<Integer> toKeep, toRemove;
--
Recursive: what will change during each step - use it as argument.
1. try to use memorization to avoid re-computation.
2. need Set<boolean> visisted?
What kind of data structure we can use?
-- multiple level data structure
design mini search app:
Map<String, List<List<Integer>> word -> docid1:pos1,pos2 | docid2: |
Use multiple data structure:
Hashmap with array
Some data structures that can maintains kind of order
TreeSet, TreeMap
-- We can also maintain multiple level order
Class: WordPosition
{
int docid,
int position
}
PriorityQueue(Min/Max Heap)
Trie
Binary Search Tree
When learn algorithm/data structure, expand it, and ask how you can optimize space, time complexity etc. whether there is better solution.
Trie -> to save space -> ternary trie -> or radix trie
Union find -> compress path
Common bugs:
1. forget base condition
2. forget init the data
always think what's the initial value: 0, -1, or MIN/MAX_VALUE
dp[][]
3. handle first case i=0(n-1) specially
4. last element - whether we need do extra stuff after loop
http://javahungry.blogspot.com/2014/06/algorithm-problem-solving-techniques-or-approaches-for-software-programmer.html
1. Examplify : Create the example of the algorithm
First use the simplest case.
Simplify the example.
2. Pattern Matching
We have to consider what problems the algorithm is similar to , we need to figure out if we can modify the solution to develop an algorithm for the given problem .
3. Simplify and Generalize
Changing constraint (e.g size,length,data type) to simplify the problem.For example changing the data type from double to int , make the problem smaller.
4. Base case and Build
This approach is most widely used in the recursive algorithm .
Solve the algorithm first for a base case (e.g., just one element). Then, try to solve it for elements one and two, assuming that we have the answer for element one. Then, try to solve it for elements one, two and three, assuming that we have the answer to elements one and two.
5. Data Structure Brainstorm
This is tiresome method and based on hit and trial method . Simply , run through a list of data structures and try to apply each one.
Heap(PriorityQueue), HashMap(Set), Trie, BitSet, Binary Search Tree
Double End Queue
https://dzone.com/articles/cracking-coding-interview-12
#2 Write code WITHOUT tools
#3 Have a portfolio
#4 Think out loud
#5 Don’t argue, blame or make excuses
#6 Don’t give up
#7 Test your code
So, pretend like your code might be capable of having errors and test through it before you tell the interviewer that you are done.
paper test it. (That means walk through the code with possible inputs, line-by-line.)
#8 Name things clearly
#9 Ask for feedback
it doesn’t hurt to ask the interviewer their opinion on your code and your solution to the problem.
Yes, I know they are going to say some irrelevant bull-crap, but remember what I said about making them feel important? You know that unobtainable standard of perfection that you don’t want to project?
Ask them for feedback. Especially if you don’t know the answer to a problem and they’ve timed you out.
Show that you are interested in learning and that you don’t just want to get the answer right, but you want to understand it.
I guarantee it won’t make you look stupid.
#10 Don’t rush
It’s about being thoughtful, analytical, careful and accurate.
Be the guy who takes his time, tests his code and makes sure it works, before he throws it over to the interviewer and says he’s done.
#11 Practice mock interviews and take notes
#12 Ask questions
Don’t just start coding the solution to a problem. Even if you think you understand it.
Ask the interviewer some questions to confirm.
The point isn’t to run off and code the right answer, the point is to simulate how you’d behave in a real-world environment.
If you don’t ask clarifying questions about your assignment in a coding interview, the interviewer is likely to assume that you wouldn’t ask questions in a real-world situation either.
http://horicky.blogspot.com/2010/06/strategy-for-software-engineering.html
https://dzone.com/articles/strategy-software-engineering
Employers are generally looking at 5 areas when hiring a software engineer ...
- Technical knowledge of specific technology product
- Experience of the business problem domain
- General technical and architecture sense
- Personality and working style
- IQ, problem solving skills
This can help you to make sure you fully understand the question and clarify if there is any hidden assumptions you have made. Repeat the question "slowly" also gives you more time to think.
From the interview perspective, he/she can see clearly the candidate's ability to digest a problem.
2. Construct a Visual model of the problem
Use a whiteboard, or paper (if this is a phone interview) to diagram the problem that you perceive. Our brain is good in understanding picture than words so having a diagram will be very useful to come up with solution ideas.
From an interview's perspective, he/she can see a clear picture how you analyze the problem.
3. Use a special, simple case to guide you
Never try to tackle the general problem at first, start with a super-simple, special case, and think how you would solve this simple case first. This is very helpful to reduce the amount of things that you need to consider and let you focus in the core part of the problem.
4. Start with a very naive solution as a baseline
Tell the interviewer that you want to start with a very naive solution to establish a baseline. The naive solution can usually be constructed using a brute-force approach (try all combination until you find a matched solution). After that analyze the complexity of this naive solution as a baseline for future comparison.
5. Improve your solution
At this stage, you need to evolve and improve your solution. Here are some general techniques.
- Divide and conquer: Decompose the problem into smaller ones and solve each sub-problem separately, then combine the solutions for the overall problem.
- Reduce to well-known algorithm models: Try to model your problem in terms of well-studied computer science data structure model (e.g. Tree, Graph, Search, Sort) and then apply well known algorithm to solve them
- Recursive structure: Try to structure your problem in a recursive form. Finding the solution for the base case and then expand the solution in a recursive manner.
- Greedy method: Try to modify attributes of your current best solution to see if you can get a better one. Watch out of being trapped in a local optimal solution.
- Approximation: Instead of finding an exact solution, try to see if it is acceptable to find an approximate solution. Probabilistic approach (try 100 random combination and pick the best outcome)
Don't wait until you fully figure out the answer. Keep talking while you are thinking about the solution so the interviewer understand how you analyzing things, and you are also showing how well you can express your thoughts. It is also easier for the interviewer to guide you or give you hints. And finally you may impressed the interviewer even you cannot get to the exact answer.
7. Generalize your solution for the final answer
After you find a working solution for the simple case, extend the simple case to see how you would solve it. See if you can find a general pattern how the solution would look like. Once you find it, generalize your solution for the general problem
From the interview's perspective, he/she can assess if the candidate can think in different levels of abstraction, and the ability to apply a solution in a broader scope of problem.
8. Remember the interview hasn't ended at the office building
You always have the chance to think through the question that you haven't given satisfactory answer after you walk out from the office. Submit a solution via email once you get back home (do it ASAP though), along with a thank you note to the interviewer.
http://www.cnblogs.com/yrbbest/p/5136729.html
最近在看<算法问题实战策略>，里面总结了一些解决问题的步骤，我也记录一下。
- 阅读并理解问题
- 用熟悉的术语重新定义问题
- 制定解题计划
- 验证计划
- 通过程序实现解题
- 回顾解题过程，思考can we do better
http://www.1point3acres.com/bbs/thread-79646-1-1.html
我觉得如果一点算法和数据结果都不知道的话，要先学一门算法和数据结构的课，里面复杂的数学推导和证明可以不管，但是一定要会分析时间和空间复杂度，这是面试必问的。
有了数据结构和算法的基础，之后我推荐Programming Interview Exposed，里面有大段分析，讲一个怎样分析一个问题，然后想出BF方案，再优化的过程，我觉得讲的非常好。这本书看完，就可以刷CC150或者Leetcode了。不过不管是看书还是刷Leetcode里面的题，一定要自己想结果，一个题至少要想个十几分钟乃至几小时，如果实在想不出来，再去看答案，如果想出了方案，再自己想想怎么能优化不？之后再看答案，对比一下自己为什么没想到最优方案，然后一定要彻底理解这个最优方案，如此下来遇到同样甚至变形的题才会有思路。
强调一下：直接看答案或者只想很短时间就看答案收获是比较小的，只有自己仔细想了，收获才最大！
http://selfboot.cn/2015/11/03/howto_find_algorithm/
刘未鹏在跟波利亚学解题上有一个不错的观点：好问题即测试一个人思维的习惯的题目，通常考察你的联想能力、类比能力、抽象能力、演绎能力、归纳能力、观察能力、发散能力等。
http://www.1point3acres.com/bbs/thread-130162-2-1.html
要把做过的题目联系起来，然后总结方法。寻求为什么这么做，而不是怎么做。否则，不通过举一反三，而寄希望于在考试／面试时出现做过的内容，那就真是“以有崖求无崖，殆哉矣”。这里，我只谈方法。给个实例：
大家可能都觉得，算法题中动态规划是比较麻烦的问题。但当你碰到这类问题时，仔细总结过方法么？考虑过题目为什么要用动态规划么？动归和递归的区别在哪里？
我觉得，从子问题解决原问题, 无非是两种方法，自底向上(Bottom-Up)与自顶向下(Top-Down)，形式上前者对应iteration，利用循环将结果存在数组里，从数组起始位置向后计算；后者对应recursion，即利用函数调用自身实现，如果不储存上一个状态的解，则为递归，否则就是DP。举个斐波那契数列(0,1,1,2,3,5…)的例子：
1) 自底向上
int array[n] = {0};
array[1] = 1;
for (int i = 2; i < n; i++)
array = array[i-1] + array[i-2];
事实上，额外空间可以进一步缩小到O(1)：利用几个变量记录之前的状态即可。由于记录了子问题的解，故给出的方法就是DP。事实上，自底向上的方式往往都是通过动态规划实现。
2) 自顶向下
int Fibonacci(int n)
{
if(n == 0)
return 0;
if(n == 1)
return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
为计算Fibonacci的第n个元素，我们先自顶向下地计算子问题：第n-1个元素和第n-2个元素。由于没有储存子问题的运算结果，给出的方法是递归。然而，Fibonacci(n-1)与Fibonacci(n-2)包含很多重复的子问题，所以DP效率更高。如果用一个全局数组，将子问题的解储存到数组的对应位置，在重复计算的时候直接读取计算结果，那么就是DP的解法。
动态规划的核心在于，如果通往一个问题的solution，subproblem被重复计算，那么就可以利用记录中间结果，达到用空间换取时间的目的。在递归过程中用hash table记录中间计算结果的DP，称作Memoization。
Memoization的一般形式是: 建立以input为key，以output为value的hash table：
T func(N node, HashTable<N, T>& cache) {
If (cache.contains(node)) {
return cache.get(node);
}
…
T sub_res = func(next_node, cache);
…
T res = G( sub_res … ); //当前子问题的解，依赖于更小的子问题(s)
cache.set(node, res);
return res;
}
从解决问题的角度来说，用Bottom-Up的DP，固然通常可以节省递归本身的空间开销，但有很多缺点和局限：较难理解，边界条件较难处理，只适用于问题的节点空间是离散的整数空间，必须一步步邻接、连续地计算(无论是不是每一个节点的结果都会被用到)。而Memoization，则灵活得多：可以从递归形式轻易修改得到，也更符合普遍的思维过程，并且没有上面说的这些局限，子问题只有在被需要的时候才会被计算。尤其是在某些情况下，不仅需要aggregate的结果，还需要获得achieve这个结果的路径，这时候就算用Bottom-Up的DP，也需要记录prev节点，最后需要递归回溯得到路径，那么节省递归空间开销的优势，也荡然无存了。
那么Bottom-Up的DP可以解决哪类问题？我说，DP适用于解决“收敛结构问题”。所谓的“收敛结构问题”是指关于特解，或数量的问题（例如，第n个元素，第n步有多少种方法等）。这些问题都可以用整数坐标映射所有节点（即DP状态），且当前节点的解只依赖于前驱节点(无论是顺序还是倒序)。那么，这类问题往往可以用DP解决。解决的关键是建立subproblem的解之间的递推关系：
f(n) = G[f(n-1), f(n-2), … , f(1)] 或
f(i, j) = G[f(i-1, j-1), f(i, j -1), f(i-1,j)]
其中G[ ]表示子问题到原问题的映射关系，例如对于斐波那契数列，有递推式：
f(n) = G[f(n-1), f(n-2)] = f(n-1) + f(n-2)
但如果出现类似于“所有解”，“所有路径”等关键词，则用Top-down方法更为直接。
举一道简单的题目： Suppose we have a ladder which has n steps. Each time you can either climb 1 or 2 steps. Please write a function to calculate how many distinct ways that can you climb to the top?
解题分析：本问题描述了一个数量问题，属于前述的强收敛(聚合)性问题，可以用DP。DP的核心在于递推关系：当前节点的值可以由前驱走一步到达，或者前前驱走两步到达，即CountOfWays(n) = CountOfWays(n–1) + CountOfWays(n-2)；由于当前节点只与紧邻的两个节点决定，所以只需要2个临时变量来表示前驱节点的解即可，而不用DP table，因为更老的解我们不需要关心。在实现时，往往边界条件直接用if…then return value的形式，成为递归的出口。
因此，当理解到了一定的深度，真不是特别在乎做了多少题目。与之相关的另一个问题是，准备周期得有多长？这里，我只谈事实。看过我之前文章的朋友也知道，我本来是考虑转博的，但后来打算直接工作。我那时一月底开始准备，二月底投简历，到四月底一共onsite了12家公司拿了10个offer。不否认我的基础还算不错，科研也和软件相关，但也不算科班出身，硕士是ECE（在面试google的时候也暴露了CS知识面不够广的问题，所以G家也是我唯一技术上没过的公司）。
但是，我们准备的时候极其认真，效率远远超过现在工作。特别是他为了节约时间，一天只吃固定东西：中午越南粉，晚上Jack in the box或者互换。谈事实的目的就是，如果真正投入加仔细思考方法，几个月搞定心仪的工作也不是不可能。就看你理解的有多深。
大家可以比较下思考的深度。他笔记里的思想后来成了我们书的原型。
只练不想还有两个问题：
1. 看到类似的题目就硬套方法。当面试官要求换个思路时会感觉很困难
2. 看到没见过的题目有时就会慌，结果连正常水平也没发挥出来。
总而言之，希望大家能换个方向看刷题，与其做上两遍，三遍，不如花相同的时间认真总结下适合自己的方法。
https://www.zybuluo.com/smilence/note/76
Books
http://lbv-pc.blogspot.com/p/advice-for-beginners.html
- Programming Challenges by Skiena, Revilla.
- Competitive Programming by the Halim brothers (of World of Seven and uHunt fame).
And a few more academic ones, where the theory is more rigorously mathematical:
- The Algorithm Design Manual (a.k.a. the red book) by Skiena.
- Algorithm Design (a.k.a. the black book) by Kleinberg, Tardos.
- Introduction to Algorithms (a.k.a. CLR) by Cormen, Leiserson, Rivest.
- Concrete Mathematics by Graham, Knuth, Patashnik.
