Day 44: House Robber

Day 44 — House Robber

Coding problem

Solution outline (coding)

• DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — rob or skip current house.
• Base: dp[0], dp[1] from first two houses.
• Optimize to O(1) space with two rolling values.

Time complexity: O(n).

Space complexity: O(1).

from typing import List


class Solution:
  def rob(self, nums: List[int]) -> int:
    prev2 = prev1 = 0
    for x in nums:
      prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1


# Input:  nums = [2,7,9,3,1]
# Output: 12

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).
bank_transactions(user_id, ts, amount). BigQuery: compute max non-adjacent-sum of daily net amounts per user (House Robber analogue) using window functions and staging tables.

Tables implied by the prompt:

• bank_transactions(user_id, ts, amount)
• user(House Robber analogue)

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).
• Filter time first: predicate on DATE(ts) / partition column before heavy joins; state the window in plain English.
• Windows: align PARTITION BY / ORDER BY with the business rule; use QUALIFY in BigQuery when you need top-N per group.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH daily AS (
  SELECT user_id, DATE(ts) AS d, SUM(amount) AS net
  FROM bank_transactions
  GROUP BY user_id, d
),
lagged AS (
  SELECT user_id, d, net,
    LAG(net) OVER (PARTITION BY user_id ORDER BY d) AS prev_net
  FROM daily
)
SELECT user_id, d, net + IFNULL(prev_net, 0) AS rob_two_day_analog FROM lagged;