Programming Pearls Col 2 – Aha! Algorithms

Column 2 introduced models to solutions to the classical “group anagrams”, “string rotation” and “finding duplicates” problems. The author used very simple mathematical principles to design solutions and called them aha! insights. Then variations to the principles are applied in the implementation of the solution in regards to the problem.

Group anagrams: using a signature for each group of anagrams (sorting one of the anagrams and using as key to bucket in hash map)

String rotation:

1. x modulo n – x is the length of the string and n is the number of rotations. This solution ends up using constant memory and linear time. But it only works when x is divisible by n. (slow in time, efficient in memory)
2. Reversal: String as ab, a is characters [0, i). Place a in its final position, then reverse the rest recursively. (spikes in intervals)
3. Block reverse: Separate string into a and b and reverse recursively: in every step, reverse a to get a’, reverse b to get b’, and (a’b’)’ to obtain ba. Apply this principle to convert three partitions (abc to cba) – reverse either ab or bc, reverse the rest, then reverse the whole string. (fastest long-term)

Finding duplicates:

1. Extracting a small portion of data each time to use binary search on it. This solution has stable performance.
2. Another solution I was thinking is XORing bit patterns and output the first bit pattern that outputted 0. Although its worst case is O(N), it can potentially reach the goal faster than binary search in some cases