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 Meta.

What role is this question designed for?

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

Find a String Containing Another | Meta Coding Question

Find a String Containing Another

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a list of strings, determine whether any string in the list contains another string from the same list as a contiguous substring. Return one string that contains at least one other distinct string from the list. If multiple strings qualify, return any one of them. If no such string exists, return an empty string. Example: ```text Input: ["programming", "am", "pro"] Output: "programming" ``` Explanation: `"programming"` contains both `"am"` and `"pro"` as substrings. Implement the function and explain its time and space complexity. Also discuss two or three approaches that improve on a naive brute-force comparison of every pair of strings.

Quick Answer: This question evaluates proficiency in string algorithms, substring search techniques, and algorithmic complexity analysis within the Coding & Algorithms domain.

Given a list of strings, return one string that contains at least one other distinct string from the same list as a contiguous substring. If multiple strings qualify, you may return any one of them. If no such string exists, return an empty string. A string does not count as containing itself. Also, duplicate copies of the exact same text do not create a valid match by themselves; the contained string must be a different string value. Example: Input: ["programming", "am", "pro"] Output: "programming" Explanation: "programming" contains both "am" and "pro" as substrings. After implementing the function, explain its time and space complexity. As a follow-up, discuss two or three approaches that improve on the naive strategy of comparing every pair of strings independently.

Constraints

1 <= len(strings) <= 10^4
1 <= len(strings[i]) <= 10^3
The sum of all string lengths is at most 2 * 10^5
Strings are case-sensitive and duplicate values may appear

Examples

Input: (["programming", "am", "pro"],)

Expected Output: "programming"

Explanation: "programming" contains both "am" and "pro", and no other string in the list contains a different string.

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

Expected Output: ""

Explanation: No string contains any other distinct string as a contiguous substring.

Input: (["hello"],)

Expected Output: ""

Explanation: With only one string, there is no different string to be contained.

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

Expected Output: ""

Explanation: Duplicate copies of "abc" do not count as a distinct contained string, and neither string contains a different value from the list.

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

Expected Output: "aa"

Explanation: "aa" contains "a" as a substring.

Input: (["table", "able", "zzzz"],)

Expected Output: "table"

Explanation: "table" contains "able" as a suffix, so it is a valid answer.

Hints

Checking every pair of strings separately repeats a lot of work. Can you preprocess all words into one shared search structure?
A trie with failure links (Aho-Corasick) lets you scan each word once while simultaneously checking for every other word as a substring.

Quick Overview

This question evaluates proficiency in string algorithms, substring search techniques, and algorithmic complexity analysis within the Coding & Algorithms domain.