← Meta Interview Insights

Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026Remote

Summary

Meta software engineer coding round with two algorithmic problems. Both were on the trickier side, one a sliding window variant and one a classic backtracking problem with some nasty edge cases. Came out feeling okay but not great.

Questions Asked (2)

Q1

Given an integer array and an integer k, check whether any two equal elements exist within k indices of each other. If yes, also return the minimum such index gap. Design an O(n) time, O(k) space solution and explain how you evict stale entries as you scan.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I knew the basic contains-duplicate-ii problem but the twist here was returning the minimum gap AND the O(k) space constraint.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to store the most recent index of each element, and as you scan the array, check if the current element exists in the map and if the index difference is ≤ k. If so, update the minimum gap; otherwise, update the map with the current index. To maintain O(k) space, evict entries that are more than k indices behind the current position.

Pro tip: Emphasize that the hash map only needs to store indices within the last k positions, so you can evict stale entries by checking if the stored index is less than current_index - k. This shows you understand the space constraint and how to maintain it dynamically.

1. Clarify the problem and constraints

Restate the problem: find if any two equal elements are within k indices, and return the minimum such gap. Confirm that the array can be large, so O(n) time and O(k) space are required.

2. Choose the right data structure

Use a hash map (dictionary) to store the most recent index of each element seen so far. This allows O(1) average lookup and update.

3. Scan and check for duplicates within k

Iterate through the array with index i. For each element, if it exists in the map and i - map[element] ≤ k, update the minimum gap. Then update the map with the current index.

4. Evict stale entries to maintain O(k) space

After processing each element, remove entries from the map whose stored index is less than i - k. This ensures the map only holds indices within the last k positions.

5. Return the result

If a minimum gap was found, return it; otherwise, return -1 or indicate no such pair exists. Discuss time and space complexity: O(n) time, O(k) space.

Key Points to Mention

  • Hash map for O(1) lookups and updates.
  • Maintain only the most recent index for each element to minimize space.
  • Eviction strategy: remove entries with index < current_index - k.
  • Time complexity: O(n) because each element is processed once and eviction is amortized O(1).
  • Space complexity: O(k) because at most k+1 entries are stored at any time.
  • Edge cases: k=0 (no gap possible), k ≥ n (check entire array), duplicate elements with gap > k.

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

Q2

Given the digits 1 through 9 in order as a string, insert '+', '-', or nothing between any adjacent digits (concatenation), and optionally a leading sign before the first digit. Find an expression that evaluates to a given target T, without reparsing the string each time.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

This one hurt a little.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use recursion with memoization to explore all possible expressions by inserting operators or concatenating digits, while maintaining the current value and the last term to handle operator precedence. Alternatively, use dynamic programming to build expressions incrementally and store results for each position and target. The key is to avoid reparsing by evaluating expressions on the fly.

Pro tip: Emphasize that the solution should handle operator precedence correctly by tracking the last operand and its sign, and mention that memoization can reduce redundant computations when the same subproblem (position, current value, last term) is encountered.

1. Clarify the problem and constraints

Confirm that digits must be used in order, concatenation is allowed, and a leading sign is optional. Discuss potential constraints like target range and whether all expressions need to be found or just one.

2. Choose a recursive backtracking approach

At each digit, decide to either concatenate with the previous number, or apply '+' or '-' as a new term. Maintain the current total and the last term to correctly handle precedence.

3. Incorporate memoization

Use a hash map to cache results for states defined by (index, current total, last term) to avoid recomputing the same subproblems, especially when searching for all solutions or when the target is large.

4. Handle base case and pruning

When all digits are processed, check if the current total equals the target. Prune branches where the remaining digits cannot possibly reach the target (e.g., using bounds).

5. Analyze time and space complexity

Discuss that without memoization, the number of expressions is 3^(n-1) for n digits (plus leading sign options), but memoization can reduce redundant work. Space complexity is proportional to the recursion depth and memoization table.

Key Points to Mention

  • Operator precedence: '+' and '-' have same precedence, but concatenation forms multi-digit numbers that must be treated as a single operand.
  • State representation for memoization: (index, current total, last term) to avoid recomputing subproblems.
  • Handling leading sign: either include it as an option before the first digit or treat the first number as positive by default and allow negation.
  • Pruning strategies: if the maximum possible value from remaining digits (by concatenating all) cannot reach the target, prune the branch.
  • Time complexity: O(3^n) without memoization, but memoization can reduce to O(n * target * max_value) in some cases.
  • Space complexity: O(n) for recursion stack plus O(n * target * max_value) for memoization table if used.

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