Determine validity after digit-constrained deletions

Quick Overview

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.

Determine validity after digit-constrained deletions

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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.

Overview: 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.

Read the full Google Software Engineer interview experience this question came from

Community answers

Answer by Coderka14

#include using namespace std; class Solution { public: vector>> memo; bool solve(int i, int deleted, int balance, string& s) { if (balance < 0) return false; if (i == s.size()) return balance == 0; int &res = memo[i][deleted][balance]; if (res != -1) return res; char ch = s[i]; // Digit if (isdigit(ch)) { int required = ch - '0'; if (deleted != required) return res = false; return res = solve(i + 1, deleted, balance, s); } // Delete bool del = solve(i + 1, deleted + 1, balance, s); // Keep bool keep = false; if (ch == '(') { keep = solve(i + 1, deleted, balance + 1, s); } else { if (balance > 0) keep = solve(i + 1, deleted, balance - 1, s); } return res = del || keep; } bool solution(string s) { int n = s.size(); memo.assign( n, vector>( n + 1, vector(n + 1, -1) ) ); return solve(0, 0, 0, s); } };

Answer by mojahidislam221

boolean solution(String s) { int D = 0; for (char c : s.toCharArray()) if (Character.isDigit(c)) D += c - '0'; Set> dp = new HashSet<>(); dp.add(List.of(0, 0)); // (deleted, balance) int need = 0; for (char ch : s.toCharArray()) { if (Character.isDigit(ch)) { need += ch - '0'; final int req = need; dp.removeIf(st -> st.get(0) < req); // prefix feasibility if (dp.isEmpty()) return false; continue; } Set> next = new HashSet<>(); for (List st : dp) { int d = st.get(0), b = st.get(1); if (d < D) next.add(List.of(d + 1, b)); // delete (cap at D) if (ch == '(') next.add(List.of(d, b + 1)); // keep '(' else if (b > 0) next.add(List.of(d, b - 1)); // keep ')' } dp = next; } return dp.contains(List.of(D, 0)); } public class Sollution3 { boolean solution(String s){ int indOp = 0, indCl = 1; Set> dp = new HashSet<>(); dp.add(List.of(0,0)); int n = s.length(); int open = 0; int close = 0; for(int i=0;i> next; if(Character.isDigit(ch)) { int num = ch - '0'; next = dp.stream().filter(a -> (a.get(indOp) + a.get(indCl)) == num).collect(Collectors.toSet()); continue; } next = new HashSet<>(); for(List ele: dp){ if(ch=='('){ open++; next.add(List.of(ele.get(indOp)+1,ele.get(indCl))); next.add(ele); }else { close++; next.add(List.of(ele.get(indOp),ele.get(indCl)+1)); int count = open + close; int actualOpen = open-ele.get(indOp); int actualClose = close - ele.get(indCl); // fixed: was open - ... if(actualOpen>=actualClose){ next.add(ele); } } } dp = next; } for(List ans: dp){ if(ans.get(indOp).
Google logo
Google
Aug 8, 2025
mediumSoftware EngineerOnsiteCoding & Algorithms
31
0

Determine validity after digit-constrained deletions

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.

Clarifying Questions to Ask Guidance

  • Clarify input sizes, value ranges, mutability, return format, and tie-breaking.
  • State the target time and space complexity before coding.
  • Call out edge cases such as empty inputs, duplicates, invalid values, overflow, and boundary sizes.

What a Strong Answer Covers Guidance

  • A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
  • A correctness argument that explains why the algorithm covers all required cases.
  • Time and space complexity, plus at least one alternative approach when relevant.
  • Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions Guidance

  • How would the approach change if the input were streaming or too large for memory?
  • What invariants would you assert in production code?
  • Which tests would catch off-by-one, duplicate, or tie-breaking bugs?