Day 11: Best Time to Buy & Sell Stock

Day 11 — Best Time to Buy & Sell Stock

Coding problem

Solution outline (coding)

• Track the minimum price seen so far as you scan the array once.
• At each day, profit if sold today is price - min_so_far; update the global max profit.
• You only need one pass — classic “one buy before one sell” optimum.

Time complexity: O(n).

Space complexity: O(1).

from typing import List


class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    best = 0
    lo = float('inf')
    for p in prices:
      lo = min(lo, p)
      best = max(best, p - lo)
    return best


# Input:  prices = [7,1,5,3,6,4]
# Output: 5

SQL interview practice

1. Interview question

Companies / track: All companies (general analytics)

Universal analytics: geography rollups, time windows, and joins to user dimensions show up in almost every big-tech SQL round—think payments, ads, or subscriptions.

What you are asked to write (SQL prompt):

Phone-screen style (any large tech company) — revenue, geo, and time windows are universal.
prices(symbol, ts, price). BigQuery: using window functions, compute max profit per symbol from one buy and one sell (buy before sell) over a range; include partitioning and clustering strategy.

Tables implied by the prompt:

• prices(symbol, ts, price)
• sell(buy before sell)

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 Sliding Window 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.
• Rates: SAFE_DIVIDE or NULLIF; define numerator and denominator.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

WITH ordered AS (
  SELECT symbol, ts, price,
    MIN(price) OVER (PARTITION BY symbol ORDER BY ts ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS min_so_far
  FROM prices
)
SELECT symbol, MAX(price - IFNULL(min_so_far, price)) AS max_profit_one_trade
FROM ordered
GROUP BY symbol;