Contains Duplicate

Good day! It is Thursday morning and it is a typical gloomy and cold winter day in the Twin Cities of Minneapolis and St. Paul. The good thing is that is Thursday. One more day to go to and we can start enjoying the weekend. For most of us the weekend will be 2-days long. It is different from the past two weekends in which most people enjoyed 3 or 4 days off work.

Due to COVID-19 my wife and I just leave home for grocery shopping and healthcare appoints when needed. The good thing is that vaccination has started in the USA and hopefully in a few more months most of us will be vaccinated and can start getting back to normal. We all will see what happens. Continue reading “Contains Duplicate”

Revenue Milestones in Java

Good day ladies and gentlemen. Today is Wednesday January 06, 2021. The claims of electoral fraud in the 2020 presidential elections in the USA continue to be brought up. One way or the other January 20 is about two weeks away. If the claims do not pan out then on that day we will have a new president be sworn in. We will be able to read news without political opinions.

Earlier today my wife fixed a delicious chicken dish with a white sauce with lemon and capers. She served it with rice, baked potatoes and beats. For desert we had chocolate ice cream followed by a triple espresso. That marked the middle of my day. In the afternoon I finished two additional 2-hour blocks. Continue reading “Revenue Milestones in Java”

Continuous Subarray Sum

Tomorrow is Thanksgiving Day 2020. My wife finished preparing three containers with cheesy potatoes casserole. She has been making this dish as far as I can remember. Due to the ingredients we tend to have it once or twice a day. I will provide the recipe and some pictures on tomorrows post. If I am not able to solve a problem and generate a post, will generate a post as soon as possible.

We are still in the midst of the COVID-19 pandemic. About two million people around the world have die of complications related to the novel coronavirus. My wife and I have some friends’ originally from Vietnam. We learned today that one of them is in the hospital and the other barely making it at home. One of my wife’s brothers has been diagnosed with COVID-19. He, his wife and two kids are in quarantine at home. Our best wishes and our thoughts go out to them for a quick and safe recovery. Continue reading “Continuous Subarray Sum”

Is Permutation

Let’s define the requirements for this algorithm. We are given two sets of integers. The idea is to check if the sets are permutations of each other. If they are, return YES; otherwise return NO.

First let’s make sure we agree with the definition of permutation. For the sets to be permutations we must have the same number of elements in both sets. Each set must have the same counts for each entry. For example if the sets are:

1 2 3 4 5 6

6 5 4 3 2 1

Then we would return YES. Both sets have the same length (six in this case) the numbers are the same on both sets, and the count of each number matches (one in this case).

7 6 5 0 9 7

7 6 1 0 9 7

Given that 5 is in the first set, but not in the second and 1 is in the second, but not in the first, these are not permutations of each other so we would return NO. Continue reading “Is Permutation”

Simple Array Sum

It is a sunny but not so warm day in the Twin Cities of Minneapolis and St. Paul. The high for today will be 68 F which is a few degrees below the average high for this time of the year. Looks like a perfect day for a walk. My wife and I will be out and about after work today.

This HackerRank challenge is quite simple. The reason I went for it is due to the fact that a few weeks ago I exchanged some messages with JAVAAID. He has a YouTube channel and solves HackerRank challenges. Continue reading “Simple Array Sum”

Java 1D Array (Part 2)

It has been one of those days. Yesterday morning I was working in my home office when some noise coming from the utilities room called my attention. A week or so ago, a contractor on behalf of the City of Apple Valley stopped by to replace the water meter. Apparently the new meters are able to send data for billing purposes. Two people came in. One was a trainee and the other was supervising the operation. They cut off the water supply inside the house, installed the new meter in the line, and  turned back on the water supply. All seemed well. I checked that evening and no leaks. All seemed well at the time.

Yesterday the sounds coming from the utility room seem to indicate something was dripping. I went and check and tater was coming from the connection that they made. We immediately called the City of Apple Valley. I took some pictures.  Two hours later a representative of the contractor and a Public Works Supervisor from the city showed up.

The issue was simple to fix. They shut off the water and inserted a plastic / rubber ring that was missing. They did find one or two rings in the area around the meter. Apparently it fell twice and the people that made the installation only noticed the ring falling out of place once. Continue reading “Java 1D Array (Part 2)”

Equal Stacks

While I was waiting for some tests to complete I checked my Gmail and found a message from HackerRank suggesting a challenge. The Equal Stacks challenge may be found under Practice > Data Structures > Stacks > Equal Stacks. I read the description for the problem and decided to tackle it using stacks; how creative of me. Continue reading “Equal Stacks”

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

Autocomplete

trie_diagramYesterday evening I was talking with a software manager about an algorithm to autocomplete words. The idea was to build a data structure that could help (hint) users with the available words that would match what has been entered so far. For example, if someone would be looking for my phone number in a company directory application and would have entered “can” then the autocomplete feature could display “cane” and “canessa”. Continue reading “Autocomplete”