Solve Two Backtracking Array Problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You will solve two independent coding problems. For each problem, first discuss edge cases, then implement a correct solution, and finally explain how you would optimize it.
### Problem 1: Find Three Cards Summing to 15
You are given a list of integer card values. Return the indices of any three distinct cards whose values sum to exactly `15`. If no such three cards exist, return an empty result.
Requirements:
- Each card may be used at most once.
- The input may contain duplicate values.
- The returned indices must be distinct.
- Discuss a brute-force approach and an optimized approach.
Example:
```text
cards = [2, 7, 4, 8, 6, 1]
```
A valid answer is indices for values `7 + 6 + 2 = 15`.
### Problem 2: Maximize Unique Characters from a Word List
You are given a list of lowercase words. Choose any subset of the words and concatenate them in any order. The final concatenated string must contain no repeated characters. Return the maximum possible length of such a concatenation.
Requirements:
- A word that contains duplicate characters internally cannot be used.
- Each word may be chosen at most once.
- Return only the maximum length, not the actual subset.
- Discuss a straightforward backtracking solution and at least one optimization.
Example:
```text
words = ["ab", "cd", "aef", "gh"]
```
One valid choice is `"cd" + "aef" + "gh"`, which has length `7` and all unique characters.
Quick Answer: This prompt evaluates algorithmic problem-solving skills focused on combinatorial search and backtracking, including handling duplicate values, index distinctness, and enforcing character-uniqueness constraints across concatenated subsets.
Part 1: Find Three Cards Summing to 15
Given a list of integer card values, return the indices of three distinct cards whose values add up to exactly `15`. If multiple valid triples exist, return the lexicographically smallest triple of indices in increasing order. If no such triple exists, return an empty list.
A brute-force approach checks every triple of indices in `O(n^3)`. A better solution should improve on that.
Constraints
- `0 <= len(cards) <= 2000`
- `-10^9 <= cards[i] <= 10^9`
- Indices in the answer must be distinct
- Duplicate card values may appear
Examples
Input: ([2, 7, 4, 8, 6, 1],)
Expected Output: [0, 1, 4]
Explanation: Values at indices 0, 1, and 4 are 2, 7, and 6, which sum to 15.
Input: ([5, 5, 5, 5],)
Expected Output: [0, 1, 2]
Explanation: There are multiple valid triples, so return the lexicographically smallest one.
Hints
- Try fixing the first two indices and asking what third value is needed to reach 15.
- To make the answer deterministic, scan `i` and `j` from left to right and choose the earliest valid `k > j`.
Part 2: Maximize Unique Characters from a Word List
You are given a list of lowercase words. Choose any subset of the words and concatenate them in any order so that the final string contains no repeated characters. Return the maximum possible length of such a concatenation.
A word that contains duplicate characters internally cannot be used at all. A straightforward solution uses backtracking over subsets. An optimized solution can represent each word as a bitmask and prune impossible branches.
Constraints
- `0 <= len(words) <= 16`
- `1 <= len(words[i]) <= 26`
- `words[i]` contains only lowercase English letters
Examples
Input: (['ab', 'cd', 'aef', 'gh'],)
Expected Output: 7
Explanation: One best choice is 'cd' + 'aef' + 'gh', which has length 7 and all unique characters.
Input: ([],)
Expected Output: 0
Explanation: Edge case: choosing nothing gives length 0.
Hints
- First discard any word that already contains a repeated character inside itself.
- Represent each valid word as a 26-bit mask so overlap checks become very fast.