It's problems like that which terrify newbies.
20% of our applicants pass this, and they all go through a phone screen first..
I think it's a fair question..... but "())))(((" would fail in the second condition
Would something like this pass (maybe with some comments and test cases)?
1 @tailrec
2 def hasBalancedParens(s:String, open:Int):Boolean = {
3 if(s.length == 0) open==0
4 else if(s.charAt(0) == '(') hasBalancedParens(s.tail, open+1)
5 else if(s.charAt(0) == ')') open>0 && hasBalancedParens(s.tail, open-1)
6 else hasBalancedParens(s.tail, open)
7 };
If this answer fails (modulo any stupid mistakes; idk if it even compiles), you might consider being much more specific about the desired average runtime complexity.
If this answer passes but would fail if line 4 was modified, you might consider re-writing your problem text to include either "Feel free to ask for clarifications" or "A string has balanced parentheses only if every closing parenthesis is preceded by an opening parenthesis". People tend to not treat interviews like normal interactions, and interview questions don't have a surrounding context so it's hard to determine what it means for an answer to be correct.
function getBalance (parenStr) {
var count = 0;
for (var i = 0; i < parenStr.length; i++) {
if (parenStr[i] === '(') { count++; }
else if (parenStr[i] === ')') { count--; }
}
return count === 0;
}In a previous job, a question like that would not even get a 20% pass rate, but it also have a lot to do with where we were sourcing our employees: If you are talking to generic contracting firms that employ people in giant, generic behemoths, you WILL get a lot of terrible candidates from them. From the powerpoint architect that hasn't written a line of code in weeks, to people that just had a job at big megacorp, and did the minimum possible not to get fired (and, in some of those corps, that's really little).
It got that bad that there were employer patterns that we considered resume black flags: Spent one year in MasterCard? Well, they hire pretty much anyone for a year, and they just don't get renewed, so we will understand that experience as 'you weren't good enough to work there, and most people there suck'.
For example, your code would return true for ")())((" even though nothing is balanced. I was thinking more of a stack; push to stack only on opens, pop on closes, if we get a close before an open is on the stack, then we return false.
But I only thought about it for a few minutes so it's rather rudimentary.
I would venture to say there are a small set of positions where you'd use these exact skills on a fairly frequent basis.