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.
12/22/2016 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.
12/14/2016 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. And there is a superficial relationship between D&C and DP. And an underlying relationship between topological sort of a DAG and subproblems of a DP question.
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. Because it is my first coding language and I have used it for 4 years. 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.
12/3/2016 New Note: If I do a second run on LC, I will do all the problems in python and post the solutions here.
Readings
- Mathematical Recreation by Henri Poincaré
- The Two Cultures of Mathematics by W. T. Gowers