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

Sorting (2): 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 sub-problems are trivial to solve. In the end, outcomes of all sub-problems are assembled backwards, which eventually gives the final result of the whole problem.

Read More

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

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