yokolet's notelets

As a lisp family language programmer, I used to write a lot of parentheses. Specifically, ( and ). In an algorithm world, parentheses often includes other brackets as well, such as {} or [], but that’s it. At most three types of pairs are there, some problems are much complicated to find a solution. This post is about such problems.

“Count how may ways to do …” is one type of algorithm questions. For example, count ways to climb up stairs, count ways to make sum by given coins, or count ways to reach from top left to bottom right corner.

We often see problems related to a palindrome or palindromic something. Palindrome is, like “racecar,” a reversed and original are exactly the same string. We see really many types of palindrome related problems. Sometime, problems are based on palindromic substrings. Sometime, those are palindromic subsequences.

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

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.

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

This post is about XOR bit manipulations. XOR is surprisingly capable of solving various algorithm problems. Let’s dig deep to see how we can use XOR.

Let’s think how we can divide an array of integers into K fair amount groups. The problem description is: given an array of integers, divide into k subarrays so that the differences of sum of each subarray will be minimized. Keep the order of the given array.

Let’s count smaller on the right in an array. More precisely, the problem is: given an array of integers, count integers smaller than the index i, also, located on the right of index i. So, the answer will be also an array of the integers. Apparently, the answer to the last element is 0.