Checking the balanced parenthesis as asked in interview

Question

Input:

Input contains one string S which consists of big and small latin letters, digits, punctuation marks and brackets from the set []{}().

Constraint:

Constraints. The length of S is at least 1 and at most 10⁵

Output:

If the code in S uses brackets correctly, output "Success" (without the quotes). Otherwise, output the 1-based index of the first unmatched closing bracket, and if there are no unmatched closing brackets, output the 1-based index of the first unmatched opening bracket.

Code:

console.clear();
function hashBalancedParanthesis(string) {
 // Pre: The string should have ASCII characters
 var len = string.length;
 var stack = [];
 for (var i = 0; i < len; i++) {
 var char = string[i];
 //console.log(stack + " : " + char);
 if ('([{'.indexOf(char) !== -1) // O(3 * len) 
 stack.push(char);
 else if (')]}'.indexOf(char) !== -1) { // O(3 * len)
 // Below operations are O(n) time
 var top = stack.pop();
 if (top === '[' && char !== ']') return string.indexOf(char) + 1;
 if (top === '{' && char !== '}') return string.indexOf(char) + 1;
 if (top === '(' && char !== ')') return string.indexOf(char) + 1;
 }
 }
 // Post: When here the stack should be empty for balanced case
 if (stack.length !== 0) return string.indexOf(stack.pop()) + 1;
 return true;
};
// False
console.log(hashBalancedParanthesis('('));
console.log(hashBalancedParanthesis('{[}'));
console.log(hashBalancedParanthesis('foo(bar[i);'));
// True
console.log(hashBalancedParanthesis(''));
console.log(hashBalancedParanthesis('{}[]'));
console.log(hashBalancedParanthesis('[()]'));
console.log(hashBalancedParanthesis('(())'));
console.log(hashBalancedParanthesis('foo(bar);'));

Description:

Instead of hard work since last three years I got rejected in one of the dream companies so, now I would like to have clear understanding of running time and edge cases as well as code quality.

Naming is now second priority.

As per my knowledge the above code runs in linear time \$\Theta(n)\$ where n is the string length.

PS: I am going to write a detailed analysis of my interview experience I would like to know which place would be better for it.

• Phrancis: On your PS, the best place to write an analysis of your interview experience would probably be a blog (or other similar media), also that part doesn't really add to the question so it may be best to remove it.
• Bruno Costa: // Below operations are O(1) time. Not really, indexOf is O(n).
• greybeard: "()(" - which index would be correct? (Why is it called hashXyz()? It does not output Success.)
• CodeYogi: @BrunoCosta ya modified my code to return index later on, correcting the comment.
• CodeYogi: @greybeard I think it should be 3.

Answer 1

Returning mixed types.

return string.indexOf(stack.pop()) + 1;
return true;

This is a dangerous design for the interface, as it requires strict type checks in the calling code to distinguish between the error case (non-zero integer) and the success case (true boolean).

Stick to a single data type for the return value at all cost. This would have been quite easy in this case, as every error case yields a non-zero integer. So just returning 0 to signal error free execution would have been acceptable.

---

Not fulfilling the requirements

if there are no unmatched closing brackets, output the 1-based index of the first unmatched opening bracket.

Said ahead, the "fix" suggested by @BrunaCosta doesn't work either.

The only way to reconstruct this information, is to record it when creating the stack. You can't identify the position correctly afterwards.

This shows that you lack understanding of what data you need to compute in order to solve the problem.

---

Proper testing

console.log(hashBalancedParanthesis('('));

This is by no means a unit test. A test is characterized by either failing or succeeding in a replicable way. Simply sending the output to console does neither, even less so when the expected value is only denoted as a comment in your code, making it impossible to run the tests automatically.

If you don't want to use a full testing framework, the least you could have done would have been to use the builtin assert() function to assert that each of your test cases either succeeds, or your test suite fails.

Your tests should not have been placed in the main file either. Even less so, when that means that they run on every inclusion of your library. And less again when they cause log spam without any good reason at that.

As pointed out by @BrunaCosta, your unit tests are also flawed in another way, as they don't test any non-trivial case.

---

Separation of concern

function hashBalancedParanthesis(string);

Your approach of separating the actual algorithm from the input/output handling was almost correct.

Except that you forgot to implement the latter part. You are neither capturing any input, nor are you creating any output. Except for the log spam resulting from placing your strange test cases into main file.

Providing a user interface of any sort is usually considered part of these challenges, even if it's just a console application which reads from stdin and outputs to stdout. Or in the case of JavaScript best a small HTML application.

---

Your comments are a lie

// False

The value False will never appear on the console.

Whenever you comment something - and you should if something isn't self-explanatory - you must take care to update the comments as well. A comment which is out of sync with the commented code is far worse than not having a comment at all.

• Bruno Costa: Yeah I thought that my "fix" wouldn't work for every scenario. It was a provisional improvement. That other requirement is quite pesky and I didn't take the time to even say anything about it. So, good job. Returning different types is not inherently a bad thing, the spec says you need to return Success, so you can't really avoid that.
• Ext3h: @BrunoCosta The spec say to output success. There is no input/output handling at all in the submitted code.
• CodeYogi: @Ext3h let me clear out one thing if you see my whole history of one year I tried to be very pragmatic with the unit tests having said that if you see my later half of the description you can see that I was really stumped over in the interview because of some silly off by one and similar issues. Hence I am trying to avoid writing a separate unit tests suite because it really doesn't pay off in the interviews believe me.
• Ext3h: @CodeYogi The problem with your tests isn't the lack of a framework, that only makes them less comfortable to use. The real problem is that you didn't include any test cases beyond the trivial ones. You only tested the trivial edge case "not closed and first of kind", but you should always also test the "average" or "in the middle" as well as the "at the end" cases as well. Because that's how you actually trigger these off-by-one errors and alike with tests.
• CodeYogi: @Ext3h I agree I was just replying on your comment that only console log would not work and I feel to strongly disagree now, either its interview or some quick code we don't get that liberty to using any test framework or even assert either. Having said that yes I agree that I need to learn these edge cases as you described.

Answer 2

Sorry but I really have to say this: Your implementation is far from being desirable.

Let's see what is wrong with it.

• It does not follow the specification:

output "Success" (without the quotes)

You are returning true instead of Success. You can leave a comment explaining that in your opinion return true would be a better option, but nonetheless the job of a algorithm is to follow a specification.

• The implementation is not correct

The algorithm fails with the following input hashBalancedParanthesis('{}[]{');. It returns 1 instead of 5. Many other examples like this could be found.

• You could have avoided both the bug and the O(n) indexOf

string.indexOf(char) + 1;

You wanted to return i + 1 here.

• Bruno Costa: @greybeard Does it?
• ilkkachu: So how do you deal with nested parenthesis on the way out of the middle? say, how, exactly, would your algorithm check the string [({}{})something] ?
• ilkkachu: Also, you found one bug with a simple fix, and one trivial implementation detail (the fact that the main program printing the "Success" string isn't shown) and that's "far from being desirable"?
• ilkkachu: @BrunoCosta, I'm pretty sure that to check all the pairs of parenthesis, a stack is needed (to remember the order the different types of parens come up). I can't prove that formally, but there's a couple of questions on balanced parens under shown as "Related", all of them use a stack, so it doesn't seem that clear it can be done without. You stated first "can be made without memory footprint", but now it's "you guess"? That's not very convincing. (To me, it's less convincing than an almost working code with a single bug, but YMMV.)
• njzk2: also, it crashes on ")"