Google Software Engineer Interview Experience — Interviewer Told Me Mid-Round I'd Failed the Parentheses DP Problem

Round 1: The input is a string made up of parentheses and numbers, something like "(( ))2 )1( )".

Index: 0 1 2 3 4 5 6 7 8
Element: ( ( ) ) 2 ) 1 ( )

Say the index of a number is i — for example the number 2 is at index 4, and the number 1 is at index 6. For a given number, you have to pick:

1. Exactly that many parentheses to remove. For the number 2, you pick two parentheses from before it and remove them — i.e. from "(( ))" you pick two to delete. For the number 1, you pick one to delete from "(( )) )".
2. The parentheses you remove for a number must be located before that number, and you must remove exactly that many — for the number 2 you can't remove only one.

Also, once a parenthesis is removed it's gone — it can only be removed once. So you can't have the number 2's operation use up a parenthesis and then have the number 1's operation try to remove that same one again.

Return whether, after doing all the removal operations, it's possible for the parentheses left over to be valid (return true or false).

For example, one valid answer: for the 2, remove the parentheses at index 1 and 2; for the 1, remove the parenthesis at index 5. What's left is "()()", which is valid. One invalid answer: for the 2, remove the parentheses at index 1 and 2; for the 1, remove the parenthesis at index 0. What's left is "))()" — not valid.

Since there are many ways to do the removals, and at least one of them is valid, you return true. (The search space is choosing k1 out of n1, k2 out of n2, and so on.)

(My approach was backtracking that records the removal path, while a StringBuilder tracks what's left after each dfs to set up the next round of backtracking. After each dfs finished I checked whether it was valid — but the interviewer told me on the spot that this wouldn't work. I think he wanted at least a dp + dfs combo, using a bitmask to track which parentheses survive.)

(I think this interviewer just wanted me to do it his way — honestly my approach was correct too, it just tracked one extra removal state, with the StringBuilder tracking survivors at the same time, and the time complexity wasn't bad either. But there was nothing I could do — he just said flat out the approach doesn't work. To be fair he was pretty honest about it, basically telling me straight up I'd failed this round. I don't know what to say — I'd prepared for a long time and I failed this round. Looking back, if I'd just finished writing the whole thing out and then optimized with memoization on the StringBuilder, it probably would have been fine. During an interview I really think it's better to get something written down first — getting cut off right as I was trying to finish so I could optimize really rattled me. I guess he thought I was too far from the optimal solution, and he was trying to give me a hint but I couldn't catch it.)

(The interviewer for this round was honest with me, I'll give him that... he tried to nudge me toward it and I just couldn't get there. Bad luck, and my ability to think on my feet wasn't great either.)

Of course, thinking about it after the fact — maybe you could let the parentheses cancel themselves out first, and then compare against the numbers.

Second question: numbers come in one at a time, and you have to return the running median — e.g. for 3, 4, 5 coming in one at a time, the median after each is 3, 4, 4. Two heaps handles that. After finding the median you also had to find its "loose median" — for 3, the loose median is the k such that 2^k < 3 < 2^(k+1), so the range is [2^1, 2^2]; you can get there with a bitmask, something like 1 << k. The follow-up was: what's the bottleneck of this algorithm? Answer: the heaps need memory, so once the numbers get large enough you run out. Then he asked what you'd do about that — I said bucket sort or external sort, and the interviewer said that works.

Round 3: Behavioral. I thought this one was unusual — every question was a hypothetical, nothing tied to my actual past experience. Like "suppose you're a senior manager and one of your reports is overwhelmed, what do you do" — that kind of thing.

There were only three rounds total; the phone screen's result was folded into the onsite, so it counted as three rounds altogether.

God, this was rough... After the first round I completely didn't want to keep going, but I gritted my teeth and did the rest anyway. Honestly, if they'd made me actually write out the bitmask-based dp with all the state transitions, I probably wouldn't have gotten that right either. I feel awful, like I want to cry — I know failing an interview is completely normal, but I still feel bad about it.