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.

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.

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.