Meta's 3-Part AI-Assisted Coding Question

Meta's newer coding round is staged around how you work with AI: first reason about complexity unaided, then propose a better approach, then implement it (and you may use AI for the last part). This Words Containing Others question is a clean example. Here is the full question, Java for the baseline and the optimized solution, and the rubric.

The question

Part 1 · The baseline and its complexity

The obvious solution checks every word against every other for containment. With n words of length up to m, contains is O(m) per pair, so the whole thing is O(n squared times m). State that out loud before optimizing.

import java.util.*;

class Solution {
    // Part 1 baseline: O(n^2 * m). For each word, is it inside any other word?
    List<String> substringsOfOthers(String[] words) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++)
            for (int j = 0; j < words.length; j++)
                if (i != j && words[j].contains(words[i])) { result.add(words[i]); break; }
        return result;
    }
}

Part 2 · The optimization to propose

A substring is a prefix of some suffix. So index every suffix of every word in a trie; then walking a query word from the root finds it as a prefix of some suffix, meaning it occurs inside that word. Tag each trie node with which source word reached it, so you can tell whether the match came from a different word. This trades the n-squared scan for O(total characters) to build and O(word length) per query. For a strictly linear variant you would name Aho-Corasick, which is the right reach in the AI-assisted part.

Part 3 · The implementation

Insert all suffixes, tracking the first source word at each node and whether more than one word passes through it. A word is contained in another iff its path is reached by a different word.

class Trie {
    static final int A = 26;
    static class Node { Node[] next = new Node[A]; int firstWord = -1; boolean multi = false; }

    List<String> substringsOfOthers(String[] words) {
        Node root = new Node();
        for (int i = 0; i < words.length; i++)
            for (int s = 0; s < words[i].length(); s++) insertSuffix(root, words[i], s, i);

        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++)
            if (containedInOther(root, words[i], i)) result.add(words[i]);
        return result;
    }

    private void insertSuffix(Node root, String w, int start, int word) {
        Node cur = root;
        for (int k = start; k < w.length(); k++) {
            int c = w.charAt(k) - 'a';
            if (cur.next[c] == null) cur.next[c] = new Node();
            cur = cur.next[c];
            if (cur.firstWord == -1) cur.firstWord = word;
            else if (cur.firstWord != word) cur.multi = true;   // a second word passes here
        }
    }

    private boolean containedInOther(Node root, String w, int word) {
        Node cur = root;
        for (int k = 0; k < w.length(); k++) {
            cur = cur.next[w.charAt(k) - 'a'];
            if (cur == null) return false;                       // its own suffix guarantees a path
        }
        return cur.multi || cur.firstWord != word;               // reached by some other word?
    }
}

Worst-case build is O(sum of m squared) characters; typically far less, and queries are linear in word length. If you used an assistant for Part 3, the signal is whether you caught the off-by-one in suffix insertion and the same-word exclusion, not whether you typed it yourself.

How Meta scores it

Meta interview FAQ