It is Sunday March 15, 2020 and it is a sunny day in the Twin Cities of Minneapolis and St. Paul. The current temperature is about 22 F. It has gone up a few degrees since I woke up today. The high is expected to be in the low 40’s. It seems like it is going to be a nice warm winter day.
It has been a crazy week. The count of confirmed COVID-19 cases in MN according to the StarTribune up to last Friday was 9. That said; my wife and I decided to get some supplies (e.g., two packages of toilet paper at Costco) and remain at home (with a few exceptions) until the pandemic is under control. I will write a set of posts regarding COVID-19 in a separate category.
I did watch the short YouTube video “Do Something Difficult Every Day | AMA #1 – Ask Me Anything with Lex Fridman”.
I believe and have been promoting for decades that “stress is the salt of life”.
Stress helps us to learn how to behave when we encounter more difficult situations in our personal and work lives.
In the video, Lex Fridman mentions that “suffering is good for the soul”. Occasionally he takes a 1 minute cold shower. My father, as long as I can remember, would take cold showers every single day. He told me that some degree of pain at the start of the day would help you cope with the day ahead.
When I was younger, for reasons I will not cover at this time, I took cold showers, multiple times a day, for a period of seven years. During that time I would get up at 05:00 and would run and exercise for a couple hours. I was in a crew rowing team. I loved it. Today I shower with nice warm water. Perhaps I am getting soft :o)
Lex Fridman runs quite often because it is good for him. When he starts he initially experiences discomfort and struggles. He also mentions that you need to train yourself to struggle in order to be prepared to handle it when life demands it. Habits are necessary. Do things every day as opposed to a lot of something once a month.
I believe Lex Fridman is an interesting person and has good things to say. My suggestion is for you to watch a couple videos and make your own decision. BTW I have subscribed and get notified when he posts new videos on YouTube.
Now let’s get to the topic of this post. Earlier this week I randomly selected the HackerRank challenge “Sherlock and the Valid String”. If you are interested read the requirements, think about it, come up with a strategy, write some code and come up with a solution.
I decided to write my solution in Java using the Visual Studio Code IDE by Microsoft. That said; I was working with Azure on the Windows machine I do most of my work including the code for this blog. Today I am not sure what happened last Tuesday. VS Code no longer works. It crashes my machine when I run Java code. My Visual Studio Enterprise editions 2013, 2017 and 2019 seem to work well with C/C++. I have not tested them with Java. Have re installed Java and VS Code multiple times. It just continues to crash my Windows 10 64-bit machine. If you have any suggestions please let me know. I have a few more things to try but I am cautious since I do not to have to reformat the drives and reinstall the Windows OS and all the different applications and tools.
The Java code for this post was written in a different Windows 10 machine using VS Code.
The requirements for the problem follow:
“Sherlock considers a string to be valid if all characters of the string appear the same number of times. It is also valid if he can remove just one character at one index in the string, and the remaining characters will occur the same number of times.”
Make sure you read the requirements carefully and understand them. I tried a couple approaches which passed most test cases. I then decided to just solve the problem with test cases. I did not purchase test cases using hackos.
On one approach I decided to use Average and in another Median. Shortly they got somewhat confusing and decided to abandon them. I did leave the short method I wrote to compute the median. It is not used in the final solution.
1 acb YES 1 abb YES 1 abcc YES 1 abbbc NO 1 aaabbbxxxxxyyyzzz NO 3 abc abcc abccc YES YES NO 3 aabbcd aabbccddeefghi abcdefghhgfedecba NO NO YES 3 aaaabbbccc abbbb aaabcccddd YES YES YES 1 abbbb YES 1 aaacccdddjjjz YES 4 aaaaaaaaaabbbbbbbbbbccccccccccdddddddddd aaaaaaaaaabbbbbbbbbbccccccccccddddddddddd aaaaaaaaaabbbbbbbbbbccccccccccdddddddddddd aaaaaaaaaabbbbbbbbbbccccccccccddddddddddddd YES YES NO NO 2 aaaabbbbccddddeeeeffffgggg aaaabbbbccccccddddeeeeffffgggg NO NO
The idea is to return “YES” or “NO” if a string is valid or not according to the requirements. I could have put all test cases into one long one but I left them in the order I used them.
// **** open scanner ****
static Scanner sc = new Scanner(System.in);
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** read the number of strings to process ****
int n = Integer.parseInt(sc.nextLine().trim());
// **** loop reading strings ****
for (int i = 0; i < n; i++) {
// **** read the next string ****
String s = sc.nextLine().trim();
// **** process string and display result ****
System.out.println(isValid(s));
}
// **** close scanner ****
sc.close();
}
The test scaffolding reflects the one provided by HackerRank, but it is slightly simpler and shorted. Keep in mind that you will use the one from HackerRank when you submit your code.
The idea is to read the number of strings and then read a string, determine if it is valid or not and display the result. We use a loop to read a string, process it and display the result.
/**
* Generate a sorted array of frequencies (no zero entries)
*/
static int[] stringCharFreq(String s) {
// **** ****
HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
// **** get frequencies of characters ****
for (char ch : s.toCharArray())
hm.put(ch, hm.getOrDefault(ch, 0) + 1);
// **** create empty array of non-zero frequencies ****
int[] freq = new int[hm.size()];
// **** populate the array of frequencies ****
Iterator<Entry<Character, Integer>> it = hm.entrySet().iterator();
int i = 0;
while (it.hasNext()) {
Entry<Character, Integer> e = it.next();
freq[i++] = e.getValue();
}
// **** sort the frequency array ****
Arrays.sort(freq);
// **** return sorted frequency array ****
return freq;
}
The stringCharFreq() method is used to generate an array of sorted frequencies not including zeros, in ascending order for all the characters in the specified string. Hopefully with that done, we can use such information to test some conditions in order to satisfy the requirements of the problem at hand.
We start with a hash map and associate with each character it’s frequency. We could have used a character array, which I did in a previous pass, but ended with this code.
/**
* Compute median of specified array of integers.
* !!! NOT USED IN THE SOLUTION !!!
*/
static double computeMedian(int[] f) {
// **** sort the frequency array ****
Arrays.sort(f);
// **** compute median ****
if (f.length % 2 == 0)
return (f[f.length / 2 - 1] + f[f.length / 2]) / 2.0;
else
return f[f.length / 2];
}
As I mentioned I generated the computeMedian() when I was trying a different approach. I could have deleted it from the code but decided to just label it and leave it for possible future use.
/**
* Complete the isValid function below.
* Using single array.
*/
static String isValid(String s) {
// **** sanity check ****
if (s != null && s.length() <= 1)
return "YES";
// **** generate a sorted frequency array ****
int[] freq = stringCharFreq(s);
// **** for ease of use ****
int min = freq[0];
int postMin = freq[1];
int max = freq[freq.length - 1];
int prevMax = freq[freq.length - 2];
// **** check min == max ****
if (min == max)
return "YES";
// **** first frequency is 1 and the rest are equal ****
if (min == 1 && postMin == max)
return "YES";
// **** all frequencies the same except last ****
if (min == postMin && min == prevMax && max == prevMax + 1)
return "YES";
// **** this is not a valid string ****
return "NO";
}
The isValid() method implements the core of the solution.
We start with a simple check. Then we generate an array of integers with the frequencies of the characters that are not zero. The array is sorted in ascending order.
For ease of use I assign the min, postMin, max and preMax values. We could have used the array directly but I believe in making the code as readable as possible for maintenance reasons. Of course, little if any maintenance will be required to this code but as we read earlier, good habits are important.
We then check three conditions using the frequency array. The three conditions are needed to pass all 20+ tests required by HackerRank for this problem.
Now we are ready to push our solution back to GitHub.
# **** directory of workspace0 on a different WIndows 10 computer ****
C:\Users\johnc\workspace0>dir
03/12/2020 10:42 AM <DIR> .
03/12/2020 10:42 AM <DIR> ..
03/12/2020 10:43 AM <DIR> SherlockValidString
03/10/2020 04:24 PM <DIR> SortOnFrequency
# **** let's take a look at the contents ****
C:\Users\johnc\workspace0>cd SherlockValidString
# **** display contents ****
C:\Users\johnc\workspace0\SherlockValidString>dir
03/12/2020 10:43 AM <DIR> .
03/12/2020 10:43 AM <DIR> ..
03/12/2020 10:42 AM 211 README.md
03/15/2020 08:34 AM 3,216 Solution.java
# **** check status ****
C:\Users\johnc\workspace0\SherlockValidString>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)
# **** add the solution to the next commit ****
C:\Users\johnc\workspace0\SherlockValidString>git add Solution.java
# **** check status ****
C:\Users\johnc\workspace0\SherlockValidString>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
# **** commit the solution ... whoops!!! ****
C:\Users\johnc\workspace0\SherlockValidString>git commit -m "completed solution"
*** Please tell me who you are.
Run
git config --global user.email "you@example.com"
git config --global user.name "Your Name"
to set your account's default identity.
Omit --global to set the identity only in this repository.
fatal: unable to auto-detect email address (got 'johnc@AzureKinect.(none)')
# **** specify my email for GitHub ****
C:\Users\johnc\workspace0\SherlockValidString>git config --global user.email "john.canessa@gmail.com"
# **** specify my user name for GitHub ****
C:\Users\johnc\workspace0\SherlockValidString>git config --global user.name "JohnCanessa"
# **** let's try the commit and see what happens ... all went well!!!****
C:\Users\johnc\workspace0\SherlockValidString>git commit -m "completed solution"
[master b7474e0] completed solution
1 file changed, 121 insertions(+)
create mode 100644 Solution.java
# **** check status ****
C:\Users\johnc\workspace0\SherlockValidString>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
# **** push the commit to GitHub ****
C:\Users\johnc\workspace0\SherlockValidString>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.30 KiB | 1.30 MiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/SherlockValidString.git
7647230..b7474e0 master -> master
# **** check the log ****
C:\Users\johnc\workspace0\SherlockValidString>git log
commit b7474e0a22c958f345d8ecf064b3402913a3e271 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Sun Mar 15 08:38:54 2020 -0500
completed solution
commit 7647230168676f2b4a4755e0174ff6bb5213676a
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Tue Mar 10 10:17:38 2020 -0500
Create README.md
As I am writing this post, I noticed that I do not have a screen capture illustrating cloning the project using git. Sorry about that. I will make sure I capture the steps for the next post. If you want to see similar steps, you can refer to recent post i.e., “Sherlock and Anagrams” in this blog.
If you follow this blog, the workspace on this machine is relatively new compared to the other Windows 10 development computer.
All seems to be fine until I attempt to commit the code. It fails. The reason is that this is a relatively new computer and I have not used GitHub from it yet.
I specify my email and user name. GitHub displays a window which I did not capture in which I had to enter my GitHub password. Once done, I was able to commit the code for this post. The commit was then pushed to GitHub. We check the log. As you can see I have been busy with work, the issue with VSCode crashing and supplies to be able to lock down at home for the next few weeks. The repo was created last Tuesday and today Sunday the solution was posted.
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 477 subscribers to my blog!!! Keep safe during the next few weeks.
John
Twitter: @john_canessa