System Design: Common Performance Numbers

The performance a computer system is related to its physical properties. Knowing some of those common performance numbers helps us develop an intuition for the hardware. With that, we are able to evaluate a system design without first building it. It also allows us to think more thoroughly when making decisions for system design.

Read More

Algorithm Cheat Sheet: Sorting with Divide and Conquer

Sorting can be done faster than quadratic time. Two of such sorting algorithms are based on the principle of divide and conquer. Divide and conquer is a strategy that helps simplify solving a complex problem. It begins by dividing a problem into sub-problems. It then keeps doing that until the sub-problem is trivial to solve. In the end the outcomes of each sub-problem are assembled backwards and eventually lead to the result of the whole problem.

Read More

Algorithm Cheat Sheet: Binary Tree Morris Traversal

Morris traversal does not need to rely on recursion or stacks. Instead, it reorganize the tree into a thread that forms a certain sequence. It does modify the structure of the original tree. When that is not a concern, Morris traversal is able to achieve the optimal time and space complexity. Morris traversal is original designed for in-order traversal, but it can be applied to pre-order traversal as well, though I am not sure if it’s applicable to post-order traversal.

Read More

Algorithm Cheat Sheet: Graph Traversal

When traversing a graph, one typical question we are interested in is whether the graph contains cycles. For directed graphs, a cycle often indicates the conflict between dependencies. There are two approaches to traverse a graph and identify cycles, the breadth-first and depth-first searches.

Read More

Algorithm Cheat Sheet: Two Pointers

When dealing with arrays or lists, we tend to think in the single-threaded way and scan the array or list with one pointer. Sometimes working concurrently through two pointers can help make things more clear and efficient. For example, problems can thus be solved within one pass instead of two. In some cases, solutions can also involve much less space usage.

Read More