Day 73: Min Remove Valid Parens (re-solve)

Day 73 — Min Remove Valid Parens (re-solve)

Coding problem

Solution outline (coding)

• First pass: remove invalid ) using stack of indices (or count balance).
• Second pass from right: remove extra ( — or one pass with careful tracking.
• Goal: lexicographically smallest valid string if multiple removals (problem-specific).

Time complexity: O(n).

Space complexity: O(n) — stack or char array.

class Solution:
  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:  "lee(t(c)o)de)"
# Output: valid parentheses string

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).
Same parentheses validity dataset. BigQuery: implement a timed re-check pipeline that recomputes validity after new data loads and compares with previous results.

Tables implied by the prompt:

• Infer schemas from the prompt and state them before coding.

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 (timed) to SQL: say the relational equivalent (e.g. hash map → GROUP BY + key; two pointers → ordered window + filter).
• Structure: CTEs (WITH) — one step per CTE; validate on a tiny slice (counts, nulls, duplicates).

SELECT run_id, COUNTIF(valid != LAG(valid) OVER (PARTITION BY doc_id ORDER BY run_id)) AS flips
FROM paren_validity_runs;