Day 5: Product of Array Except Self

Day 5 — Product of Array Except Self

Coding problem

Solution outline (coding)

• Compute prefix products left-to-right (each position = product of all elements to its left).
• Compute suffix products right-to-left, or combine in a second pass without extra array if you reuse output.
• Answer at i = prefix[i] * suffix[i] — do not use division if the problem forbids it.

Time complexity: O(n) — two or three linear passes.

Space complexity: O(1) extra if you treat the output array as allowed scratch; otherwise O(n) for prefix/suffix arrays.

from typing import List


class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums)
    out = [1] * n
    p = 1
    for i in range(n):
      out[i] = p
      p *= nums[i]
    p = 1
    for i in range(n - 1, -1, -1):
      out[i] *= p
      p *= nums[i]
    return out


# Input:  nums = [1,2,3,4]
# Output: [24,12,8,6]

SQL interview practice

1. Interview question

Companies / track: Google, Netflix

Google + Netflix: often blends ads or search-scale patterns with streaming engagement (cohorts, watch-time analogs, sessionization).

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google, Netflix**-scale surfaces (ads, product, or engagement — as the tables suggest).
daily_metrics(day, metric_name, metric_value). BigQuery: for each row, compute product of metric_value for all other days in same month/metric using window functions, then rewrite with LOG/SUM/EXP to avoid overflow.

Tables implied by the prompt:

• daily_metrics(day, metric_name, metric_value)

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 / Suffix to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Filter time first: predicate on DATE(ts) / partition column before heavy joins; state the window in plain English.
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH ranked AS (
  SELECT
    day,
    metric_name,
    metric_value,
    SUM(LN(ABS(NULLIF(metric_value, 0)))) OVER (
      PARTITION BY metric_name, DATE_TRUNC(day, MONTH)
    ) - LN(ABS(NULLIF(metric_value, 0))) AS log_sum_others
  FROM daily_metrics
)
SELECT
  day,
  metric_name,
  metric_value,
  EXP(log_sum_others) AS approx_product_others
FROM ranked;