[throwawayinterv]

20% is a very suprising number...

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 };

Or should line 5 halt the loop? What if line 4 did not contain open>0 at all?

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.