Before and After Puzzle

Before and After Puzzle

What is this problem about?

The "Before and After Puzzle interview question" is a string concatenation challenge. You are given a list of phrases. A "puzzle" is formed by merging two phrases, $A$ and $B$, if the last word of phrase $A$ is exactly the same as the first word of phrase $B$. The resulting phrase should contain the shared word only once. You need to find all unique merged phrases and return them in lexicographical (alphabetical) order.

Why is this asked in interviews?

Companies like Clutter use the "Before and After Puzzle coding problem" to test a candidate's ability to handle string parsing, hash maps, and sorting. It evaluates whether you can efficiently find pairs that satisfy a condition without using a nested $O(N^2)$ loop that might be too slow for larger datasets. It's a test of "Hash Table interview pattern" and "String interview pattern."

Algorithmic pattern used

This problem is best solved using a Hash Map for Prefix/Suffix indexing.

1. Parsing: Split each phrase into three parts: the first word, the last word, and the "middle" (if any).
2. Indexing: Use a hash map where keys are "first words" and values are lists of phrase indices that start with that word.
3. Matching: Iterate through each phrase $A$. Look at its "last word." Check the hash map to see which phrases $B$ start with that word.
4. Merging: For every valid pair $(A, B)$, merge them. Ensure $A eq B$ (unless allowed by problem constraints).
5. Deduplication: Use a Set to store the merged phrases to handle duplicates.
6. Sorting: Convert the set to a list and sort it.

Example explanation

Phrases: ["writing code", "code is fun", "fun times"]

1. Phrase 1 ends in "code". Phrase 2 starts with "code".
   • Merge: "writing code is fun".
2. Phrase 2 ends in "fun". Phrase 3 starts with "fun".
   • Merge: "code is fun times". Result: ["code is fun times", "writing code is fun"].

Common mistakes candidates make

• Splitting incorrectly: Forgetting that a phrase might consist of only a single word (where the first word and last word are the same).
• Inefficient Search: Using a nested loop to compare every pair of strings, which is $O(N^2 imes S)$ where $S$ is string length.
• Missing Duplicates: Not using a set to handle cases where different pairs of phrases might result in the same merged string.

Interview preparation tip

When searching for pairs that share a common key, always use a Hash Map. It turns a search into an $O(1)$ lookup. Practice splitting strings by space and re-joining them—these are foundational "String interview pattern" skills.