Strings – Making Anagrams

anagram_sampleIn this blog entry I generated a solution for the Strings: Making Anagrams challenge at HackerRank.

For a description of the challenge please refer to the HackerRank web site using Strings: Making Anagrams.

I received a comment regarding two items:

Item Comment
1 I can’t see the utility of the line char c = s.charAt(i);
2 And the line hist += 1; has incompatibility error.

It has been almost a year since I posted this entry. Had to look through several workspaces to locate the actual source code and updates the project. Today I am using Eclipse IDE Version: Oxygen.1a Release (4.7.1a). Apparently the projects in that workspace were not compatible. Eclipse did whatever it needed to do and the source code appeared on the screen. Ran the code and all seems to be working fine.

Item 1

The only reason for it is testing. I like to see what the code is doing. I write several hundred thousand lines of code a year using different programming languages and IDEs. I like to use simple and easy to follow code. Typically with enough comments that remind me what and why I wrote code segments (which may be single lines).

The line in question could have been condensed as follows:

			// **** get the current character from the string ****
			
			char c = s.charAt(i);
			
			// **** increment the frequency associated with this character in the histogram ****
			
			hist += 1;
			
			// **** alternately condensing the above two statements into one ****
			
//			hist[s.charAt(i) - 'a'] += 1;

Item 2

Not sure why that statement is producing such error. The actual statement is:

hist += 1;	// NOT:  hist+= 1;

Lately (in the past year or so), I am using a different mechanism to surround code which produces nice output. The previous mechanism was not that great. Sorry is that caused confusions.

Following is a console screen capture of the Eclipse IDE when I tried the sample data:

cde
abc
<<< hist: c(1) d(1) e(1) 
<<< hist: a(1) b(1) c(1) 
numberNeeded <<< deleted: 4
4

The proper answer is 4. The reason for this is that ‘d’, ‘e’, ‘a’ and ‘b’ characters are not in both strings.

The approach that I used is to generate two histograms with the character counts in each string. The counts in the arrays are in alphabetic order where ‘a’ matches 0, ‘b’ matches 1 and so forth and so on. The final logic is to determine how many characters are in one array but not in the other.

The actual Java code for my solution follows:

package john.canessa.anagrams;

import java.util.Scanner;

public class Solution {

	final private static int totalLetters 	= 26;	// [a - z]

	/*
	 * print histogram
	 */
	private static void print(int[] hist) {
		System.out.print("<<< hist: ");
		for (int i = 0; i < totalLetters; i++) {
			if (hist[i] != 0) {
				System.out.print((char)(i + 'a') + "(" + hist[i] + ") ");
			}
		}
		System.out.println();
	}
	
	/*
	 * array with histogram of letters
	 */
	private static int[] histogram(String s) {
		int[] hist = new int[totalLetters];
		
		// **** traverse the string from start to finish ****
		
		for (int i = 0; i < s.length(); i++) {
			
			// **** get the current character from the string ****
			
			char c = s.charAt(i);
			
			// **** increment the frequency associated with this character in the histogram ****
			
			hist += 1;
			
			// **** alternately condensing the above two statements into one ****
			
//			hist[s.charAt(i) - 'a'] += 1;
		}
		return hist;
	}
	
	/*
	 * count characters needed to be deleted from both histograms
	 */
	private static int countCharacters(int[] firstHist, int[] secondHist) {
		int deleted	= 0;
		for (int i = 0; i < totalLetters; i++) {
			if (firstHist[i] != secondHist[i]) {
				deleted += Math.abs(firstHist[i] - secondHist[i]);
			}
		}
		return deleted;
	}
	
	/*
	 * count number of deleted characters
	 */
	public static int numberNeeded(String first, String second) {
		int	deleted	= 0;
		
		// **** build histogram with letters from first string ****
		
		int[] firstHist = histogram(first);
		print(firstHist);
		
		// **** build histogram with letters from second string ****
		
		int[] secondHist = histogram(second);
		print(secondHist);

		// **** count different characters on histograms ****
		
		deleted = countCharacters(firstHist, secondHist);
		System.out.println("numberNeeded <<< deleted: " + deleted);

		// **** return number of deleted characters ****
		
		return deleted;
	}

	/*
	 * test code
	 */
	public static void main(String[] args) {
		Scanner in 	= new Scanner(System.in);
		String a 	= in.next();
		String b 	= in.next();
		in.close();
		System.out.println(numberNeeded(a, b));
	}
}

The print() method is used for testing purposes only. References to that method are commented out in the final solution.

If you have comments or questions on this or any other blog entry, please send me a message via email.

John

www.johncanessa.com

Follow me on Twitter:  @john_canessa

Arrays – Rotate Left

rotate_arrayThis is the first of a set of challenges (I believe the series / set is relatively new) in the HackerRank web site. You may find them at HackerRank under All Domains -> Tutorials -> Cracking the Coding Interview.

The challenge is to develop the body for a method / function that rotates left an array of n integers k times. Continue reading “Arrays – Rotate Left”

Shell Sort

shell_sortI spent some time reading (section 2.1 in the Algorithms fourth edition by Robert Sedgewick and Kevin Wayne) and experimenting with the Shell Sort algorithm.

The Shell sort algorithm is an optimized Insertion sort. The idea is to reduce the number of exchanges by presorting elements in sub sequences. Continue reading “Shell Sort”

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”