Balance a string with parentheses. "a(b)" - "a(b)"; "(((((" - ""; "(()())" - "(()())"; ")ab(()" - "ab()"; etc...

Question

Balance a string with parentheses. "a(b)" -> "a(b)"; "(((((" -> ""; "(()())" -> "(()())"; ")ab(()" -> "ab()"; etc...

as well Interview Candidate · Accepted Answer

Hey! I had a similar experiences with you last week! I have a light accent, and it always throw me off when the person interviewing me over the *phone* has an accent as well. On one hand, it shows me they are diverse, but it did not make feel at east at all on the spot. My interviewer made me feel like he was going through a check list as well. Each time I answered his questions, he sort moved on to the next question quickly. So I have no idea, should I stop talking and wait for him or should I just MOVE ON to the next question. 

When we finally got to the coding session. It was very new for me to talk through my headset and listen and think AND write code at the same time. I got really stressed out for the first 10 minutes. I could not think straight. I got frustrated on myself of not able to think. Once I get over that, the questions are some what reasonable.

This is my first codepad-sharing-phone-interview! It is one of those situations, if you are kind of person like me who got nervous about this kind of situation, you might be out of luck of  not be able to think straight. However, once you know what it is like, you will be able to get over with it next time!

Anonymous · Answer

Observed that in any case, we would end with the same number of parens as we started with or less. So this is an exercise in removing parens.

Decided there should be a pre-processing step to remove edges in instances of a LP or RP that clearly came in the wrong order, such as ")ab(()" -> "ab(()".

Next there would need to be balancing. Keep count of the LPs and RPs with a pass over the String, and also note the first index of LP and last index of RP. If LP count is higher, remove first LP. If RP count is higher, remove last RP. I did not get beyond this in the allotted time.  I'm sure that that approach would imply the need to pass over the string 1 to many times, so maybe stashing the indexes of all LPs and RPs and removing them in one swoop would be better. Regardless, this was my approach.

Anonymous · Answer

Thanks for the feedback! I think a lot of people end up in this boat from what I read. And it makes me feel like to a degree you just gotta get lucky, and take a shot before hand!

Meta

Meta interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches