Katkat
Back

Find and count target-sum subarrays

TikTokMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

Find and count target-sum subarrays evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given an integer array nums and an integer target, implement: (

  1. a function that returns true if any non-empty contiguous subarray sums to target; (
  2. a function that returns the number of contiguous subarrays whose sum equals target; (
  3. assuming all numbers in nums are non-negative, design an O(n) time, O(
  4. extra-space method to find one such subarray (return its start and end indices) and explain how to adapt it to count all such subarrays. For (
  5. and (
  6. also aim for O(n) time. Discuss trade-offs, edge cases (e.g., zeros, negative numbers, large inputs), and prove correctness.