Akuna Capital·Data Scientist·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Interviewed for a Data Scientist role at Akuna Capital and got hit with a classic prefix sum problem that sounds easy until you actually have to explain the negative numbers case under pressure.

Questions Asked (1)

Given an integer array and an integer k, count the number of contiguous subarrays whose sum equals k. Solve it in O(n) time and O(n) space, explain why it handles negative numbers correctly, and walk through the complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew prefix sums going in but the negative numbers justification tripped me up more than I expected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to store the cumulative sum frequencies. Iterate through the array, updating the cumulative sum and checking if (cumulative sum - k) exists in the map. This counts all subarrays with sum k in O(n) time, and the map handles negative numbers naturally because it tracks all possible prefix sums.

Pro tip: Emphasize that the hash map approach works for negative numbers because it doesn't rely on monotonicity, unlike sliding window. Also, mention that you initialize the map with {0: 1} to account for subarrays starting from index 0.

1. Clarify the problem and constraints

Confirm that the array can contain negative numbers and that we need to count all contiguous subarrays. State that O(n) time and O(n) space are required.

2. Explain the prefix sum concept

Define prefix sum as the sum of elements from index 0 to i. A subarray from j+1 to i has sum k if prefix_sum[i] - prefix_sum[j] = k, i.e., prefix_sum[j] = prefix_sum[i] - k.

3. Describe the hash map algorithm

Initialize a hash map with {0: 1} to handle subarrays starting at index 0. Iterate through the array, update cumulative sum, and for each sum, add the frequency of (sum - k) to the count, then increment the frequency of the current sum.

4. Address negative numbers

Explain that the hash map approach works with negative numbers because it doesn't assume the prefix sums are increasing. It simply counts all pairs of indices where the difference in prefix sums equals k.

5. Analyze complexity

Time complexity is O(n) because we traverse the array once and each hash map operation is O(1) on average. Space complexity is O(n) for the hash map, which can store up to n distinct prefix sums.

Key Points to Mention

Prefix sum and its relation to subarray sum
Hash map to store frequency of prefix sums
Initialization with {0: 1} to account for subarrays starting at index 0
Why sliding window fails with negative numbers (non-monotonic prefix sums)
Time complexity O(n) and space complexity O(n)
Edge cases: empty array, k=0, all negative numbers

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