Before We Begin
Some strategies and resources. We need a map and a somewhat good plan before we start our journey in the wonderland.
Algorithmic Thinking
"Computer science is really not about programming. It's generally more about problem solving and about careful, methodical, and efficient thinking." - CS50
Understanding An Algorithm (or Proof)
Textbooks follow a very formal or Euclid inspired system to present algorithms (or theorems). It normally goes like definition -> lemma -> theorem -> proof. The flow is very elegant and perfect. But But But, this is totally the reverse of how human think. These famous textbooks don't really explain the thought process behind the scene. It is critical for you to look for and hunt down the origin. To understand and use an algorithm/theorem, you need to know the proof. But to understand and recreate the proof, you must know the thought process and history behind the proof.
Problem Solving
Questions on LC are increasing daily. Solving all the possible questions is madness. But the tags stay the same. So we use the problems available to get a better understand of the underlying concepts.
Problem solving flow:
listen/read the question carefully
do a few examples (ask questions to clarify)
come up the obvious / brute force sol
optimize the sol (infer a paradigm from the given properties ex. sorted → two pointers / bsearch, overlapping subproblems → memoization)
walk through the opt approach in details
now write your clean and beautiful code
test normal input, small/large input, empty/null input, trace through the code
Order of Topics
Basic data structures are the foundation of algorithm design of any kind. So placing it as our first topic is indisputable. The following topics, however, are design techniques that are relatively independent from each other. In this note, I decide to put them in increasing order in terms of their level of difficulties.
New Note: It turned out the most textbooks had their reasons to put them in this order. Because as you will see, there are natural graph questions (i.e. MST) that can be solved with a greedy approach. One needs to understand recursion or DFS first before getting the hang of memoization in DP. Also, in most DP questions, we can visualize the subproblems as states in a DAG then perform a topological sort on them.
New Note 2: Every topic seems to be connected. Let's just use DP as an example. DP is just a smarter exhaustive search. And how DP works is really an enhanced version of greedy algorithms. Instead of just making one optimal choice, we are trying a collection of choices and guaranteed to find one optimal choice in that collection. DP is finding shortest path in a DAG. DP is D&C in disguise (the thought process being bottom-up). If the problem has do with string or sequences, we can use 1D or 2D array to memoize the solution. If the problem has a to do with a data structure (tree, trie, grid, graph), then we can just memoize it in that data structure.
Choice of Language
Most coding interviews accept solutions written in Java, C++, and python. Java has the richest online resources and books for coding interview. But python is the newly crowned king. Its elegance gives you a much better chance to be bug free and finish on time. On the contrary to all the reasons above, C++ is not recommended.
The solutions given here will be in Java. Still, I hope you will find the thought process helpful so that you can implement the solution in any language you wish.
Note: In the spirit of algorithmic questions, we only care about computational complexity instead of the runtime of real code. The fact that python is interpreted (so it can be slower in practice) does not matter to us.
New Note: I will try do post some solutions in Python if decide to do a second run .
Implementation
This is the topic that I ignored when I first wrote this section. Implementing an algorithm is not as glorious as coming up with one. It is language dependent and can be trivial at times. Instead of considering it as a drudgery, we can view it as an opportunity to not only materialize our understanding on the algorithm, but also to reinforce our mastery on our favorite programming languages.
Readings
Last updated