Meta·Software Engineer·Onsite - Coding / Algorithms·Senior

Senior

Apr 2026

Summary

AI Coding round at Meta for a Research Scientist role. One problem, four test files with progressively harder inputs, and a clock ticking. The real challenge wasn't solving the problem, it was solving it fast enough at scale.

Questions Asked (1)

Given an array of strings, find the maximum length of a string formed by concatenating a subsequence such that all characters in the result are unique.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Started with a naive backtracking approach and it passed the first two files fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the problem asks for the maximum length of a concatenation of a subsequence (preserving order) where all characters are unique. Then propose a bitmask dynamic programming solution that tracks the set of used characters and the maximum length achievable, iterating through the strings and updating states.

Pro tip: Mention that you can prune strings that themselves contain duplicate characters or have characters overlapping with the current mask, and that the state space is only 2^26 for lowercase letters, making it feasible. Also, discuss trade-offs between time and space, and possibly an alternative meet-in-the-middle approach for very large inputs.

1. Clarify the problem

Confirm that the subsequence must preserve the original order of strings, and that the concatenated result must have all unique characters. Ask about constraints (e.g., alphabet size, number of strings, string lengths).

2. Preprocess strings

For each string, check if it has duplicate characters; if so, discard it. Otherwise, compute its character bitmask and length.

3. Define DP state

Use a DP array where dp[mask] = maximum length of a valid concatenation using exactly the characters in mask. Initialize dp[0] = 0 and others to -1.

4. Transition

For each valid string, iterate over all masks. If the string's mask does not overlap with the current mask, update dp[mask | string_mask] = max(dp[mask | string_mask], dp[mask] + len(string)).

5. Return result

After processing all strings, the answer is the maximum value in the dp array.

Key Points to Mention

Bitmask representation of character sets for efficient overlap checks.
Dynamic programming over subsets (masks) to maximize length.
Time complexity: O(N * 2^A) where A is alphabet size (e.g., 26), and space O(2^A).
Pruning invalid strings (with duplicates) early to reduce N.
Trade-offs: DP is simple but may be heavy for large A; meet-in-the-middle can reduce time for large N.
Handling of empty strings or strings with no characters (length 0) appropriately.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.