throwawayinterv

As I suggested in another comment, it might be in general bad advice to try to get people to ask clairfying questions about non-contextual interview problems. If you want to measure social adeptness / willingness to ask for clarification -- which are important! -- consider interview questions that have a "role playing" component or actively invite the interviewee to ask questions.

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

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.