Day 68: Longest Valid Parentheses

Day 68 — Longest Valid Parentheses

Coding problem

Solution outline (coding)

• Stack indices of (; on ), pop or mark invalid.
• Or DP: dp[i] = longest valid ending at i.
• Two-pass: remove invalid ) left-to-right, then ( right-to-left.

Time complexity: O(n).

Space complexity: O(n) stack or O(n) DP.

class Solution:
  def longestValidParentheses(self, s: str) -> int:
    st = [-1]
    best = 0
    for i, ch in enumerate(s):
      if ch == '(':
        st.append(i)
      else:
        st.pop()
        if not st:
          st.append(i)
        else:
          best = max(best, i - st[-1])
    return best


# Input:  s = ")()())"
# Output: 4

SQL interview practice

1. Interview question

Companies / track: Meta

Meta: expect event logging, ads / integrity, and social product analytics—deduping, sessionization, and window functions are frequent themes.

What you are asked to write (SQL prompt):

Frame this as metrics work for **Meta**-scale surfaces (ads, product, or engagement — as the tables suggest).
parens_sequences(user_id, seq, ts). BigQuery: compute longest valid parentheses substring length via UDF and aggregate distribution per user.

Tables implied by the prompt:

• parens_sequences(user_id, seq, ts)

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 / 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).
• Sessions / streaks: often LAG/LEAD or gap flags, then aggregate; check boundary dates.
• Arrays / UDFs: UNNEST and offsets for index; say when logic belongs in SQL vs a UDF.
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT user_id, MAX(LENGTH(seq)) AS max_raw_len FROM parens_sequences GROUP BY user_id;