Google·Software Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Google SWE interview with a pretty gnarly string/parentheses problem that had me second-guessing my approach the whole time. The problem felt deceptively clean on the surface but the deletion constraint interaction made it genuinely hard to reason about.

Questions Asked (1)

You're given a string of parentheses and digits. Each digit v at position i requires you to delete exactly v parentheses that appear before it in the string, with no parenthesis deleted more than once across all digits. Digits are ignored when checking validity. Does there exist a valid set of deletions such that the remaining parentheses form a valid sequence? Describe an efficient algorithm, its complexity, and optionally produce a witness deletion set.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I stared at this for a solid minute before saying anything.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a greedy matching with constraints: process the string left to right, maintaining a balance of unmatched parentheses and a count of required deletions from digits. Use a priority queue to select which parentheses to delete, ensuring that deletions don't break the validity of the remaining sequence. Then verify the final sequence is valid and return the deletion set if possible.

Pro tip: Emphasize that digits are ignored for validity, so you can treat them as separators or just skip them when checking balance. Also, mention that the greedy choice of deleting the earliest possible parentheses might not work; instead, use a priority queue to delete the most 'expendable' parentheses (e.g., closing parentheses that would otherwise cause imbalance).

1. Understand the problem and constraints

Clarify that each digit v requires exactly v deletions of parentheses before it, and no parenthesis can be deleted more than once. Digits are ignored when checking validity, so the remaining parentheses must form a valid sequence (balanced and properly nested).

2. Design a greedy algorithm with priority queue

Traverse the string left to right. Maintain a balance counter for parentheses and a list of available parentheses for deletion. When encountering a digit, delete the required number of parentheses from those seen so far, choosing them wisely (e.g., using a max-heap of indices of closing parentheses that are 'safe' to delete).

3. Ensure validity of remaining sequence

After processing all digits, check if the remaining parentheses form a valid sequence. If not, the algorithm should backtrack or adjust choices. Alternatively, incorporate validity checks during the greedy process to avoid invalid states.

4. Analyze complexity and optimize

The naive approach of trying all subsets is exponential. The greedy with priority queue can achieve O(n log n) time and O(n) space. Discuss potential optimizations and trade-offs.

5. Produce a witness deletion set

If a valid deletion set exists, output the indices of deleted parentheses. This can be done by recording which parentheses are deleted during the greedy process.

Key Points to Mention

Greedy strategy with priority queue to select deletions
Handling digits as constraints, not part of validity check
Maintaining balance and ensuring proper nesting
Time and space complexity analysis (O(n log n) time, O(n) space)
Edge cases: digits at start, insufficient parentheses, multiple digits
Proof of correctness or counterexample if greedy fails

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.