How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Find concatenated words in list | Amazon Coding Question

Quick Overview

This question evaluates proficiency in string manipulation, efficient lookup structures (e.g., hashing/trie) and dynamic programming or recursion for word segmentation, testing algorithmic efficiency and data-structure selection within the Coding & Algorithms domain.

Find concatenated words in list

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

##### Question LeetCode 472. Concatenated Words – Given an array of strings words, return all words that are concatenations of at least two shorter words also present in the array. leetcode.com/problems/concatenated-words/description/

Quick Answer: This question evaluates proficiency in string manipulation, efficient lookup structures (e.g., hashing/trie) and dynamic programming or recursion for word segmentation, testing algorithmic efficiency and data-structure selection within the Coding & Algorithms domain.

Given an array of strings `words` (without duplicates), return all the words that are *concatenated words* in the given list. A **concatenated word** is defined as a string that is composed entirely of at least two shorter words (not necessarily distinct) from the same input array. **Example 1:** ``` Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] Output: ["catsdogcats","dogcatsdog","ratcatdogcat"] Explanation: "catsdogcats" = "cats" + "dog" + "cats" "dogcatsdog" = "dog" + "cats" + "dog" "ratcatdogcat"= "rat" + "cat" + "dog" + "cat" ``` **Example 2:** ``` Input: words = ["cat","dog","catdog"] Output: ["catdog"] ``` Return the concatenated words in any order. The empty string is never a concatenated word.

Constraints

1 <= words.length <= 10^4
1 <= words[i].length <= 30 (per LeetCode); the input contains no duplicate words
words[i] consists of lowercase English letters
0 <= sum of words[i].length <= 10^5
A concatenated word must be formed from at least two shorter words already present in the array
Component words may be repeated (e.g. "cats"+"dog"+"cats")

Examples

Input: (["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"],)

Expected Output: ['catsdogcats', 'dogcatsdog', 'ratcatdogcat']

Explanation: Canonical example: 'catsdogcats'=cats+dog+cats, 'dogcatsdog'=dog+cats+dog, 'ratcatdogcat'=rat+cat+dog+cat. 'hippopotamuses' cannot be split into other listed words.

Input: (["cat","dog","catdog"],)

Expected Output: ['catdog']

Explanation: 'catdog' = 'cat' + 'dog', a concatenation of exactly two shorter words.

Input: ([],)

Expected Output: []

Explanation: Empty input list yields no concatenated words.

Input: (["a"],)

Expected Output: []

Explanation: A single word cannot be a concatenation of two or more words.

Input: (["","",""],)

Expected Output: []

Explanation: The empty string is never reported as a concatenated word and is not used as a zero-length building block.

Input: (["a","b","ab","abc"],)

Expected Output: ['ab']

Explanation: 'ab'='a'+'b'. 'abc' cannot be formed because 'c' is not in the array.

Input: (["nuts","and","bolts","nutsandbolts","bolt"],)

Expected Output: ['nutsandbolts']

Explanation: 'nutsandbolts'='nuts'+'and'+'bolts'. Note 'bolt' alone leaves a trailing 's' so the split must use 'bolts'.

Hints

A word qualifies if it can be broken ("word-broken") into pieces that are all themselves in the dictionary — this is the classic Word Break problem applied to each word.
Put all words in a hash set for O(1) average lookups, then run a DP over each word: dp[i] is true if the prefix of length i can be segmented into dictionary words.
To enforce 'at least two shorter words', forbid using the whole word itself as a single piece — exclude the segment that spans the entire word (j==0 and i==len).
Be careful with the empty string: it should never be reported, and don't let it act as a free zero-length building block.

Quick Overview