Katkat
Back

Solve array-sum and city-community problems

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to solve two distinct algorithmic patterns: using a prefix sum hash map to count subarrays with a target sum, and using flood fill to determine the size of connected components in a grid.

Part 1: Subarray Sums

Given an array of integers nums and an integer k, write a function countSubarrays(nums, k) that returns the total number of continuous subarrays whose sum equals k.

Constraints

  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Example

# Input: nums = [1, 1, 1], k = 2
# Output: 2
# Explanation: The subarrays [1, 1] (index 0-1) and [1, 1] (index 1-2) sum to 2.

Part 2: Community Sizes

Given a 2D grid representing a map where 1 represents a building and 0 represents empty space, two buildings are in the same community if they are connected horizontally or vertically. Write a function getMaxCommunitySize(grid) that returns the number of buildings in the largest community.

Constraints

  • m == grid.length, n == grid[i].length
  • 1 <= m, n <= 300

Example

# Input: grid = [[1, 1, 0], [1, 0, 0], [0, 0, 1]]
# Output: 3
# Explanation: The community at (0,0), (0,1), and (1,0) has 3 buildings.

Hints

Hint 1

For Part 1, use a hash map to store the frequency of prefix sums encountered so far to identify subarrays that sum to k in O(n) time.

Hint 2

For Part 2, treat the grid as an undirected graph where each cell is a node and perform a Depth-First Search or Breadth-First Search to traverse connected buildings.

Hint 3

Ensure you mark visited cells in Part 2, either by modifying the grid in-place or using a separate boolean matrix to prevent infinite loops.

Follow-up questions

  • How would you modify Part 1 if the array contained only non-negative integers?
  • In Part 2, what are the space complexity trade-offs between iterative and recursive DFS?
  • If the grid is extremely large and does not fit in memory, how would you approach counting communities?