Day 9: 3Sum

Day 9 — 3Sum

Coding problem

Solution outline (coding)

• Sort the array so you can fix one index i and use two pointers on the remainder.
• For each i, set lo = i+1, hi = n-1, and search pairs summing to -nums[i]; skip duplicates after sorting.
• Collect unique triplets and avoid duplicate (i, lo, hi) triplets by skipping equal neighbors.

Time complexity: O(n²) — O(n log n) sort plus O(n²) two-pointer sweep.

Space complexity: O(1) extra beyond the output list (sort may be O(log n) stack).

from typing import List


class Solution:
  def threeSum(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n):
      if i and nums[i] == nums[i - 1]:
        continue
      t = -nums[i]
      lo, hi = i + 1, n - 1
      while lo < hi:
        s = nums[lo] + nums[hi]
        if s < t:
          lo += 1
        elif s > t:
          hi -= 1
        else:
          res.append([nums[i], nums[lo], nums[hi]])
          lo += 1
          hi -= 1
          while lo < hi and nums[lo] == nums[lo - 1]:
            lo += 1
    return res


# Input:  nums = [-1,0,1,2,-1,-4]
# Output: [[-1,-1,2],[-1,0,1]]

SQL interview practice

1. Interview question

Companies / track: Google, Meta

Meta and Google both lean on ads and product surfaces: event streams, CTR-style rates, windowed metrics, and careful handling of identity joins.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google, Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
trades(symbol, ts, price). BigQuery: for each symbol/day, conceptually find triplets of trades where prices sum to 0 within 0.01; then discuss why this is impractical and propose scalable approximation.

Tables implied by the prompt:

• trades(symbol, ts, price)

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 Two Pointers / Sort to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

-- Full triple self-join is O(n^3); use for tiny samples or pre-bucketed prices only.
WITH recent AS (
  SELECT symbol, ts, ROUND(price, 2) AS price
  FROM trades
  WHERE ts >= TIMESTAMP_SUB(CURRENT_TIMESTAMP(), INTERVAL 1 DAY)
),
sampled AS (SELECT * FROM recent TABLESAMPLE SYSTEM (1 PERCENT))
SELECT a.symbol, a.ts AS t1, b.ts AS t2, c.ts AS t3, a.price + b.price + c.price AS triplet_sum
FROM sampled AS a
JOIN sampled AS b ON a.symbol = b.symbol AND a.ts < b.ts
JOIN sampled AS c ON b.symbol = c.symbol AND b.ts < c.ts
WHERE ABS(a.price + b.price + c.price) <= 0.01
LIMIT 100;