Day 79: Decode Ways

Day 79 — Decode Ways

Coding problem

Solution outline (coding)

• dp[i] = ways to decode s[0:i]; single digit and double digit if valid.
• Handle leading zero and 06 vs 6 rules.
• Rolling two values can reduce space.

Time complexity: O(n).

Space complexity: O(n) or O(1) rolling.

class Solution:
  def numDecodings(self, s: str) -> int:
    if not s or s[0] == '0':
      return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
      if s[i - 1] != '0':
        dp[i] += dp[i - 1]
      two = int(s[i - 2 : i])
      if 10 <= two <= 26:
        dp[i] += dp[i - 2]
    return dp[n]


# Input:  s = "226"
# 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).
messages(user_id, ts, encoded_string). BigQuery: implement DP-like decode count in UDF per encoded_string and aggregate fail vs success rates.

Tables implied by the prompt:

• messages(user_id, ts, encoded_string)

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).
• Aggregate: fix GROUP BY keys, then HAVING for thresholds (e.g. min volume).
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Rates: SAFE_DIVIDE or NULLIF; define numerator and denominator.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT user_id, encoded_string, LENGTH(encoded_string) AS enc_len FROM messages;