Notes about programming

Online Algorithm - mean and median

This post discusses so-called Online Algorithm. If fixed number of integers (or real numbers) are given, it’s easy to find a mean or median. Summing up all, then dividing by a number of given values gives us the mean. For a median, sorting the given values then finding center index (indices) would be the all.

Trapping Rain Water

“Trapping Rain Water” is one more famous algorithm problem using bars, like Skyline Problem or Lagest Rectangle in a Histogram. Compared to other two bar chart problems, this was an easier problem once I understood what I should focus on. Also, solutions are posted on many websites, which helped to solve.

Skyline Problem

The skyline problem is another famous algorithm problem using bars, like Lagest Rectangle in a Histogram. Although the problem is described using bars, it is totally another problem compared to the largest rectangle. The skyline problem asks range maximum values.

Largest Rectangle in a Histogram

“Find the largest rectangular area in a histogram” is a famous algorithm problem using bars. There are some types of problems expressed by bars such as trapping water or skyline. Those look like similar since all are plotted on 2D plain multiple bars on. However, how to think and solve the problems are not the same. What data structure and algorithm can be applied to solve problems effectively is, sometime, confusing. For this reason, I’m going to add this topic to my memo.

You can do it by XOR

This post is about XOR bit manipulations. XOR is surprisingly capable of solving various algorithm problems.