文件列表:

LICENSE (18047, 2015-10-14)
column-eight-algorithm-design-techniques/ (0, 2015-10-14)
column-eight-algorithm-design-techniques/turnpike.py (597, 2015-10-14)
column-fifteen-strings/ (0, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/ (0, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/.classpath (372, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/.project (383, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/.settings/ (0, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/.settings/org.eclipse.jdt.core.prefs (587, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/src/ (0, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/src/LRS.java (1161, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/src/Main.java (145, 2015-10-14)
column-fifteen-strings/LongestRepeatedSubstring/src/TestLRS.java (482, 2015-10-14)
column-fifteen-strings/StringSearch/ (0, 2015-10-14)
column-fifteen-strings/StringSearch/.classpath (226, 2015-10-14)
column-fifteen-strings/StringSearch/.project (371, 2015-10-14)
column-fifteen-strings/StringSearch/src/ (0, 2015-10-14)
column-fifteen-strings/StringSearch/src/Main.java (176, 2015-10-14)
column-fifteen-strings/StringSearch/src/StringSearch.java (1973, 2015-10-14)
column-fourteen-heaps/ (0, 2015-10-14)
column-fourteen-heaps/PriorityQueue/ (0, 2015-10-14)
column-fourteen-heaps/PriorityQueue/.classpath (226, 2015-10-14)
column-fourteen-heaps/PriorityQueue/.project (372, 2015-10-14)
column-fourteen-heaps/PriorityQueue/src/ (0, 2015-10-14)
column-fourteen-heaps/PriorityQueue/src/Container.java (514, 2015-10-14)
column-fourteen-heaps/PriorityQueue/src/EmptyHeapException.java (713, 2015-10-14)
column-fourteen-heaps/PriorityQueue/src/Main.java (647, 2015-10-14)
column-fourteen-heaps/PriorityQueue/src/PriorityQueue.java (3318, 2015-10-14)
column-fourteen-heaps/PriorityQueue/src/SizeOverflowException.java (731, 2015-10-14)
column-fourteen-heaps/SeedPlayer/ (0, 2015-10-14)
column-fourteen-heaps/SeedPlayer/.classpath (376, 2015-10-14)
column-fourteen-heaps/SeedPlayer/.project (426, 2015-10-14)
column-fourteen-heaps/SeedPlayer/.settings/ (0, 2015-10-14)
column-fourteen-heaps/SeedPlayer/.settings/org.eclipse.jdt.core.prefs (587, 2015-10-14)
column-fourteen-heaps/SeedPlayer/src/ (0, 2015-10-14)
column-fourteen-heaps/SeedPlayer/src/seed/ (0, 2015-10-14)
column-fourteen-heaps/SeedPlayer/src/seed/Main.scala (152, 2015-10-14)
... ...

# 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.**

近期下载者：

相关文件：

评论：[我要评论] [举报此文件]

收藏者：