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 medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

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

Solve array-sum and city-community problems

Quick Overview

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.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Two coding problems were asked in a phone screen for a Software Engineer role: 1. **Count contiguous segments with a target sum** Given an integer array `nums` and an integer `k`, return the number of contiguous subarrays whose sum is exactly `k`. **Follow-up:** How would you handle this if the input were extremely large or arrived as a stream, so you could not store the full array in memory? Describe what information you would maintain online and the time/space trade-offs. 2. **Count independent building communities in a city grid** You are given a 2D grid representing a city map, where `1` means a building and `0` means empty land. Two building cells belong to the same community if they are adjacent vertically or horizontally. Return the number of distinct communities. **Follow-up:** If the grid is very large, how would you adapt your approach to avoid issues with recursion depth, memory usage, or loading the entire grid at once?

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

Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum is exactly k. 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
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)

Expected Output: 6

Explanation: All possible subarrays sum to 0, and there are 6 of them.

Hints

Use prefix sums. If the current prefix sum is p, then any earlier prefix sum of p - k forms a valid subarray ending here.
Store how many times each prefix sum has appeared so far in a hash map.

Part 2: Online target-sum subarray counting for a stream

Numbers arrive one by one in a stream. After each new number arrives, report the total number of contiguous subarrays seen so far whose sum is exactly k. Your algorithm should update its answer online instead of recomputing from scratch after every arrival.

Constraints

0 <= len(stream) <= 200000
-10^9 <= stream[i] <= 10^9
-10^9 <= k <= 10^9
The running totals fit in a signed 64-bit integer.

Examples

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

Expected Output: [0, 1, 2]

Explanation: After each step, the total number of valid subarrays becomes 0, then 1, then 2.

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

Expected Output: [0, 1, 2, 2, 2, 3, 3, 4]

Explanation: This shows the running total after each arrival.

Input: ([], 5)

Expected Output: []

Explanation: No arrivals means no running totals.

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

Expected Output: [1, 3, 6]

Explanation: Each new zero creates several additional zero-sum subarrays.

Input: ([5], 5)

Expected Output: [1]

Explanation: The single-element subarray [5] matches the target.

Hints

You do not need the full history of elements. Maintain only the current prefix sum, the running answer, and counts of previous prefix sums.
When a new prefix sum p arrives, add the number of earlier times you have seen p - k.

Part 3: Count independent building communities in a city grid

You are given a 2D grid where 1 represents a building and 0 represents empty land. Two building cells belong to the same community if they are adjacent vertically or horizontally. Return the number of distinct building communities.

Constraints

0 <= number of rows <= 300
0 <= number of columns <= 300
grid[r][c] is either 0 or 1

Examples

Input: [[1, 1, 0, 0], [0, 1, 0, 1], [0, 0, 1, 1], [1, 0, 0, 0]]

Expected Output: 3

Explanation: There are three separate groups of buildings.

Input: []

Expected Output: 0

Explanation: An empty grid contains no communities.

Input: [[1]]

Expected Output: 1

Explanation: A single building cell forms one community.

Input: [[1, 0], [0, 1]]

Expected Output: 2

Explanation: Diagonal cells do not connect, so these are two separate communities.

Input: [[1, 1, 1], [1, 1, 1]]

Expected Output: 1

Explanation: All building cells are connected.

Hints

Whenever you find an unvisited building cell, you have discovered a new community.
Use DFS or BFS to mark every building cell in that community before continuing.

Part 4: Count communities in a huge grid streamed row by row

A very large city map is provided row by row, where each row is a string of '0' and '1' characters. A '1' is a building and a '0' is empty land. Two building cells are in the same community if they are adjacent vertically or horizontally. Return the total number of communities while using only O(columns) additional memory and no recursion.

Constraints

0 <= len(rows)
All rows have the same length
Each row contains only '0' and '1'
The algorithm should use O(columns) additional memory

Examples

Input: []

Expected Output: 0

Explanation: No rows means no communities.

Input: ['']

Expected Output: 0

Explanation: A grid with zero columns contains no buildings.

Input: ['1100', '1100', '0011', '0011']

Expected Output: 2

Explanation: The top-left block and the bottom-right block are separate communities.

Input: ['101', '111']

Expected Output: 1

Explanation: The two top cells become connected through the second row.

Input: ['1001', '0000', '1001']

Expected Output: 4

Explanation: Each isolated building group is separated by empty rows or columns.

Hints

When scanning left to right, a building cell only needs to consider its left neighbor in the current row and its upper neighbor from the previous row.
If a component appears in the previous row but not in the current row, it can never connect to future rows again and can be finalized.

Quick Overview