This was my Hackerrank coding challenge for an Interview for a New Grad Software Engineer position:
Before and After Puzzle
Given a list of phrases, generate a list of Wheel of Fortune "Before and After" puzzles. "Before and After" puzzles are where one phrase ends with the last word of the first one of another. As a basic example, given two phrases, "writing code" and "code rocks" the output will be "writing code rocks". Here is a more comprehensive example of inputs and expected output.
input = [ "mission statement", "a quick bite to eat", "a chip off the old block", "chocolate bar", "mission impossible", "a man on a mission", "block party", "eat my words", "bar of soap" ]
output = [ "a quick bite to eat my words", "a chip off the old block party", "chocolate bar of soap", "a man on a mission statement", "a man on a mission impossible" ]
Constraints: - Returned results do not have to be unique - Don't worry about casing. Assume inputs are only a - z lowercase letters with spaces (so no special characters or dealing with case matching words) - Assume all whitespace is just single spaces (No need to worry about white spacing edge cases)
I solved the problem by completing 6/7 test-cases where the last test-case terminated due to timeout.
// 1. Submitted code during the interview (cleared 6/7 test-cases)
/*
My approach: Compare every phrase in the list to every other phrase in the list.
If the last word of the phrase matches the first word of another phrase, do the
following:
1) Remove the first word from the other phrase.
2) Combine both phrases
3) Add the combined phrase to the output list.
*/
private static List<String> generate_phrases(List<String> phrases) {
List<String> output = new ArrayList<>();
for(String temp: phrases) {
String[] content = temp.split(" ");
for(String temp2: phrases) {
String[] content2 = temp2.split(" ");
if(content[content.length-1].equals(content2[0])) {
String tempWord = content2[0];
temp2 = temp2.replaceAll(tempWord, "");
output.add(temp+temp2);
}
}
}
return output;
}
// 2. Improved code after the interview
/*
My approach: Compare every phrase in the list to every other phrase in the list.
If the last word of the phrase matches the first word of another phrase, do the
following:
1) Push both phrases to a set.
2) Remove the first word from the other phrase.
3) Combine both phrases
4) Add the combined phrase to the output list.
5) for all phrases added in the set, decrease the size of the input list by removing the visited phrases
*/
private static List<String> generate_phrases(List<String> phrases) {
List<String> output = new ArrayList<>(); boolean flag = false;
int length = phrases.size();
for(int i=0; i<length; i++) {
Set<String> wordsToRemove = new HashSet<>();
String temp = phrases.get(i);
String[] contents1 = temp.split(" ");
for(int j=0; j<length; j++) {
String temp2 = phrases.get(j);
String[] contents2 = temp2.split(" ");
if(contents1[contents1.length-1].equals(contents2[0])) {
flag = true;
wordsToRemove.add(temp); wordsToRemove.add(temp2);
String tempWord = contents2[0];
temp2 = temp2.replaceAll(tempWord, "");
output.add(temp+temp2);
}
}
if(flag) {
for (String s : wordsToRemove){ phrases.remove(s); length--; }
flag = false; i=0;
}
}
return output;
}
I submitted my first piece of code which failed the last test case and got terminated due to timeout. This was the best I was able to do during the interview. Later spending some time after the interview, I came up with an efficient solution that took fewer iterations than the previous one. But All of my solutions use 2 for loops. Can someone help me with a better and efficient code?
By following the approach from the comments at my post, I came up with a solution. But still can't figure out if it will be more efficient. What will be the time complexity of my code now?
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("mission statement");
list.add("a quick bite to eat");
list.add("a chip off the old block");
list.add("chocolate bar");
list.add("mission impossible");
list.add("a man on a mission");
list.add("block party");
list.add("eat my words");
list.add("bar of soap");
System.out.println(generate_phrases(list));
}
private static List<String> generate_phrases(List<String> phrases) {
List<Phrase> phraseList = generatePhraseList(phrases);
Map<String, List<Phrase>> map = generateHashMapOfUniqueKeys(phraseList);
return generateOutputList(map);
}
private static List<Phrase> generatePhraseList(List<String> phrases) {
List<Phrase> phraseList = new ArrayList<>();
for (String p: phrases) {
Phrase temp = new Phrase(p);
phraseList.add(temp);
}
return phraseList;
}
private static Map<String, List<Phrase>> generateHashMapOfUniqueKeys(List<Phrase> phraseList) {
Map<String, List<Phrase>> map = new HashMap<>();
for(Phrase p : phraseList) {
String start = p.getStart();
if(!map.containsKey(start)) {
List<Phrase> temp = new ArrayList<>();
temp.add(p);
map.put(start, temp);
} else {
map.get(start).add(p);
}
}
return map;
}
private static List<String> generateOutputList(Map<String, List<Phrase>> map) {
List<String> output = new ArrayList<>();
for(List<Phrase> list: map.values()) {
for(Phrase p: list) {
String keyToBeSearched = p.getEnd();
if(map.containsKey(keyToBeSearched)) {
List<Phrase> temp = map.get(keyToBeSearched);
for(Phrase p2: temp) {
output.add(p.getWhole()+" "+p2.getMiddle());
}
}
}
}
return output;
}
}
class Phrase {
private final String start;
private final String middle;
private final String end;
private final String whole;
public Phrase(String initial) {
this.whole = initial;
String[] words = initial.split(" ");
this.start = words[0];
this.middle = Arrays.stream(words, 1, words.length).collect(joining(" "));
this.end = words[words.length - 1];
}
public String getStart() {
return this.start;
}
public String getMiddle() {
return this.middle;
}
public String getEnd() {
return this.end;
}
public String getWhole() {
return this.whole;
}
}