1

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;
    }

}
2
  • Just wondering: what if the input has multiple input pairs that would match on the same last/first word. Would your set approach find all those pairs?
    – GhostCat
    May 3, 2019 at 21:33
  • Yes, the 2nd for loop continues until it scans all the entries from the input list. for example, when it reaches "a man on a mission" in the gvien input list, it will scan for both "mission statement" and "mission impossible" entries.
    – InstaKarma
    May 3, 2019 at 21:41

3 Answers 3

1

It might be worth encapsulating collecting the results of you split operations so that it doesn't need to be repeated many times:

class Phrase {
    private final String start;
    private final String middle;
    private final String end;

    public Phrase(String initial) {
        String[] words = initial.split(" ");
        start = words[0];
        middle = Arrays.stream(words, 1, words.length).collect(joining(" "));
        end = words[words.length - 1];
    }

    public boolean matches(Phrase other) {
        this.end.equals(other.start);
    }

    public String combine(Phrase other) {
        assert matches(other);
        return Stream.of(this.start, this.middle, this.end, other.middle, other.end)
            .collect(joining(" "));
    }
}

Then your generation code becomes pretty simple:

List<Phrase> phrases = Arrays.stream(inputPhrases).map(Phrase::new).collect(toList());
return phrases.stream()
    .flatMap(ph1 -> phrases.stream().filter(ph1::matches).map(ph1::combine))
    .collect(toList());

I'm not certain this is more efficient but my guess is that it'd be less efficient for small inputs and much more efficient for large inputs. You could also make the streams parallel to take advantage of multiple threads of execution if your hardware can take advantage of that.

2
  • This is definitely a much better and more readable solution. I managed to run it on my IDE by removing this.end and other.end from the return statement of the combine function to get the exact output. I never knew about most of the inbuilt functions that you used until now. Thank you very much! :)
    – InstaKarma
    May 4, 2019 at 0:52
  • @InstaKarma you might like to accept the answer if you found it useful
    – sprinter
    May 5, 2019 at 3:05
1

Getting good time complexity for this problem (and many others) requires cutting down the search space. Here’s one way:

There are some end/start word pairs that are unique. Pair them up first. Use a HashMap to group phrases under their start and end words. After grouping, pair up groups of size one and remove them from the map.

Continuing to use the map, use a depth first search (with back tracking) over all remaining pairs.

The HashMap will give you constant time search speed.

2
  • Awesome! Short and concise explanation. I will try to code using your approach right away. :)
    – InstaKarma
    May 4, 2019 at 1:43
  • I managed to come up with a different solution and added a new code to my post. Can you tell me if it's a decent approach in terms of time, space complexity? Or how can I make it better?
    – InstaKarma
    May 5, 2019 at 2:33
0

Use HashMap to store the starting worlds as key and list of string associated. So When we make a search it becomes O(N) traversal Total Time=O(2N) First N to store data in HashMap. 2nd N to do lookups

1
  • Thank you very much! My updated code already follows the same approach to get O(n) time.
    – InstaKarma
    Jun 25, 2019 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.