How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve Subarray Sum and Local Minimum

Quick Overview

This question evaluates array algorithm proficiency and complexity analysis by testing the ability to count target-sum contiguous subarrays and to locate a local minimum under a logarithmic-time constraint. It is commonly asked in the Coding & Algorithms domain to measure practical implementation skills and conceptual understanding of algorithmic patterns and time-complexity guarantees.

Solve Subarray Sum and Local Minimum

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

Two coding problems were reported in the same phone-screen round: 1. **Count target-sum subarrays.** Given an integer array `nums` and an integer `k`, return the number of contiguous subarrays whose sum is exactly `k`. 2. **Find any local minimum in `O(log n)`.** Given an array `nums` of length `n >= 1` where every pair of adjacent elements is different, return any index `i` such that `nums[i]` is a local minimum: - `i = 0` is valid if `nums[0] < nums[1]` - `i = n - 1` is valid if `nums[n - 1] < nums[n - 2]` - otherwise, `i` is valid if `nums[i] < nums[i - 1]` and `nums[i] < nums[i + 1]` The required time complexity for the second problem is `O(log n)`.

Quick Answer: This question evaluates array algorithm proficiency and complexity analysis by testing the ability to count target-sum contiguous subarrays and to locate a local minimum under a logarithmic-time constraint. It is commonly asked in the Coding & Algorithms domain to measure practical implementation skills and conceptual understanding of algorithmic patterns and time-complexity guarantees.

Part 1: Count Target-Sum Subarrays

Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum is exactly k. A subarray is a continuous block of elements in the array. The array may contain positive numbers, negative numbers, and zeros.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
-10^9 <= k <= 10^9

Examples

Input: ([1, 1, 1], 2)

Expected Output:

Explanation: The subarrays [1, 1] at indices (0..1) and (1..2) both sum to 2.

Input: ([1, 2, 3], 3)

Expected Output:

Explanation: The valid subarrays are [1, 2] and [3].

Input: ([3, 4, 7, 2, -3, 1, 4, 2], 7)

Expected Output:

Explanation: There are four valid subarrays whose sum is 7.

Input: ([], 0)

Expected Output:

Explanation: An empty array has no subarrays.

Input: ([1, -1, 0], 0)

Expected Output:

Explanation: The valid subarrays are [1, -1], [0], and [1, -1, 0].

Hints

Think about prefix sums: if prefix_sum[j] - prefix_sum[i] == k, then the subarray (i+1..j) has sum k.
Use a hash map to count how many times each prefix sum has appeared so far.

Part 2: Find Any Local Minimum in O(log n)

Given an array nums of length n >= 1 where every pair of adjacent elements is different, return any index i such that nums[i] is a local minimum. An index i is a local minimum if: - i == 0 and nums[0] < nums[1], or - i == n - 1 and nums[n - 1] < nums[n - 2], or - 0 < i < n - 1 and nums[i] < nums[i - 1] and nums[i] < nums[i + 1] Your algorithm must run in O(log n) time.

Constraints

1 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
nums[i] != nums[i + 1] for all 0 <= i < n - 1

Examples

Input: ([9],)

Expected Output:

Explanation: With one element, index 0 is trivially a local minimum.

Input: ([2, 1, 3],)

Expected Output:

Explanation: nums[1] = 1 is smaller than both neighbors.

Input: ([5, 4, 3, 2, 1],)

Expected Output:

Explanation: The array is strictly decreasing, so the last element is the only local minimum.

Input: ([1, 2, 3, 4],)

Expected Output:

Explanation: The array is strictly increasing, so the first element is the only local minimum.

Input: ([9, 7, 3, 4, 8],)

Expected Output:

Explanation: nums[2] = 3 is smaller than both 7 and 4, so index 2 is a local minimum.

Hints

First check the boundary cases: the first or last element may already be a local minimum.
During binary search, if nums[mid] is greater than its left neighbor, then a local minimum must exist on the left side; otherwise it must exist on the right side.

Last updated: Apr 28, 2026

Loading coding console...

Quick Overview

Solve Subarray Sum and Local Minimum

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

Part 1: Count Target-Sum Subarrays

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
-10^9 <= k <= 10^9

Examples

Input: ([1, 1, 1], 2)

Expected Output:

Explanation: The subarrays [1, 1] at indices (0..1) and (1..2) both sum to 2.

Input: ([1, 2, 3], 3)

Expected Output:

Explanation: The valid subarrays are [1, 2] and [3].

Input: ([3, 4, 7, 2, -3, 1, 4, 2], 7)

Expected Output:

Explanation: There are four valid subarrays whose sum is 7.

Input: ([], 0)

Expected Output:

Explanation: An empty array has no subarrays.

Input: ([1, -1, 0], 0)

Expected Output:

Explanation: The valid subarrays are [1, -1], [0], and [1, -1, 0].

Hints

Think about prefix sums: if prefix_sum[j] - prefix_sum[i] == k, then the subarray (i+1..j) has sum k.
Use a hash map to count how many times each prefix sum has appeared so far.

Part 2: Find Any Local Minimum in O(log n)

Constraints

1 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
nums[i] != nums[i + 1] for all 0 <= i < n - 1

Examples

Input: ([9],)

Expected Output:

Explanation: With one element, index 0 is trivially a local minimum.

Input: ([2, 1, 3],)

Expected Output:

Explanation: nums[1] = 1 is smaller than both neighbors.

Input: ([5, 4, 3, 2, 1],)

Expected Output:

Explanation: The array is strictly decreasing, so the last element is the only local minimum.

Input: ([1, 2, 3, 4],)

Expected Output:

Explanation: The array is strictly increasing, so the first element is the only local minimum.

Input: ([9, 7, 3, 4, 8],)

Expected Output:

Explanation: nums[2] = 3 is smaller than both 7 and 4, so index 2 is a local minimum.

Hints

First check the boundary cases: the first or last element may already be a local minimum.
During binary search, if nums[mid] is greater than its left neighbor, then a local minimum must exist on the left side; otherwise it must exist on the right side.

Last updated: Apr 28, 2026

Loading coding console...