Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Meta coding round, one problem, the whole thing was basically a deep dive on a single array question. Felt okay during it but realized afterward I probably rushed the complexity analysis.

Questions Asked (1)

Given an integer array and a target value T, count the number of contiguous subarrays whose elements sum to T. Your solution must run in linear time. Also explain how your approach handles negative numbers, edge cases like T = 0, and an empty prefix.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the prefix sum trick going in, which saved me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to store the frequency of prefix sums seen so far, then for each element compute the current prefix sum and check if (current prefix sum - T) exists in the map, adding its frequency to the count. This yields O(n) time and handles negative numbers naturally because prefix sums can decrease. Explain that the empty prefix (sum 0) is initialized with frequency 1 to account for subarrays starting at index 0.

Pro tip: Mention that this is a classic application of the 'two-sum' pattern to subarrays, and that the same technique works for counting subarrays with sum divisible by K or with XOR equal to a target. Also, clarify that the hash map stores frequencies, not just presence, to count all valid subarrays.

1. Clarify the problem and constraints

Restate the problem: count contiguous subarrays summing to T in O(n) time. Confirm that the array can contain negative numbers and that T can be zero. Ask if the array is mutable or if extra space is allowed (hash map uses O(n) space).

2. Explain the prefix sum + hash map approach

Describe how to compute prefix sums on the fly and use a hash map to store the frequency of each prefix sum seen so far. For each index, check if (current prefix sum - T) is in the map; if so, add its frequency to the count. Then add the current prefix sum to the map.

3. Handle edge cases and negative numbers

Initialize the map with {0: 1} to account for the empty prefix (subarrays starting at index 0). Explain that negative numbers are handled because prefix sums can decrease, but the hash map still correctly identifies previous sums. For T=0, the approach counts subarrays with sum zero, including empty subarrays? No, empty subarrays are not counted because we only consider contiguous subarrays of length >=1; the empty prefix is only used as a starting point.

4. Walk through a small example

Choose a small array (e.g., [1, -1, 1, -1] with T=0) and step through the algorithm to demonstrate correctness, especially with negative numbers and T=0. Show how the count updates and how the map frequencies change.

5. Analyze complexity and trade-offs

State that time complexity is O(n) and space complexity is O(n) due to the hash map. Mention that this is optimal for time, but if space is a concern, a two-pointer approach could be used for non-negative numbers, but it fails with negatives. Emphasize that the hash map approach is necessary for general integers.

Key Points to Mention

Prefix sum technique: cumulative sum from start to current index.
Hash map stores frequency of each prefix sum encountered so far.
Key insight: subarray sum from i+1 to j equals prefix[j] - prefix[i], so we need prefix[i] = prefix[j] - T.
Initialization with {0: 1} to handle subarrays starting at index 0 (empty prefix).
Negative numbers are naturally handled because prefix sums can go up and down, but the hash map still finds complementary sums.
Edge cases: T=0 (counts subarrays with sum zero), empty array (returns 0), and all elements zero (counts all subarrays).

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