Union-Find and Adapter Design Pattern

weighted-quick-unionEarlier today I finished reading chapter 1.5 Case Study: Union-Find in the Algorithms Fourth Edition book by Robert Sedgewick and Kevin Wayne published by Addison-Wesley. Not sure if the authors recommend reading the chapters in order because they tend to use previous material. Last week I was browsing the table of contents and decided to read chapter 4.1. It mentions contents of chapter 1.5. From now on, I will read the book in order ;o)

It is always good to work on a single topic. I am breaking that rule to some extent. I will cover two very similar implementations of the Union-Find algorithm from chapter 1.5. It does give an introductory flavor for what is to come in chapter 4.1 Undirected Graphs. Continue reading “Union-Find and Adapter Design Pattern”

Anagrams of a Word

anagram_sampleLast week I was talking with a software engineer. While chatting the description of a problem / challenge came up. The description, as far as I can recall, follows:

“Given a text file with all (most would be more precise) English language words in lower-case, find all anagrams for a specified word”.

An example of an anagram was discussed. At the time I was thinking on palindromes and was not able to concentrate on the definition of anagrams. I thought that an anagram consists of a set of letters in any order and letters may repeat. For example, “ana” and “anna” would fit my incorrect definition. I mentioned that I would spend some time on my own and come up with a solution. Continue reading “Anagrams of a Word”

Top 10 Words in a Text File

how-to-find-highest-repeating-word-from-a-file-in-javaThis entry describes the implementation of an algorithm used to display the top ten (the number is just a constant in the solution) words found in a text file. The solution is implemented in Java.

As is typical, a challenge is described by some requirements. The requirements for this challenge follows:

“Given a text file holding some text (a few thousand words) generate the list of the top ten words found in the text file”. Continue reading “Top 10 Words in a Text File”

Split Words

splitstringI have had a stressful week. Glad the weekend arrived. Today I will provide my solution, including the thinking process, to a common and quite popular programming challenge. I have encountered several variations of it. The base problem follows:

“Split a text string into words. Words only contain ASCII letters which for simplicity may be treated as lower (a – z) or upper case (A – Z) characters (developer’s choice)”.

Continue reading “Split Words”

Fraction Recurring Decimal

recurring_decimalsFor the past few months I had been working attempting to solve a challenge per day on HackerRank. I like that site. A couple weeks ago I was introduced to LeetCode. Challenges seem to be more intense and requirements seem to be vaguer. Knowing this, one needs to think and plan the approach / algorithm with greater care and expect to fail unit tests that one would not think off. I just finished a challenge and decided to post in this blog my approach to solving it. Continue reading “Fraction Recurring Decimal”

Count Ones

binary_counts_with_fingersHere is a simple task. Given an array of 10,000 random unsigned short integers (16-bit values) count the number of bits set to one (1). In the following example we have an array of two (2) unsigned shorts:

41344 1010000110000000

58520 1110010010011000

The first number 41,344 contains 4 ones and the second value 58,520 contains 7 ones for a total of (4 + 7) = 11 ones. Continue reading “Count Ones”

No Prefix Set

weekend_on_line_classAs I have mentioned in a previous blog I am currently taking a weekend on-line course on Spring Framework. Last Wednesday my computer received a Windows update labeled “Cumulative Update for Windows 10 Version 1511 for x64-based Systems (KB3185614)”. For some reason the update failed to install on Thursday. After rebooting my machine the installation process continued. A few minutes later it indicated a failure and the system was being restored. The entire process took over one hour. Continue reading “No Prefix Set”