Common Techniques: Advanced Interview Essentials
There are some common approaches to problems that, when you use them, can dramatically improve your programs. These techniques are more advanced, because it takes practice to be able to identify problems where these approaches work well. Two tricky approaches that apply to a broad range of problems are:
- Greedy Algorithms: an approach to optimizing a “score” through a sequence of choices, which only uses the choice that makes the largest immediate improvement;
- Divide and Conquer: a technique that breaks problems into smaller (and easier) subproblems before merging them back to a solution of the original problem.
This section also looks at problems whose solutions utilize disjoint sets, which allow us to group a collection of objects into non-overlapping sets. This fast and powerful data structure enables us to quickly label objects as belonging together.