Day 45: Coin Change

Day 45 — Coin Change

Coding problem

Solution outline (coding)

• Define dp[amt] = min coins to make amt; try each coin: dp[amt] = min(dp[amt - coin] + 1).
• Initialize dp[0]=0, others infinity; iterate amount from 1 to target.
• If dp[amount] stays infinity, return -1.

Time complexity: O(amount · len(coins)).

Space complexity: O(amount) — DP array.

from typing import List


class Solution:
  def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [0] + [10**9] * amount
    for x in range(1, amount + 1):
      for c in coins:
        if c <= x:
          dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] < 10**9 else -1


# Input:  coins = [1,2,5], amount = 11
# Output: 3

SQL interview practice

1. Interview question

Companies / track: Google

Google: SQL screens usually assume BigQuery, Ads / Search / YouTube-style fact tables, and talking through bytes processed and partition pruning.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Google**-scale surfaces (ads, product, or engagement — as the tables suggest).
coin_values(value), target_sums(user_id, target). BigQuery: for small target, precompute coin-change combination counts via arrays; discuss when to shift to code or approximations.

Tables implied by the prompt:

• coin_values(value)
• target_sums(user_id, target)

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 DP to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• 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).

WITH targets AS (
  SELECT user_id, target FROM target_sums LIMIT 100
),
coins AS (SELECT value FROM coin_values)
SELECT t.user_id, t.target, COUNT(*) AS combo_count
FROM targets AS t
CROSS JOIN coins
WHERE t.target <= 20
GROUP BY t.user_id, t.target;