Java Recursion, DP and greedy
The three techniques that cover the harder half of coding rounds, and the questions that check you know which applies.
3 concepts · 9 interview questions
What this topic covers
Every concept in recursion, dp and greedy, and the questions each one gets asked as. Where a question links, it has a full write-up.
Recursion and backtracking
Solving a problem in terms of a smaller instance, and undoing a choice when it leads nowhere. Every recursion needs a base case and a shrinking argument.
- Generate all subsets, or all permutations, of a list.
- Solve the n-queens problem, and say what makes it backtracking.
- How deep can Java recurse, and what happens then?
Dynamic programming
Recursion where subproblems repeat, so results are remembered. Recognising the overlap is the whole difficulty.
- What tells you a problem is dynamic programming?
- Memoisation or tabulation?
- Solve the coin change problem and state its complexity.
Greedy algorithms
Taking the locally best option at each step. Fast and often correct, but only provably so when the problem has the right structure.
- When is a greedy choice provably correct?
- Schedule the maximum number of non-overlapping intervals.
- Give an example where greedy fails and DP succeeds.