It is a rather cold spring day in the Twin Cities of Minneapolis and St. Paul. I believe there is a winter storm warning for today all day. This morning when I got up, there was a thin coating of snow on roofs and lawns. The roads seem to just be wet. One way or the other my wife and I are not planning on going out. We are under lockdown due to the Wuhan virus (also known as COVID-19) pandemic.
Besides work I have been taking a few courses, reading technical documents, reading non-technical stuff and watching the news. As of today April 12, 2020 in Dakota County, MN (I live in the city of Apple Valley which is in Dakota County) the total number of deaths attributed to the pandemic in
Dakota County is 4 which represents 0.001% of the population. The previous count of 3 held for several weeks. In the USA the total number of deaths is 20,411 which represent 0.006% of the population of about 330 million. Seems like in this area we are doing well. No matter which city or country you live in, please keep social distancing and do not leave home unless it is needed. In order to beat the pandemic we all need to follow social distancing until a vaccine is available or until the CDC (do not trust unofficial sources) informs us that it is safe for people that have antibodies for them to resume normal activities.
I have been watching national and world news. Political struggles continue to develop all over the world. In addition we have China which continues to pretend that they did all what was needed to prevent the pandemic and that magically they have been able to control it in their own country. China continues to sell vaccines, tests and masks mostly to countries that are not able to produce them. In general all their products do not work or are substandard. It seems that in Europe, Asia and North America, governments and companies are starting to realize that it is time to drop manufacturing in China and move it back to their own countries. Leaving China is a must. It is also a must for all countries to be able to completely manufacture the products they produce in their own countries. They should always outsource a percentage (for cost reasons) to be manufactured abroad in multiple 
countries, keeping the factories in their own countries producing a large percentage of the total production. For example, Ford produces cars, so 55% of all models should be produced in the USA. Of the remaining 45% factories in at least 3 different countries (completely excluding China) should produce about 15% each. If something goes wrong and some or all the foreign plants stop producing vehicles, the plants in the USA would just have to up their production. They do not need to acquire new machinery or get employees trained. They know how to design and produce cars in their entirety. In addition there will only be tariffs for the 45% of cars that would be imported from different countries.
Chinese people are not the issue. The government of China is. They have and will continue to enslave their people. China has been buying off people is world organizations and slaving their own to benefit a very few number of 
people in their communist party. They pose a threat to democracy. People (by not buying products made in China), companies (by not manufacturing products in China) and governments (by not buying or using services and products made in China) will prevent the world domination aspirations by the communist party.
My wife called me to go up for an early lunch. She reheated leftovers from yesterday. At 12:00 PM CDT Andrea Bocelli had a half hour concert from the Duomo in Milan, Italy. The concert was live in YouTube. The Duomo was empty with the exception of the organ player and Bocelli. We thought the concert was too short but great. Hopefully things will go back to normal sooner than later and we will be able to go back and enjoy Italy.
OK, enough of the pandemic and China. Let’s get to the main topic for this post.
Earlier this week I received a notification from YouTube that Nick White had a new post on his channel. I subscribe to several YouTube channels. The video Google Coding Interview Question – composeRanges discusses a problem asked by Google during a technical interview.
Let’s take a look at the requirements.
“Given a sorted integer array that does not contain any duplicates, return a summary of the number ranges it contains.”
An example would be:
nums = [-1, 0, 1, 2, 6, 7, 9]
output:
composeRanges(nums) = [“-1->2”, “6->7”, “9”]
We note that the sample array is sorted in ascending order. The array contains integers and there are no duplicates. The results are encapsulated by 3 strings. We have a range [-1, 0, 1, 2], followed by another [6, 7] ending with [9]. The sample answer seems to meet requirements. Now let’s see if we can generate a solution using the Java programming language. I will use the Visual Studio Code IDE. Of course you can use a different IDE or even a different programming language.
# **** Windows 10 console **** Microsoft Windows [Version 10.0.18363.720] (c) 2019 Microsoft Corporation. All rights reserved. # **** **** C:\Users\johnc>dir 04/08/2020 07:59 AM <DIR> . 04/08/2020 07:59 AM <DIR> .. 09/22/2019 08:00 AM <DIR> .eclipse 03/15/2020 08:38 AM 59 .gitconfig 04/07/2020 10:38 AM <DIR> .p2 09/22/2019 08:00 AM <DIR> .tooling 03/10/2020 03:53 PM <DIR> .vscode 03/10/2020 04:43 PM <DIR> 3D Objects 03/10/2020 04:43 PM <DIR> Contacts 04/08/2020 07:59 AM <DIR> ContainsCloseNums 02/17/2020 03:52 PM <DIR> Documents 04/03/2020 03:20 PM <DIR> Downloads 09/22/2019 07:57 AM <DIR> eclipse 09/22/2019 07:59 AM <DIR> eclipse-workspace_0 03/10/2020 04:43 PM <DIR> Favorites 03/10/2020 04:44 PM <DIR> Links 03/10/2020 04:43 PM <DIR> Music 09/12/2019 04:36 PM <DIR> NCH Software Suite 04/10/2020 06:59 AM <DIR> OneDrive 03/10/2020 04:43 PM <DIR> Saved Games 03/10/2020 04:43 PM <DIR> Searches 03/10/2020 04:43 PM <DIR> Videos 04/08/2020 08:00 AM <DIR> workspace0 # **** **** C:\Users\johnc>cd workspace0 # **** **** C:\Users\johnc\workspace0>dir 04/01/2020 08:57 AM <DIR> BST-Search 04/08/2020 08:04 AM <DIR> ContainsCloseNums 04/05/2020 08:32 AM <DIR> GraphBFS 03/29/2020 08:30 AM <DIR> ORCost 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** clone repositorfy from GitHub **** C:\Users\johnc\workspace0>git clone https://github.com/JohnCanessa/ComposeRanges.git Cloning into 'ComposeRanges'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), 726 bytes | 8.00 KiB/s, done. # **** **** C:\Users\johnc\workspace0>dir 04/10/2020 11:29 AM <DIR> . 04/10/2020 11:29 AM <DIR> .. 04/01/2020 08:57 AM <DIR> BST-Search 04/10/2020 11:29 AM <DIR> ComposeRanges 04/08/2020 08:04 AM <DIR> ContainsCloseNums 04/05/2020 08:32 AM <DIR> GraphBFS 03/29/2020 08:30 AM <DIR> ORCost 03/10/2020 04:24 PM <DIR> SortOnFrequency # **** **** C:\Users\johnc\workspace0>cd ComposeRanges # **** **** C:\Users\johnc\workspace0\ComposeRanges>dir 04/10/2020 11:29 AM <DIR> . 04/10/2020 11:29 AM <DIR> .. 04/10/2020 11:29 AM 191 README.md # **** **** C:\Users\johnc\workspace0\ComposeRanges>type README.md # ComposeRanges Simple Google interview question solved usingJava To read more about it and follow how the code was developed you may use the follwoing link: T.B.D. Enjoy! John C:\Users\johnc\workspace0\ComposeRanges>
I always like to start by creating a repository in GitHub. The initial repository contains a README.md file. As you can see I left a T.B.D. to be replaced by a link to this post after the post is completed using WordPress.
-17 [-17] [-17] -1 0 1 2 6 7 [-1->2, 6->7] [-1->2, 6->7] -1 0 1 2 6 7 9 [-1->2, 6->7, 9] [-1->2, 6->7, 9] 1 3 4 6 7 8 10 [1, 3->4, 6->8, 10] [1, 3->4, 6->8, 10] 1 3 4 6 8 9 11 [1, 3->4, 6, 8->9, 11] [1, 3->4, 6, 8->9, 11] 1 3 4 6 8 9 11 13 14 15 [1, 3->4, 6, 8->9, 11, 13->15] [1, 3->4, 6, 8->9, 11, 13->15] 1 3 4 6 8 9 11 13 14 15 17 [1, 3->4, 6, 8->9, 11, 13->15, 17] [1, 3->4, 6, 8->9, 11, 13->15, 17] -5 3 4 5 20 21 22 [-5, 3->5, 20->22] [-5, 3->5, 20->22] 1 2 3 5 6 9 [1->3, 5->6, 9] [1->3, 5->6, 9] -15 -5 5 10 [-15, -5, 5, 10] [-15, -5, 5, 10]
As you can see I used several test cases. Some of them were mentioned during the YouTube video while others I created while developing the solution.
I have two implementations of the solution. They both seem to produce the same results. I have not used the web site hosting the problem mentioned in the video. If you get an account you should be able to test your solution against multiple and different test cases.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the line with integers ****
String[] s = sc.nextLine().trim().split(" ");
// **** declare array of integers ****
int[] nums = new int[s.length];
// **** populate array of integers ****
for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.parseInt(s[i]);
}
// **** close scanner ****
sc.close();
// **** array of ranges ****
String[] ranges = null;
// **** compose ranges ****
ranges = composeRanges1(nums);
// **** display array of ranges ****
System.out.println(Arrays.toString(ranges));
// **** compose ranges ****
ranges = composeRanges2(nums);
// **** display array of ranges ****
System.out.println(Arrays.toString(ranges));
}
We just read a line of integers and split them into strings. The strings are parsed and the results are used to populate the array of integers to be fed two the two implementations. The results are then displayed on the console of the VSCode IDE.
/**
* Generate an array of Strings with ranges - O(n).
*/
static String[] composeRanges1(int[] nums) {
// **** check condition and return if needed ****
if (nums == null || nums.length == 0)
return null;
// **** array list of strings with ranges ****
List<String> ranges = new ArrayList<String>();
// **** check for single value ****
if (nums.length == 1) {
ranges.add(String.valueOf(nums[0]));
return ranges.toArray(new String[ranges.size()]);
}
// **** traverse the array of integers - O(n) ****
int i = 0;
int j = 1;
for (j = 1; j < nums.length; j++) {
// **** check if this number is in sequence ****
if (nums[j - 1] + 1 == nums[j])
continue;
// **** add single value or range ****
singleValueOrRange(nums, i, j, ranges);
// *** reset indices ****
i = j;
j = i;
}
// **** add single value or range (in case something was left behind) ****
singleValueOrRange(nums, i, j, ranges);
// **** convert to string array and return ****
return ranges.toArray(new String[ranges.size()]);
}
In this approach we first check some conditions which can be easily dealt with. This leaves us with an array of at least one integer to deal with.
We will use an array list of strings to hold the ranges.
We are ready to traverse the array of integers looking for consecutive numbers. When we deviate from the current range we add the range to the list and continue processing the integer array. Note that the method traverses the array just once in O(n).
After the main loop is completed we check that we do not miss a range that needs to be added to the list of ranges.
/**
* Auxiliary method.
* Populate the array list with a single value or a range - O(1).
*/
static void singleValueOrRange(int[] nums, int i, int j, List<String> ranges) {
// **** range generated by this method (could be a single number) ****
String range = null;
// **** check if this is a range of numbers ****
if (i + 2 <= j) { range = nums[i] + "->" + nums[j - 1];
}
// **** add an single value ****
else {
range = String.valueOf(nums[i]);
}
// **** add range to array ****
ranges.add(range);
}
The singleValueOrRange auxiliary method is used to add a single value or a range of values to the list of ranges. In practice we could have left this code in line but since we used it twice I felt compelled moving it to its own method.
/**
* Generate an array of Strings with the ranges - O(n).
*/
static String[] composeRanges2(int[] nums) {
// **** check condition and return if needed ****
if (nums == null || nums.length == 0)
return null;
// **** array of ranges ****
ArrayList<String> ranges = new ArrayList<String>();
// **** initialize start and end array index ****
int start = 0;
int end = start + 1;
// **** traverse the array of integers - O(n) ****
while (start < nums.length) {
// **** check if numbers are in the current range ****
while ((end < nums.length) && (nums[end - 1] + 1 == nums[end])) { end++; } // **** add the current range to the array list **** if (start == end - 1) { ranges.add("" + nums[start]); } else { ranges.add(nums[start] + "->" + nums[end - 1]);
}
// **** update indices into nums array ****
start = end;
end = start + 1;
}
// **** convert to string array and return ****
return ranges.toArray(new String[ranges.size()]);
}
This method implements the second solution. We run a check and put the ranges in an array list. Traversing through the array is implemented using the start and end indices. The solution is pretty much the same.
When I was done with my code I watched the rest of the video. Nick’s approach is similar, yet somewhat different. I recommend always watching other approaches because you always learn something even if it is the satisfaction that perhaps your code is more simple or elegant and easier to maintain that others.
# **** ****
C:\Users\johnc>dir
04/08/2020 07:59 AM <DIR> .
04/08/2020 07:59 AM <DIR> ..
09/22/2019 08:00 AM <DIR> .eclipse
03/15/2020 08:38 AM 59 .gitconfig
04/07/2020 10:38 AM <DIR> .p2
09/22/2019 08:00 AM <DIR> .tooling
03/10/2020 03:53 PM <DIR> .vscode
03/10/2020 04:43 PM <DIR> 3D Objects
03/10/2020 04:43 PM <DIR> Contacts
04/08/2020 07:59 AM <DIR> ContainsCloseNums
02/17/2020 03:52 PM <DIR> Documents
04/03/2020 03:20 PM <DIR> Downloads
09/22/2019 07:57 AM <DIR> eclipse
09/22/2019 07:59 AM <DIR> eclipse-workspace_0
03/10/2020 04:43 PM <DIR> Favorites
03/10/2020 04:44 PM <DIR> Links
03/10/2020 04:43 PM <DIR> Music
09/12/2019 04:36 PM <DIR> NCH Software Suite
04/12/2020 07:40 AM <DIR> OneDrive
03/10/2020 04:43 PM <DIR> Saved Games
03/10/2020 04:43 PM <DIR> Searches
03/10/2020 04:43 PM <DIR> Videos
04/10/2020 11:29 AM <DIR> workspace0
# **** ****
C:\Users\johnc>cd workspace0
# **** ****
C:\Users\johnc\workspace0>dir
04/10/2020 11:29 AM <DIR> .
04/10/2020 11:29 AM <DIR> ..
04/01/2020 08:57 AM <DIR> BST-Search
04/10/2020 11:34 AM <DIR> ComposeRanges
04/08/2020 08:04 AM <DIR> ContainsCloseNums
04/05/2020 08:32 AM <DIR> GraphBFS
03/29/2020 08:30 AM <DIR> ORCost
03/10/2020 04:24 PM <DIR> SortOnFrequency
# **** ****
C:\Users\johnc\workspace0>cd ComposeRanges
# **** check we are using the proper GitHub repo ****
C:\Users\johnc\workspace0\ComposeRanges>git remote -v
origin https://github.com/JohnCanessa/ComposeRanges.git (fetch)
origin https://github.com/JohnCanessa/ComposeRanges.git (push)
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git status
On branch master
Your branch is up to date with 'origin/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
Solution.java
nothing added to commit but untracked files present (use "git add" to track)
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git add Solution.java
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git restore --staged <file>..." to unstage)
new file: Solution.java
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git commit -m "solution with two possible approaches"
[master bfe9bb3] solution with two possible approaches
1 file changed, 157 insertions(+)
create mode 100644 Solution.java
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 12 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 1.40 KiB | 1.40 MiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/ComposeRanges.git
8a9c6cb..bfe9bb3 master -> master
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git status
On branch master
Your branch is up to date with 'origin/master'.
nothing to commit, working tree clean
# **** ****
C:\Users\johnc\workspace0\ComposeRanges>git log
commit bfe9bb3d49baea5ea34ad4ada0385afe9752ad5a (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Sun Apr 12 09:12:39 2020 -0500
solution with two possible approaches
commit 8a9c6cb3983a67169bf91a024dd4d46da04e6b09
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Fri Apr 10 11:28:54 2020 -0500
Create README.md
The entire code for this project can be found in my GitHub repository.
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 private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, thanks to all 583 subscribers to my blog!!!
John
Twitter: @john_canessa