Last updated: Feb, 2015
The list below includes my practice on problems from Leetcode Online Judge. Various online resources are of great help in such as process, including Leetcode OJ forums and this blog. I mostly write them in Python but will add solutions in C++ or Java later.
Merge and sort:
K-sum problems:
When to use binary search: if the object is somewhat “sorted”, then it has potential to be applied with binary search.
Many matrix problems here do not involve fancy algorithms and data structures. However, index manipulation can be tedious and error prone.
In C++ or Java, one may need to worry about the int type overflow in some of those problem .
Dynamic programming problems exist in many forms. The first step is to tell if the problem can be solved by dynamic programming paradigm, and then try to find the recurrence relationship. Note that dynamic programming problems are not only solvable by recursive design: they can also be done by iterative programs, which may or may not be more efficient. For the recursive approach, one needs to design the API of the recursive call. Some API design is more elegant and efficient that others.
Prototype problems of using dynamic programming: counting/listing different ways of doing something, tree operations, some program using a stack, etc. A good article on this topic is “dynamic programming: from novice to advanced”.
Basic tree traversal methods include preorder, postorder, inorder and level order. The preorder, postorder and inorder traversal can be realized recursively or interatively (using a stack). Level order traversal is realized iteratively using a queue. Zigzag level order traversal is a variant using stacks.
Binary tree properties:
Path sum problems:
Binary search trees.