Solve array-sum and city-community problems
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Quick Answer: This question evaluates array-processing and grid/graph connectivity skills, covering counting subarrays with a target sum and identifying connected building communities in a grid; it belongs to the Coding & Algorithms domain and involves streaming/online algorithm reasoning as well as grid traversal concepts.
Part 1: Count contiguous segments with a target sum
Constraints
- 0 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= k <= 10^9
- The answer fits in a signed 64-bit integer.
Examples
Input: ([1, 1, 1], 2)
Expected Output: 2
Explanation: The valid subarrays are [1, 1] at indices 0..1 and 1..2.
Input: ([1, 2, 3], 3)
Expected Output: 2
Explanation: The valid subarrays are [1, 2] and [3].
Input: ([3, 4, 7, 2, -3, 1, 4, 2], 7)
Expected Output: 4
Explanation: There are four subarrays with sum 7.
Input: ([], 0)
Expected Output: 0
Explanation: An empty array has no contiguous subarrays.
Input: ([0, 0, 0], 0)