Day 43: Climbing Stairs

Day 43 — Climbing Stairs

Coding problem

Solution outline (coding)

• Recurrence: f(n) = f(n-1) + f(n-2) with base f(0)=1, f(1)=1 (or adjust indices per problem).
• Iterate with two variables instead of full array.
• Match problem statement (1 vs 2 steps at a time).

Time complexity: O(n).

Space complexity: O(1) — rolling variables.

class Solution:
  def climbStairs(self, n: int) -> int:
    a, b = 1, 1
    for _ in range(n - 1):
      a, b = b, a + b
    return b


# Input:  n = 3
# 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).
stairs(user_id, day, steps). BigQuery: model DP-like cumulative metric: for each user, compute ways to reach a step goal using previous 1 or 2 days via iterative aggregation.

Tables implied by the prompt:

• stairs(user_id, day, steps)

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 1D DP 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).

WITH ordered AS (
  SELECT user_id, day, steps,
    LAG(steps, 1) OVER (PARTITION BY user_id ORDER BY day) AS s1,
    LAG(steps, 2) OVER (PARTITION BY user_id ORDER BY day) AS s2
  FROM stairs
)
SELECT user_id, day, steps + IFNULL(s1, 0) + IFNULL(s2, 0) AS ways_like_dp
FROM ordered;