Earlier this morning I spoke with my friend Gustavo. We know each other for most of our lives. We started kindergarten together. Today we are both married to our respective spouses and have kids and grand kids. We get on Skype about once a month always on a Friday at 06:00 AM and have a great time catching up.
He studied geology and currently owns a company that was started by his dad. He bought out his siblings and with time has grown his company quite a lot. Last time we got together was for a geology convention last year in the Twin Cities of Minneapolis and St. Paul. We had a great time with our spouses dining, dining and doing tourist things. The only thing of the trip they did not like was the snow. The show was in February and there was a lot of snow and of course cold temperatures.
Yesterday he mentioned that he finally got awarded a patent that took him a 
few years to complete. We both know that filling patents can take time.
On a separate note, I read an article that mentioned coderbyte. The site provides coding problems at three levels to help developers sharpen their coding skills. I decided to give a try the challenge that was described on the article that I read and twitted.
If you are interested the name of the challenge rated EASY is Find Intersection.
The idea is to return a string with the numbers that are in two strings provided as input. The numbers in the strings are in monotonically ascending order. The strings are not empty. The strings may contain negative integers.
I used Java for my solution and used the Visual Studio Code IDE. It seems that VS Code is becoming very popular with the development community. It is free and has a large number of extensions. Have been using it on and off for a few months and seems to work well.
"1, 3, 4, 7, 13", "1, 2, 4, 13, 15" main <<< FindIntersection1 ==>1,4,13<== "2, 4, 6, 8, 10", "1, 3, 5, 7, 11" main <<< FindIntersection1 ==>false<== "-5, -3, -1, 1, 3, 5", "-1" main <<< FindIntersection1 ==>-1<== "0, 2, 4", "1, 2, 3, 4, 5, 6" main <<< FindIntersection1 ==>2,4<== "1, 3, 9, 10, 17, 18", "1, 4, 9, 10" main <<< FindIntersection1 ==>1,9,10<==
The screen shot holds five test cases. The idea is to determine which numbers are in both strings and output them in a new string. If there are no numbers in common one should return a string with the following word: “false”.
The article that I read implemented a O(n*m) algorithm. Basically for each value in the first string, traverse the second string looking for the same value. The idea is to come up with a more efficient approach.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the string ****
String str = sc.nextLine();
// ???? display the string ????
System.out.println("main <<< str ==>" + str + "<==");
// **** split the string ****
String[] strArr = str.split("\", \"");
// **** clean the substrings ****
strArr[0] = strArr[0].substring(1);
strArr[1] = strArr[1].substring(0, strArr[1].length() - 1);
// ???? display strings ????
System.out.println("main <<< strArr[0] ==>" + strArr[0] + "<==");
System.out.println("main <<< strArr[1] ==>" + strArr[1] + "<==");
// **** close scanner ****
sc.close();
// **** find intersection ****
System.out.println("main <<< FindIntersection ==>" + FindIntersection(strArr) + "<==");
}
I tried different ways of reading the two strings. This was not part of the challenge but I did spend the time. In my first approach I had the numbers for each string on two separate lines so I would not have to deal with the double quotes and comma separating the two strings.
I then switched to having all the data read at once and then splitting and parsing the strings.
The challenge required both strings being presented as a two dimensional string array. Once that was accomplished, I called the FindIntersection function.
/*
* Return a string of numbers that occur in both strings in sorted order.
* If there is no intersection, return the string "false".
*/
static String FindIntersection(String[] strArr) {
// **** ****
StringBuilder sb = new StringBuilder();
// **** for ease of use****
String str1 = strArr[0];
String str2 = strArr[1];
// **** split first string ****
String[] arr1 = str1.split(", ");
// **** split second string ****
String[] arr2 = str2.split(", ");
// **** loop finding matches ****
int i = 0;
int j = 0;
while (true) {
// **** check if we are done ****
if ((i >= arr1.length) || (j >= arr2.length))
break;
// **** get the integer values from the proper arrays ****
int val1 = Integer.parseInt(arr1[i]);
int val2 = Integer.parseInt(arr2[j]);
// **** val1 == val2 ****
if (val1 == val2) {
if (sb.length() != 0)
sb.append("," + String.valueOf(arr1[i]));
else
sb.append(String.valueOf(arr1[i]));
i++;
j++;
}
// **** val1 < val2 ****
else if (val1 < val2) { i++; } // **** val1 > val2 ****
else {
j++;
}
}
// **** check if there is no intersection ****
if (sb.length() == 0)
sb.append("false");
// **** ****
return sb.toString();
}
To make it more efficient I used a string builder for the returning string.
For ease of use I set a couple variables to represent the strings. Not sure that was worth it but I like code that is easy to follow, debug and enhance as needed.
Both strings are then split in order to get the individual string values in two separate arrays.
Index i is used in the first string, while index j is used for the second string. We then enter a loop that generates the string with the intersections.
We need to specify a condition when we exit the loop. If we reach the end of either string, there are no more values that intersect so we break out of the loop.
We then convert the values of interest from string to integer. That simplifies the comparisons. I could have compares strings of integers with the complication of having negative values. A simple conversion seemed to be simpler and easier to understand.
There are three possibilities for the current values. If they match, this is an intersection. We append the value to the string builder and increment both indices.
If val1 is less than val2 we increment index i because both strings are in monotonically ascending order and we are interested in finding the same value on both arrays.
If val1 is greater than val2 we increment index j the reason is the same as for val1 < val2.
After we exit the loop we need to check if the string builder is empty. In such case we did not have an intersection and we need to return the string “false”.
When done we return the sting representation of our string builder.
The entire code for this project can be found in my GitHub repository.
For the next two posts will attempt the first MEDIUM and HARD problems from coderbyte.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a message using the following address: john.canessa@gmail.com. All messages will remain private.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
John
Follow me on Twitter: @john_canessa