Parse Text

UPDATE – April 09, 2018When I started this post, I was thinking in several follow ups in order to try different approaches and be able to continue to improve on previous passes by adding code or starting from scratch when a new idea came up. I was interested in showing a normal progression that the reader would encounter when developing software. In the days that passed, I decided to limit the subject to a single post. Please let me know if you encounter an issue or would like for me to expand on this entry.

Sometime last week I attempted to solve a simple online challenge. The challenge dealt with parsing a string of text and then obtaining information from the string. There are probably thousands of variants to the challenge. I am not going to cover the exact challenge in this post. I will make my own. Will start simple and will get more complex each time we add a new obstacle. Continue reading “Parse Text”

New, Duplicate or in Segment

This is my first attempt to create a set of two challenges for HackerRank. If you are interested in generating a new challenge you should try the Challenge Guidelines link and read all about how to proceed.

After reading the guidelines I created the following information for the “New, Duplicate or In Segment” challenge: Continue reading “New, Duplicate or in Segment”

Overload Operators C++

Over the weekend I received an automated email message from HackerRank to solve the following challenge: https://www.hackerrank.com/challenges/overload-operators?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign

If interested, please take a look at the challenge description.

As usual, I try to address the challenge without consulting the provided code or look at the discussions. After losing some time on my own, I check the discussions and the code provided to solve the challenge. In this case the following read only code was provided: Continue reading “Overload Operators C++”

Introduction Challenges C++

As I mentioned in a previous post, I will be solving challenges using C++ and Java. Earlier today I found in HackerRank a set of challenges for C++. The set seems to be split into the following categories:

  • Introduction
  • Strings
  • Classes
  • STL
  • Inheritance
  • Other Concepts

As usual, I like to start simple and progress towards the most complicated. In this blog entry I cover my solutions written in C++ using Microsoft Visual Studio 2013 Professional. Continue reading “Introduction Challenges C++”

Down to Zero II

This post is related to HackerRank challenge “Down to Zero II” which seems to require dynamic programming to get it solved. I tried a top down (which I modified into a bottom up) approach. Sorry but I overwrote the code for my first approach. Should have started a new method or saved it in Git.

Please take a look at the challenge at:  https://www.hackerrank.com/challenges/down-to-zero-ii

The idea of Dynamic Programming is to attempt to use existing solutions instead of computing them again each time a similar problem needs to be solved. For example, if you have computer a factor for 32 = 2 * 2 * 2 * 2 * 2 (or 2^5), then when you are computing 64 = 32 * 2 (or 2^6) you could just look up the result associated with 32 and incorporate it into the solution of 64. Continue reading “Down to Zero II”

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

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”