Company: Google
Level: L3 (Software Engineer)
Round: Coding
Status: Awaiting
The Problem (Generic Overview)The question was a string manipulation and validation problem involving parentheses (, ) and digits 0–9. Each digit acted as a conditional deletion constraint targeting characters to its left. The goal was to determine whether at least one valid sequence of deletions could yield a strictly balanced parenthesis string.Interview Flow & DiscussionClarification & Constraints (approx. 5 mins):
Clarified edge cases like zero digits (0), insufficient characters to the left, and whether consecutive digits should be combined (they shouldn't be; each digit acts sequentially).
Brute Force Approach (approx. 10 mins):
Discussed the initial recursive backtracking approach where every digit branches out into all possible combinations of deletions using combinations.
Time Complexity:O(2^N*N).
Optimized Approach & Trade-offs (approx. 15 mins):
Implemented memoization on state keys (index, current_string_state) to prune overlapping subproblems.Discussed why a retroactive left-to-right approach is required because deletion instructions appear downstream from their targets.
Touched upon an advanced Interval Dynamic Programming concept for a theoretical O(N^3) bound, but reasoned why memoized backtracking is preferred in an interview setting due to implementation clarity and was also running out of time.
Coding & Dry Run (approx. 15 mins):
Wrote clean, production-ready Python code with strong type hinting, helper validation functions, and modular structure.Walked through edge cases (empty left pools, digit 0, strict balance checking).
Would like to know what would be the verdict based on the experience I shared above?
