Day 69: Sliding Window Maximum

Day 69 — Sliding Window Maximum

Coding problem

Solution outline (coding)

• Deque stores indices of useful candidates (decreasing values for max window).
• Drop from front if out of window; drop from back while smaller than new value.
• Front is max for current window.

Time complexity: O(n) — each index pushed/popped once.

Space complexity: O(k) — deque size.

import collections
from typing import List


class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    dq = collections.deque()
    out = []
    for i, x in enumerate(nums):
      while dq and dq[0] <= i - k:
        dq.popleft()
      while dq and nums[dq[-1]] <= x:
        dq.pop()
      dq.append(i)
      if i >= k - 1:
        out.append(nums[dq[0]])
    return out


# Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
# Output: [3,3,5,5,6,7]

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).
metrics(ts, value). BigQuery: implement sliding window maximum over fixed-size time windows with window functions and ARRAYs; compare cost vs application-level computation.

Tables implied by the prompt:

• metrics(ts, value)

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 Monotonic Deque 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.
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Cost: selective columns, partition pruning, avoid SELECT * when tables are huge.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT ts, value,
  MAX(value) OVER (ORDER BY ts RANGE BETWEEN INTERVAL 59 SECOND PRECEDING AND CURRENT ROW) AS win_max
FROM metrics;