No Prefix Set

weekend_on_line_classAs 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 windows_update_failurethe 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)

einstein_insanityGoggled 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.hacher_rank_tests

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

Leave a Reply

Your email address will not be published. Required fields are marked *