Meta·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Meta ML Engineer interview with a combinatorics-heavy coding problem. The question was more involved than I expected and required careful thought about correctness, not just getting an answer on the board.

Questions Asked (1)

Given an array of integers that may contain duplicates, generate all unique permutations. No duplicate permutations should appear even when values repeat more than twice. Walk through your algorithm, argue why it's correct, and give the time and space complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The backtracking part wasn't the hard bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by sorting the array to group duplicates, then use backtracking with a used array to build permutations. At each recursion level, skip a duplicate value if its previous identical value hasn't been used in the current path, ensuring each unique permutation is generated exactly once. Finally, analyze time and space complexity, noting the worst-case O(n * n!) time and O(n) space for recursion and used array.

Pro tip: Explicitly connect the duplicate-skipping logic to the sorted order and the used array—this shows you understand why the condition `used[i-1] == false` prevents duplicates without needing a set. Also, mention that the same deduplication pattern applies to combination sum and subset problems, demonstrating pattern recognition.

1. Clarify and sort

Confirm that the output should be unique permutations and that order doesn't matter. Sort the input array to bring duplicates together, which simplifies duplicate skipping.

2. Design backtracking with used array

Use a recursive function that builds a permutation path. Maintain a boolean `used` array to track which indices are already in the current path. At each step, iterate over all indices, skip used ones, and skip duplicates when the previous identical value is not used.

3. Implement duplicate skipping

Inside the loop, if `i > 0` and `nums[i] == nums[i-1]` and `!used[i-1]`, continue. This ensures that for a group of equal values, they are used in a fixed order, preventing duplicate permutations.

4. Argue correctness

Explain that sorting groups duplicates, and the skip condition ensures that among equal elements, only the leftmost unused one can be chosen next. This enforces a canonical order for identical values, so each unique permutation is generated exactly once.

5. Analyze complexity

Time: O(n * n!) in the worst case (all distinct), but with duplicates it's O(n * U) where U is the number of unique permutations. Space: O(n) for recursion stack and used array, plus O(n) for the path, excluding output storage.

Key Points to Mention

Sorting the array to group duplicates and enable efficient skipping.
Using a boolean `used` array to track elements in the current permutation path.
The duplicate-skip condition: `if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;`.
Correctness argument: the condition enforces a fixed order among identical elements, so each unique permutation is generated once.
Time complexity: O(n * n!) worst-case, but often expressed as O(n * U) where U is the number of unique permutations.
Space complexity: O(n) for recursion and used array, excluding the output list.

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