# Web Browsing Behind the Scene

Have you ever wondered how a web page is displayed in the browser once you type an URL and press enter? What happens behind the scene is actually quite complex and interesting, though all of them complete in seconds and thus is usually transparent to users.

# 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.

# Sorting (3): Special Linear Time Scenarios

Can sorting be even faster while we’ve mentioned in the previous article that the upper bound of sorting is O(nlogn)? The answer is yes! We can do sorting in linear time if the data set meets certain conditions.

# 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.

# Sorting (1): Popular Quadratic Time Algorithms

Sorting algorithms are useful and commonly used for the pre-processing of a data set. Here we look at three simply sorting algorithms that have a quadratic time complexity. We also visit the property of each of them, in particular, the stability of sorting algorithms.

# 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.

# Binary Tree Iterative Traversal

Binary tree traversal is a perfect case to show the power of recursive algorithms which enable straightforward and trivial implementations of all three traversal styles (in-order, pre-order, and post-order). Given its simplicity, recursion is not the focus of this article. Instead, we are looking into how to do it iteratively.

# Directed Graph Traversal and Cycle Detection

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.

# 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.

# Snapshot Isolation With Versioning (2): Version Storage

Versioning can be used to support the isolation among transactions via snapshotting (i.e., snapshot isolation level). While one transaction is editing the data, the other transactions should only be able to see the original data before the edit. In order to achieve that, both of the original and new data are kept. That is, we maintain versions of the data.