As 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.
On Friday the process repeated. On Sunday I figured out to give 
the Windows update one last chance hopping that the software would automatically determined it had failed, would clean the downloaded files and try the entire process again. Seems like the update mechanism kept trying the same failed update somehow hoping for it to work. I believe someone quite brilliant said: “Insanity: doing the same thing over and over again and expecting different results” (Albert Einstein Quote). Hopefully Microsoft will include such mechanism in a future update of their Windows Update software :o)
Goggled how to remove the pending update and rebooted my machine. When done, the 3 hour class had already started. I will have to watch part of the recorded class this week. After that all seems well. Will find out what happens with Windows updates today ;o)
As I have been doing for the past few months, I have been visiting HackerRank almost every day. The last challenge I approached was labeled “No Prefix Set”. For starts it seemed like it could be solved with similar code as the challenge labeled “Contacts”. In software engineering one needs to look for the best possible specification for requirements. I believe that on purpose most challenges fail to provide well defined requirements to make them look harder. This one was no exception. To tell you the truth, it makes it more satisfying to watch all 42 tests pass :o)
This challenge provided a set on N strings no longer than 60 characters using lower-case ASCII characters in the range [a : j]. One had to determine if a given set was a “GOOD SET” or a “BAD SET” if it contained one string that was a prefix for any other string. Please check the actual requirements by visiting: https://www.hackerrank.com/challenges/no-prefix-set. Perhaps you will feel inclined to start solving some challenges.
After some experimenting and reading the associated discussions, It was clear that the problem had two different cases: The first when the duplicate prefix came BEFORE and the second when the duplicate prefix came AFTER. To make it clear, the following sequence shows the BEFORE condition:
2
abc
abcd
The output of the program should be:
BAD SET
abcd
The reason is obvious; the first string “abc” is a prefix of the second string “abcd”. That was easy to determine. It did not take me more than a few minutes. The second case was something that was not that clear in the requirement (or was it). Let’s try the following sequence:
2
abcd
abc
In this case the first string “abcd” is stored in the trie and obviously there is no issue (because there is only one string so far). When the second sting “abc” is read, it becomes a prefix for the first one. Once this requirement becomes clear, the program can be updated in a couple minutes to pass the challenge.
The actual runs of my solution follow:
2
abcd
abc
BAD SET
abc
2
abc
abcd
BAD SET
abcd
The code for my solution in Java follows:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class TrieNode {
char letter;
TrieNode[] links;
boolean fullWord;
int count;
TrieNode(char letter) {
this.letter = letter;
this.links = new TrieNode[10];
this.fullWord = false;
this.count = 0;
}
}
public class Solution {
static TrieNode createTree() {
return(new TrieNode(‘\0’));
}
static boolean insertWord(TrieNode root, String word) {
int offset = 97;
int len = word.length();
char[] letters = word.toCharArray();
TrieNode curNode = root;
int i = 0;
// **** traverse the word ****
for (i = 0; i < len; i++) {
if (curNode.links[letters[i] – offset] == null) {
curNode.links[letters[i] – offset] = new TrieNode(letters[i]);
}
// **** ****
if (curNode.fullWord) {
System.out.println(“BAD SET”);
System.out.println(word);
return true;
}
// **** ****
curNode.count++;
curNode = curNode.links[letters[i] – offset];
}
// **** flag this is an end word ****
curNode.fullWord = true;
curNode.count++;
// **** check if previous word has the same prefix ****
if (curNode.count > 1) {
System.out.println(“BAD SET”);
System.out.println(word);
return true;
} else {
return false;
}
}
public static void main(String[] args) {
int N = 0;
String name = “”;
boolean duplicate = false;
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
try {
N = Integer.parseInt(in.readLine());
} catch (NumberFormatException | IOException e) {
e.printStackTrace();
}
TrieNode root = createTree();
for (int n = 0; (n < N) && !duplicate; n++) {
try {
name = in.readLine().trim();
} catch (IOException e) {
e.printStackTrace();
}
duplicate = insertWord(root, name);
}
if (!duplicate) {
System.out.println(“GOOD SET”);
}
}
}
That was fun. If you have comments or questions please let me know by sending me an email message.
John
John.canessa@gmail.com