Day 19: Min Stack

Day 19 — Min Stack

Coding problem

Solution outline (coding)

• Use a normal stack for values; maintain a second stack (or parallel min) for the minimum seen so far.
• On push, push min(x, current_min) onto the min stack; on pop, pop both.
• getMin returns top of min stack.

Time complexity: O(1) per operation amortized.

Space complexity: O(n) — two stacks in the worst case.

class MinStack:
  def __init__(self):
    self.st = []
    self.min_st = []

  def push(self, val: int) -> None:
    self.st.append(val)
    self.min_st.append(val if not self.min_st else min(val, self.min_st[-1]))

  def pop(self) -> None:
    self.st.pop()
    self.min_st.pop()

  def top(self) -> int:
    return self.st[-1]

  def getMin(self) -> int:
    return self.min_st[-1]


# Input:  push -2, push 0, push -3, getMin -> -3, pop, top -> 0, getMin -> -2
# Output: as above

SQL interview practice

1. Interview question

Companies / track: OpenAI

OpenAI / API-scale products: SQL often covers usage logs, experiments, and evaluation pipelines—clarity on keys and grain matters as much as syntax.

What you are asked to write (SQL prompt):

Frame this as metrics work for **OpenAI**-scale surfaces (ads, product, or engagement — as the tables suggest).
prices(symbol, ts, price). BigQuery: compute running minimum price per symbol using window functions and discuss whether to materialize min_stack-like summaries vs recomputing on the fly.

Tables implied by the prompt:

• prices(symbol, ts, price)

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 Stack Design to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• 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).

SELECT symbol, ts, price,
  MIN(price) OVER (PARTITION BY symbol ORDER BY ts ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS running_min
FROM prices;