Katkat
Back

Find a String Containing Another

MetaMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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

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:

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.