I-Node Ext2 Linux File System

minix_mascotA few weeks ago I was talking with a colleague about Linux file systems. There are several file systems supported by the Linux operating system some of which have been created for it (e.g., Ext2, Ext3, Ext4) and other by different vendors (e.g., FAT, FAT32, HFS, MINIX, NTFS, System V, BSD).

Every time I run into MINIX it brings up good old memories. It was used at school to teach operating systems. I purchase a book that came with a copy of the OS. It could boot in a regular PC. Continue reading “I-Node Ext2 Linux File System”

Reverse Fibonacci Series

fibonacci_sequenceEarlier today I was looking at a challenge. The problem was stated as:

“Print in reverse order a Fibonacci series”.

I have learned and used a couple times the Fibonacci series but time goes by and I am a firm believer that one should not memorize what you can look up. Software developers would look up the definition or better yet, a Class and associated method that would generate it.

Let’s start with a definition of what a Fibonacci number is from Wikipedia: Continue reading “Reverse Fibonacci Series”

Valid Anagram

sample_anagramIt seems like anagrams are becoming quite popular in challenges. What is an anagram? The edited definition from Wikipedia follows:

“An anagram is direct word switch or word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once. Any word or phrase that exactly reproduces the letters in another order is an anagram”. Continue reading “Valid Anagram”

Sort Comparisons

selection_sortThis entry implements a class to compare a couple (more to come in the next few days) sorting algorithms. The Java code is based on examples from the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne.

As you might already know, both Selection and Insertion sorts have a complexity of O(n^2). That said; in practice Insertion seems to be faster than Selection. If you take a look at the implementations, it is easy to insertion_sortdetermine that both algorithms use nested loops, but the number of cycles in the inner loops is dependent on the initial order of elements in the array for one of the sorts. Continue reading “Sort Comparisons”

Insertion Sort

insertion-sortMoving along in the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne, I experimented with the Insertion sort algorithm. Visit the https://en.wikipedia.org/wiki/Insertion_sort web site to view an animation of the algorithm. As you can see, it resembles a person arranging playing cards for a game of bridge.

The way the authors described the API to the sorting algorithms allow this one to be quite elegant and compact.
Continue reading “Insertion Sort”

Selection Sort

selection_sortContinue to read and experiment with most of the exercises in the Algorithms fourth edition book by Robert Sedgewick and Kevin Wayne. I am currently reading chapter 2.1 Elementary Sorts. I just finished the section that deals with Selection sort. The subject matter is well described and a set of methods (with possible some exceptions) will be used to implement all the sorting algorithms in this chapter. That is quite nice because it emphasizes on the concept of hiding data and the actual algorithm from clients.

The following methods are common to all sorting algorithms described in the second chapter: Continue reading “Selection Sort”

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”