Write code to determine if a given input string contains balanced parentheses.

Question

Anonymous · Accepted Answer

An extension to this question: Modify the code to work for more brackets: {}, [].

Use a stack · Answer

loop each character
If see a "(" --- push, 
If see a ")" --- if stack empty, not balanced, else pop.
if other char, discard
end
if stack not empty, not balanced, else balanced.

Anton Spaans · Answer

No need for a stack, reducing extra space requirements to 0(1)

initialize a counter to 0.
loop over each charater:
--If see a "(" --->  counter + +,
--If see a ")" --->  counter - -.
--If see any other char, discard/do nothing
--if  counter is less than 0, not balanced
end
if counter is 0 ---> balanced : otherwise not balanced.

Runtime O(n)
Extra Space: O(1)

Google

Google interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches