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
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s