Day 47: Unique Paths

Day 47 — Unique Paths

Coding problem

Solution outline (coding)

• dp[i][j] = paths to (i,j) from top-left; move only right or down.
• Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]; handle first row/column as 1.
• If obstacles, zero out blocked cells.

Time complexity: O(m · n).

Space complexity: O(n) — rolling two rows if optimized.

import math


class Solution:
  def uniquePaths(self, m: int, n: int) -> int:
    return math.comb(m + n - 2, m - 1)


# Input:  m = 3, n = 7
# Output: 28

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).
Grid m×n implied by dimensions table. BigQuery: compute number of unique paths (right/down) with a combinatorial query and compare to DP-style expansion.

Tables implied by the prompt:

• paths(right/down)

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 2D DP to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Dedup: ROW_NUMBER() or explicit keys; state first vs last row wins.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

-- Grid paths C(m+n-2,m-1): compute in application for large m,n; illustration for small grid:
SELECT 28 AS unique_paths_for_3x7_grid;