Katkat
Back

Find Two-Word Compound Words

AmazonSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests string manipulation, hash set lookups, and the ability to efficiently identify compound words formed by the concatenation of exactly two distinct words from a provided collection.

Find Two-Word Compound Words

Given a list of unique strings, write a function find_compound_words(words) that returns a list of all strings in the input that can be formed by concatenating exactly two other strings from the same list.

Requirements

  • A word is considered a "compound word" only if it is the result of wordA + wordB, where both wordA and wordB exist in the input list.
  • wordA and wordB must be distinct words from the input; you cannot use the same word index twice (i.e., you cannot form a compound word using the same string unless that string appears as two separate entries in the input, which is disallowed by the unique constraint).
  • The output list should be sorted alphabetically.

Function Signature

def find_compound_words(words: List[str]) -> List[str]:

Examples

Example 1: Input: ["cat", "dog", "catdog", "dogcat", "bird"] Output: ["catdog", "dogcat"] Explanation: "catdog" is "cat" + "dog". "dogcat" is "dog" + "cat".

Example 2: Input: ["a", "b", "ab", "abc"] Output: ["ab"] Explanation: "abc" cannot be formed by exactly two words from the list, even though it is composed of "a", "b", and "c".

Constraints

  • 1 <= len(words) <= 10^4
  • 1 <= len(word) <= 100
  • The list contains only lowercase English letters.

Edge Cases

  • Empty list or lists with fewer than two words should return an empty list.
  • Words that are prefixes or suffixes of other words without forming a complete two-word pair.

Hints

Hint 1

Storing all words in a hash set allows for O(1) average time complexity lookups to verify if a prefix or suffix exists in the input.

Hint 2

For each word in the list, iterate through all possible split points to divide the string into two non-empty parts.

Hint 3

Ensure the split logic correctly handles cases where both parts are present in the hash set, while strictly enforcing that the two parts are separate elements from the original list.

Follow-up questions

  • How would your approach change if a compound word could be formed by concatenating more than two words?
  • If the input list were extremely large, how could a Trie (prefix tree) be used to optimize the search process?
  • What is the time complexity of your current solution in terms of N (number of words) and L (maximum length of a word)?