Day 72: Subarray Sum Equals K

Day 72 — Subarray Sum Equals K

Coding problem

Solution outline (coding)

• Prefix sum array P; subarray i..j sums to k iff P[j] - P[i-1] = k.
• Use hash map count of prefix sums seen; at j, add count[P[j] - k].
• Initialize map {0:1} for subarrays starting at 0.

Time complexity: O(n).

Space complexity: O(n) — map of prefix sums.

from typing import List
from collections import defaultdict


class Solution:
  def subarraySum(self, nums: List[int], k: int) -> int:
    pref = 0
    cnt = defaultdict(int)
    cnt[0] = 1
    ans = 0
    for x in nums:
      pref += x
      ans += cnt[pref - k]
      cnt[pref] += 1
    return ans


# Input:  nums = [1,1,1], k = 2
# Output: 2

SQL interview practice

1. Interview question

Companies / track: Meta

Meta: expect event logging, ads / integrity, and social product analytics—deduping, sessionization, and window functions are frequent themes.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
transactions(user_id, ts, amount). BigQuery: compute count of subarrays (time-ordered sequences) with sum exactly K using prefix sums and hashing logic in SQL.

Tables implied by the prompt:

• transactions(user_id, ts, amount)
• subarrays(time-ordered sequences)

Engine: BigQuery — use its date, array, and approximate functions as documented.

2. Solution outline

• Clarify out loud: result grain (one row per what?), join keys, time zone, and any ORDER BY / LIMIT / tie-breakers.
• Map Prefix Sum / Hash to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Sessions / streaks: often LAG/LEAD or gap flags, then aggregate; check boundary dates.
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

-- Subarray sum = K via prefix map is best in Python; SQL sketch — aggregate sequences per user:
SELECT user_id, ARRAY_AGG(STRUCT(ts, amount) ORDER BY ts) AS timeline
FROM transactions
GROUP BY user_id;