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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Find Words Containing Other Words | Meta Coding Question

Find Words Containing Other Words

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Given a list of lowercase strings, return all words that contain at least one other distinct word from the same list as a contiguous substring. Example: from `["category", "cat", "dog"]`, the result should include `"category"` because it contains `"cat"`. You are given an existing baseline solver. Your tasks are: 1. Analyze the current implementation's time and space complexity. 2. Propose a faster approach and state the expected complexity. 3. Implement the optimized version. If duplicates exist in the input, avoid duplicate output. Do not count a word as containing itself unless there is another distinct occurrence in the list.

Quick Answer: This question evaluates string-processing skills, knowledge of substring matching techniques and supporting data structures, and the ability to analyze and improve time and space complexity.

You are given a list of lowercase strings `words`. Return all unique words that contain at least one other word from the same list as a contiguous substring. Preserve the order of first appearance in the input. A straightforward baseline compares every pair of words and checks whether one is a substring of the other. If `n` is the number of words and `L` is the maximum word length, that baseline takes `O(n^2 * L^2)` worst-case time and `O(1)` extra space beyond the output. Your task is to implement a faster solution. Important rules: - Do not return duplicate words in the output. - A word does not count as containing itself if it appears only once. - If the same string appears multiple times in the input, that duplicate occurrence does count, but the output should still contain that word only once. - Example: `['category', 'cat', 'dog']` should return `['category']` because `category` contains `cat`.

Constraints

0 <= len(words) <= 20000
1 <= len(words[i]) <= 200
All strings consist only of lowercase English letters
The sum of lengths of all strings is at most 200000

Examples

Input: (['category', 'cat', 'dog'],)

Expected Output: ['category']

Explanation: `category` contains `cat`, while `cat` and `dog` do not contain any other listed word.

Input: (['mass', 'as', 'hero', 'superhero', 'her'],)

Expected Output: ['mass', 'hero', 'superhero']

Explanation: `mass` contains `as`, `hero` contains `her`, and `superhero` contains both `hero` and `her`.

Input: (['cat', 'cat', 'dog'],)

Expected Output: ['cat']

Explanation: The second `cat` counts as another occurrence, so `cat` qualifies, but it should appear only once in the output.

Input: ([],)

Expected Output: []

Explanation: An empty input list produces an empty output list.

Input: (['alone'],)

Expected Output: []

Explanation: A single occurrence of a word does not count as containing itself.

Input: (['abc', 'bc', 'c', 'abc'],)

Expected Output: ['abc', 'bc']

Explanation: `abc` contains `bc` and `c`, `bc` contains `c`, and the duplicate `abc` does not create another output entry.

Hints

The slow part of the baseline is re-checking all candidate substrings for every word. Can you preprocess the full dictionary once, then scan each word in a single pass?
A trie with failure links can match many patterns inside one text efficiently.

Quick Overview

This question evaluates string-processing skills, knowledge of substring matching techniques and supporting data structures, and the ability to analyze and improve time and space complexity.