Day 20: Valid Parens + Min Remove Parens

Day 20 — Valid Parens + Min Remove Parens

Coding problem

Solution outline (coding)

• Valid parentheses (20): push opening chars; on closing, pop and verify match; stack empty at end.
• Min remove (1249): stack indices of ( or two-pass: remove invalid ) then invalid ( from the left.
• Watch empty stack on pop — invalid closing.

Time complexity: O(n) — one pass per problem on string length n.

Space complexity: O(n) — stack depth.

class Solution:
  def isValid(self, s: str) -> bool:
    st = []
    pairs = {')': '(', '}': '{', ']': '['}
    for ch in s:
      if ch in '({[':
        st.append(ch)
      else:
        if not st or st[-1] != pairs.get(ch):
          return False
        st.pop()
    return not st

  def minRemoveToMakeValid(self, s: str) -> str:
    s_list = list(s)
    st = []
    for i, ch in enumerate(s):
      if ch == '(':
        st.append(i)
      elif ch == ')':
        if st:
          st.pop()
        else:
          s_list[i] = ''
    for i in st:
      s_list[i] = ''
    return ''.join(s_list)


# Input:  isValid("()[]{}") -> True
# Output: minRemoveToMakeValid("lee(t(c)o)de)") -> one valid form e.g. "lee(t(c)o)de"

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).
text_events(doc_id, ts, raw_text). BigQuery: using REGEXP, filter only parentheses characters, then compute a flag for balanced vs unbalanced; design a query to find docs most frequently invalid after updates.

Tables implied by the prompt:

• text_events(doc_id, ts, raw_text)

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 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).

WITH cleaned AS (
  SELECT doc_id, ts, REGEXP_REPLACE(raw_text, r'[^()]', '') AS parens_only
  FROM text_events
),
scored AS (
  SELECT doc_id, ts, parens_only,
    LENGTH(parens_only) - LENGTH(REPLACE(parens_only, '(', '')) AS opens,
    LENGTH(parens_only) - LENGTH(REPLACE(parens_only, ')', '')) AS closes
  FROM cleaned
)
SELECT doc_id, COUNTIF(opens != closes) AS invalid_count
FROM scored
GROUP BY doc_id
ORDER BY invalid_count DESC
LIMIT 20;