Katkat
Back

Determine validity after digit-constrained deletions

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Determine validity after digit-constrained deletions states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You're given a string S of length n consisting only of '(' , ')' , and digits '0'–'9'. For every digit at index i with numeric value v: (

  1. you must delete exactly v parentheses that occur at indices strictly less than i; (
  2. a given parenthesis can be deleted at most once across all digits; (
  3. digits themselves are not deleted and should be ignored when checking validity. After choosing deletions for all digits, consider the sequence of remaining parentheses (ignoring digits). Return true if there exists at least one choice of deletions such that the remaining parentheses form a valid parentheses string, otherwise return false. Also describe an efficient algorithm, its time and space complexity, and optionally output one valid witness set of deletions if it exists.