Programming Pearls

Exercises from the famous Programming Pearls by Jon Bentley.

---

Current content

Column 1

• Fast system sort implementation using a bitmap data structure along with an efficient algorithm for sampling k unique elements in range [1, n], for which I used the floyd's random sampling algorithm. The problem is to design an efficient algorithm to sort a list of 1,000,000 distinct positive elements all lesser than 10,000,000 using lesser than 2 MB storage. The sorting algorithm designed here beats the Java system sort by a factor of 4.

Column 2 - Algorithms

• Group anagrams in a list of words. Solved by assigning each word a signature that is its sorted form and grouping all words with the same signature together.
• Rotate a vector by i positions in-place. Boils down to changing vector ab to ba where a and b represent a contiguous block of elements. This is elegantly solved by employing a bunch of reverse operations on the array.
• Rotate matrix in place. Solved by using an in-place transposition algorithm.

Column 3 - Data Structures

• Design a clean and maintable algorithm to process tax amounts for various input incomes. Key was to use an array.

Column 8 - Algorithm Design Techniques

• A turnpike consists of n - 1 streches of road between n toll stations. Each strech has an associated cost of travel. Design a data structure that requires O(n) space but allows the cost of any route to be computed in constant time. Key was the use of prefix arrays.

Column 14 - Heaps

• Implement a Priority Queue.
• Implemented a sequencial disk access method that adds an additional pointer to every node to enable logarithmic index access time. Time and space complexity is log(n) when there are n elements in the list. The logarithmic access time is achieved by storing an additional jump pointer at every node. The functionality is similar to that of finding the ith power of a number in log(i) time. For example, to find the 5th element, we would visit 5 -> 4 -> 2 -> 1.
• Implemented an algorithm to produce matches given the rankings of players. Used a BFS like approach.

Column 15 - String Of Pearls

• Find the longest repeated substring in a string. Example, LRS(banana) = ana. The problem can be solved using suffix arrays.
• Given a new input string, how would you search a suffix array to find the longest match in the given text? Solved using binary search.