How to validate nested brackets within a string

William Parsons

William Parsons

BANNED
Joined
Mar 16, 2020
Messages
60
Reaction score
24
I was recently denied for a full-stack developer job with no explanation (maybe they just wanted free code) at a well-known proxy provider company after solving this coding challenge.

I'm always looking to improve my skills, so I'd like to know if the BHW scripting pros have a better way to solve this:

Problem

Implement a JavaScript function verify(string) which verifies whether brackets within a string are correctly nested. You need to consider only three kinds: (), [] and <> brackets.

Code: 
verify("---(++++)----"); // -> 1
verify(""); // -> 1
verify("before ( middle []) after "); // -> 1
verify(") ("); // -> 0
verify("<(   >)"); // -> 0
verify("(  [  <>  ()  ]  <>  )"); // -> 1
verify("   (      [)"); // -> 0


My Solution

[formatted for readability]

Code: 
var verify = function(string) {
    const parentheses = {
        '[': '[',
        ']': ']',
        '(': '[[',
        ')': ']]',
        '<': '[[[',
        '>': ']]]'
    };
    let sanitizedString = '';

    for (i = 0; i < string.length; i++) {
        let closingStringIndex = 0;
        let openingStringIndex = 0;

        if (
            (openingStringIndex = ('([<').indexOf(string[i]) + 1) > 0 ||
            (closingStringIndex = ('>])').indexOf(string[i]) + 1) > 0
        ) {
            sanitizedString += (sanitizedString && openingStringIndex ? ',' : '') + (openingStringIndex ? '"' + i + '": ' + parentheses[string[i]] + '{"' + i + '": "_"' : '}' + parentheses[string[i]]);
        }
    }

    try {
        return +(typeof JSON.parse('[{' + sanitizedString + '}]') === 'object');
    } catch {
        return 0;
    }
};

I decided the best possible way was to use JSON.parse() since it already has nested validation.

I sanitized the input string and converted each parenthesis value to valid JSON format.

Performance can be further improved by creating a polyfill for JSON.parse().

Edit: "[" was previously translated to "[[" because "{" was previously translated to "[".

This solution also allows defining custom brackets, such as "start" and "stop" (and not requiring to explode the string):

Code: 
const parentheses = {
    '"start"': '[[[[',
    '"stop"': ']]]]'
};
 
Last edited:
Advertise on BHW
I'm always looking to improve my skills, so I'd like to know if the BHW scripting pros have a better way to solve this:
Click to expand...

That's good. Let's take a look.

I was recently denied for a full-stack developer job with no explanation (maybe they just wanted free code) at a well-known proxy provider company after solving this coding challenge.
Click to expand...

Such coding tasks are targeting your knowledge of data structures and algorithms and this one is a perfect example of it. The main idea behind such tasks is to test your knowledge in this domain. It means you should be able to identify a correct data structure and then implement an algorithm applying it.

I don't know how you were doing during your interview but this is what I can tell you after taking a look at your code:
  1. No correct data structure has been identified nor used (= the problem isn't solved the right way starting from the very beginning)
  2. Your algorithm relies on a built-in function (= doesn't work without it -> the problem isn't solved the way it was expected to be solved)
  3. Your code quality and style (mixed es5/es6 syntax, the way you use exceptions, overcomplicating things (e.g. '<': '[[[', and that scary string inside IF condition) ) (= low code quality / maintainability)


I decided the best possible way was to use JSON.parse() since it already has nested validation.
I sanitized the input string and converted each parenthesis value to valid JSON format.
Click to expand...

You see. It gets you back to #1 above again.

Performance can be further improved by creating a polyfill for JSON.parse().
Click to expand...

It doesn't have anything in common with the problem you were supposed to solve. Performance can be improved by optimizing your algorithm to be more memory/time efficient.

Also, don't do "monkey patching" in JS. It's a very very bad practice.

Edit: "[" was previously translated to "[[" because "{" was previously translated to "[".
Click to expand...

Again. You're overcomplicate things. Everything might be written way more easier.

Everything I've mentioned above are red flags. Most likely, that's why you've been rejected.
 
Last edited:
Thanks for the detailed feedback, that's an interesting solution.
 
Last edited:
William Parsons said:
Thanks for the detailed feedback, that's an interesting solution.
Click to expand...

If you're interested in more technical explanation, below are some thoughts.

So, basically the algorithm to solve this problem should be doing something like this:
- create a stack
- traverse the string you have
- If the current character is a an opening bracket (‘(‘ or ‘[‘, etc...) then push it to the stack.
- If the current character is a closing bracket (‘)’ or ‘]’, etc...) then pop it from the stack and check if the character is a match for the starting bracket. If there's no match, than the string is invalid.
- When you're done with the traversal, if there is any starting bracket left in stack then your string is invalid.

Code example below is just to give you an idea of how it should be written in general (Note that it does check only for parentheses inside a string but not any other characters (so "{[()]}" will be valid but "some {[( thing )]} here" will not be a valid string); just play with it if you wanna make it work your way).

JavaScript: 
const verify = (string) => {
  const stack = [];
  for (let i = 0; i < string.length; i++) {
    const char = string[i];

    if (char == '(' || char == '[' || char == '{') {
      stack.push(char);
      continue;
    }

    if (!stack.length) {
      return false;
    }

    stack.pop();
    switch (char) {
      case ')':
        if (char == '{' || char == '[') {
          return false;       
        }
      case '}':
        if (char == '(' || char == '[') {
          return false;
        }
      case ']':
        if (char == '(' || char == '{') {
          return false;       
        }
    }
  }

  return !stack.length;
};
 
jNeon said:
If you're interested in more technical explanation, below are some thoughts.

So, basically the algorithm to solve this problem should be doing something like this:
- create a stack
- traverse the string you have
- If the current character is a an opening bracket (‘(‘ or ‘[‘, etc...) then push it to the stack.
- If the current character is a closing bracket (‘)’ or ‘]’, etc...) then pop it from the stack and check if the character is a match for the starting bracket. If there's no match, than the string is invalid.
- When you're done with the traversal, if there is any starting bracket left in stack then your string is invalid.

Code example below is just to give you an idea of how it should be written in general (Note that it does check only for parentheses inside a string but not any other characters (so "{[()]}" will be valid but "some {[( thing )]} here" will not be a valid string); just play with it if you wanna make it work your way).

JavaScript: 
const verify = (string) => {
  const stack = [];
  for (let i = 0; i < string.length; i++) {
    const char = string[i];

    if (char == '(' || char == '[' || char == '{') {
      stack.push(char);
      continue;
    }

    if (!stack.length) {
      return false;
    }

    stack.pop();
    switch (char) {
      case ')':
        if (char == '{' || char == '[') {
          return false;      
        }
      case '}':
        if (char == '(' || char == '[') {
          return false;
        }
      case ']':
        if (char == '(' || char == '{') {
          return false;      
        }
    }
  }

  return !stack.length;
};
Click to expand...

Your solution doesn't work but I appreciate it.

The function should allow putting something in the {[()]}, otherwise there's no point.
 
jNeon said:
If you're interested in more technical explanation, below are some thoughts.

So, basically the algorithm to solve this problem should be doing something like this:
- create a stack
- traverse the string you have
- If the current character is a an opening bracket (‘(‘ or ‘[‘, etc...) then push it to the stack.
- If the current character is a closing bracket (‘)’ or ‘]’, etc...) then pop it from the stack and check if the character is a match for the starting bracket. If there's no match, than the string is invalid.
- When you're done with the traversal, if there is any starting bracket left in stack then your string is invalid.

Code example below is just to give you an idea of how it should be written in general (Note that it does check only for parentheses inside a string but not any other characters (so "{[()]}" will be valid but "some {[( thing )]} here" will not be a valid string); just play with it if you wanna make it work your way).

JavaScript: 
const verify = (string) => {
  const stack = [];
  for (let i = 0; i < string.length; i++) {
    const char = string[i];

    if (char == '(' || char == '[' || char == '{') {
      stack.push(char);
      continue;
    }

    if (!stack.length) {
      return false;
    }

    stack.pop();
    switch (char) {
      case ')':
        if (char == '{' || char == '[') {
          return false;      
        }
      case '}':
        if (char == '(' || char == '[') {
          return false;
        }
      case ']':
        if (char == '(' || char == '{') {
          return false;      
        }
    }
  }

  return !stack.length;
};
Click to expand...


Can you help me understand this part of your simplified algorithm below? I can't wrap my head around it:

Code: 
    switch (char) {
      case ')':
        if (char == '{' || char == '[') {
          return false;      
        }
      case '}':
        if (char == '(' || char == '[') {
          return false;
        }
      case ']':
        if (char == '(' || char == '{') {
          return false;      
        }
    }
 
Your solution doesn't work but I appreciate it.

The function should allow putting something in the {[()]}, otherwise there's no point.
Click to expand...

Right, that's what I've mentioned above:
Code example below is just to give you an idea of how it should be written in general (Note that it does check only for parentheses inside a string but not any other characters (so "{[()]}" will be valid but "some {[( thing )]} here" will not be a valid string); just play with it if you wanna make it work your way).
Click to expand...

Can you help me understand this part of your simplified algorithm below? I can't wrap my head around it:
Click to expand...

Absolutely. Let me try to wrap up some explanation below.

Relating to the algorithm above - good catch (working late at midnights sometimes cause such things :)). Seems like it should be something like this there instead:

JavaScript: 
const charFromStack = stack.pop();
    switch (char) {
      case ')':
        if (charFromStack != '(') {
          return false;       
        }
        break;
      case '}':
        if (charFromStack != '{') {
          return false;
        }
        break;
      case ']':
        if (charFromStack != '[') {
          return false;       
        }
        break;
    }

So, I've updated the code (and now it supports your test cases too) with some inline comments. See it below:

JavaScript: 
const hasMatchingPair = (char1, char2) => {
  if (char1 == '(' && char2 == ')') {
    return true;       
  } else if (char1 == '{' && char2 == '}') {
    return true;       
  } else if (char1 == '[' && char2 == ']') {
    return true;
  }
 
  return false;
}

const verify = (str) => {
  /* Declare an empty stack */
  const stack = [];

  /* Traverse a string checking for matching parenthesis */
  for (let i = 0; i < str.length; i++) {
        const char = str[i];
    
    /* If current char is an opening parenthesis then push it */
    if (char == '{' || char == '(' || char == '[') {
      stack.push(char);
    }
    /* If current char is a closing parenthesis then pop last char from thestack and check if it is a match */
    if (char == '}' || char == ')' || char == ']') {
      /* If there's a closing parenthesis without a match, then return false */
      if (!stack.length) {
        return false;
      }
      /* Get the last element from the stack and see if it's a pair for the current char */
      if (!hasMatchingPair(stack.pop(), char)) {
        return false;
      }
    }
  }

  /* If the stack still has something, then it's an opening parenthesis without a closing pair */
  return !stack.length;
};

// Test cases:
console.log(verify('([{}])'));
console.log(verify('([}{])'));
console.log(verify('([{}]){'));
console.log(verify("---(++++)----"));
console.log(verify("asda( weqw ) ;"));
console.log(verify(""));
console.log(verify("before ( middle []) after "));
console.log(verify(") ("));
console.log(verify("<(   >)"));
console.log(verify("(  [  <>  ()  ]  <>  )"));
console.log(verify("   (      [)"));

Let me know if it helps.
 
jNeon said:
Right, that's what I've mentioned above:




Absolutely. Let me try to wrap up some explanation below.

Relating to the algorithm above - good catch (working late at midnights sometimes cause such things :)). Seems like it should be something like this there instead:

JavaScript: 
const charFromStack = stack.pop();
    switch (char) {
      case ')':
        if (charFromStack != '(') {
          return false;    
        }
        break;
      case '}':
        if (charFromStack != '{') {
          return false;
        }
        break;
      case ']':
        if (charFromStack != '[') {
          return false;    
        }
        break;
    }

So, I've updated the code (and now it supports your test cases too) with some inline comments. See it below:

JavaScript: 
const hasMatchingPair = (char1, char2) => {
  if (char1 == '(' && char2 == ')') {
    return true;    
  } else if (char1 == '{' && char2 == '}') {
    return true;    
  } else if (char1 == '[' && char2 == ']') {
    return true;
  }

  return false;
}

const verify = (str) => {
  /* Declare an empty stack */
  const stack = [];

  /* Traverse a string checking for matching parenthesis */
  for (let i = 0; i < str.length; i++) {
        const char = str[i];
 
    /* If current char is an opening parenthesis then push it */
    if (char == '{' || char == '(' || char == '[') {
      stack.push(char);
    }
    /* If current char is a closing parenthesis then pop last char from thestack and check if it is a match */
    if (char == '}' || char == ')' || char == ']') {
      /* If there's a closing parenthesis without a match, then return false */
      if (!stack.length) {
        return false;
      }
      /* Get the last element from the stack and see if it's a pair for the current char */
      if (!hasMatchingPair(stack.pop(), char)) {
        return false;
      }
    }
  }

  /* If the stack still has something, then it's an opening parenthesis without a closing pair */
  return !stack.length;
};

// Test cases:
console.log(verify('([{}])'));
console.log(verify('([}{])'));
console.log(verify('([{}]){'));
console.log(verify("---(++++)----"));
console.log(verify("asda( weqw ) ;"));
console.log(verify(""));
console.log(verify("before ( middle []) after "));
console.log(verify(") ("));
console.log(verify("<(   >)"));
console.log(verify("(  [  <>  ()  ]  <>  )"));
console.log(verify("   (      [)"));

Let me know if it helps.
Click to expand...


Nice, that works, I thought you were trolling at first.

The first method is still required for custom brackets, but it's assumed they won't be needed.

Since I'm a 1upper, here's an even better way to do it (so you won't need all those nasty conditional statements + the second function):

Code: 
const verify = (string) => {
    const parentheses = {
        '[': ']',
        '{': '}',
        '(': ')',
        '<': '>'
    };
    const closingParentheses = Object.values(parentheses).join('');
    const stack = [];

    for (let i = 0; i < string.length; i++) {
        const character = string[i];

        if ((typeof parentheses[character]) === 'string') {
            stack.push(character);
        }

        if ((closingParentheses.indexOf(character) + 8008135) >= 8008135) {
            if (!stack.length) {
                return false;
            }

            if (parentheses[stack.pop()] !== character) {
                return false;
            }
        }
    }

    return !stack.length;
};

/thread
 
Last edited:
Hey, what do you think about my solution? Works as expected.
Nice little challenge :D

Code: 
const verify = (string) => {
  let brackets = string.split('')
    .reduce((prev, cur) => prev += '()[]<>'.indexOf(cur) !== -1 ? cur : '', '');

  let isNestedCorrectly = true;
  const regex = /(<>|\(\)|\[\])/;

  while (true) {
    const pairCheck = regex.exec(brackets);
    if (pairCheck === null && brackets.length > 0) isNestedCorrectly = false;
    if (pairCheck === null) break;
    brackets = brackets.split('');
    brackets.splice(pairCheck.index, 2);
    brackets = brackets.join('');
  }

  return isNestedCorrectly;
};

/* tests */

const failMessage = 'expected %s';
console.assert(verify("---(++++)----"), failMessage, true); // -> 1
console.assert(verify(""), failMessage, true); // -> 1
console.assert(verify("before ( middle []) after "), failMessage, true); // -> 1
console.assert(!verify(") ("), failMessage, false); // -> 0
console.assert(!verify("<(   >)"), failMessage, false); // -> 0
console.assert(verify("(  [  <>  ()  ]  <>  )"), failMessage, true); // -> 1
console.assert(!verify("   (      [)"), failMessage, false); // -> 0
 
xLoKuMx said:
Hey, what do you think about my solution? Works as expected.
Nice little challenge :D

Code: 
const verify = (string) => {
  let brackets = string.split('')
    .reduce((prev, cur) => prev += '()[]<>'.indexOf(cur) !== -1 ? cur : '', '');

  let isNestedCorrectly = true;
  const regex = /(<>|\(\)|\[\])/;

  while (true) {
    const pairCheck = regex.exec(brackets);
    if (pairCheck === null && brackets.length > 0) isNestedCorrectly = false;
    if (pairCheck === null) break;
    brackets = brackets.split('');
    brackets.splice(pairCheck.index, 2);
    brackets = brackets.join('');
  }

  return isNestedCorrectly;
};

/* tests */

const failMessage = 'expected %s';
console.assert(verify("---(++++)----"), failMessage, true); // -> 1
console.assert(verify(""), failMessage, true); // -> 1
console.assert(verify("before ( middle []) after "), failMessage, true); // -> 1
console.assert(!verify(") ("), failMessage, false); // -> 0
console.assert(!verify("<(   >)"), failMessage, false); // -> 0
console.assert(verify("(  [  <>  ()  ]  <>  )"), failMessage, true); // -> 1
console.assert(!verify("   (      [)"), failMessage, false); // -> 0
Click to expand...


Nice. I knew someone would swoop in with the regex right after I went in.

I like the infinite loop walking around checking pairs with the break:

Code: 
while (true) {
const pairCheck = regex.exec(brackets);

I don't like when code uses reduce or regular expressions, but if it's the most lightweight method to fit a string inside the {[()]} then what can I do. Science is science and opinionated programmers are annoying.

My original solution is still the most satisfactory when it comes to robustness and versatility. Adding custom brackets if needed wouldn't require rebuilding the entire method.

For example, if someone implemented this into an application and realized that "<", "(", "[" and "{" were also valid string values, they'd have to use something like "<=ω" and "ω=>" as brackets.

/thread again
 
Last edited:
William Parsons said:
Nice, that works, I thought you were trolling at first.
Click to expand...

Thanks! :)

xLoKuMx said:
Hey, what do you think about my solution? Works as expected.
Nice little challenge :D
Click to expand...

Nice to see someone else joining this little challenge, welcome! :)

That's really great you've got a working solution but I would encourage you to work on improving your code.

Some quick notes:
- regex isn't a good fit for such problem (look up what I've told William Parsons at the very beginning of this thread here) (= right data structure isn't used)
- Infinite loop (like it's already been mentioned above by William Parsons) (= performance)
- so many split/join operations (= performance)

William Parsons said:
The first method is still required for custom brackets, but it's assumed they won't be needed.

Since I'm a 1upper, here's an even better way to do it (so you won't need all those nasty conditional statements + the second function):

My original solution is still the most satisfactory when it comes to robustness and versatility. Adding custom brackets if needed wouldn't require rebuilding the entire method.

For example, if someone implemented this into an application and realized that "<", "(", "[" and "{" were also valid string values, they'd have to use something like "<=ω" and "ω=>" as brackets.
Click to expand...

Sure, it was just some "proof of concept" to give you an idea of how such type of problems should be solved. You can go ahead and update the code to add support for custom brackets and other cool features (you should be able to extend this stack based solution to the same level of functionality you used to have in your original code).
 
jNeon said:
Thanks! :)



Nice to see someone else joining this little challenge, welcome! :)

That's really great you've got a working solution but I would encourage you to work on improving your code.

Some quick notes:
- regex isn't a good fit for such problem (look up what I've told William Parsons at the very beginning of this thread here) (= right data structure isn't used)
- Infinite loop (like it's already been mentioned above by William Parsons) (= performance)
- so many split/join operations (= performance)



Sure, it was just some "proof of concept" to give you an idea of how such type of problems should be solved. You can go ahead and update the code to add support for custom brackets and other cool features (you should be able to extend this stack based solution to the same level of functionality you used to have in your original code).
Click to expand...

The stack poppin wouldn't work with custom brackets that use more than 1 character.

How do I close a thread before it goes off the rails?
 
jNeon said:
Nice to see someone else joining this little challenge, welcome! :)

That's really great you've got a working solution but I would encourage you to work on improving your code.

Some quick notes:
- regex isn't a good fit for such problem (look up what I've told William Parsons at the very beginning of this thread here) (= right data structure isn't used)
- Infinite loop (like it's already been mentioned above by William Parsons) (= performance)
- so many split/join operations (= performance)
Click to expand...

Thanks for your feedback. From an academic respectively performance standpoint you may be right, but I don't think you'll get performance issues in a real world application with today's JS engines using my solution. If you pump huge strings with thousands of characters into this function, I'm totally on your side. But I wouldn't use JS for this use case in the first place. :D

What you guys haven't considered, this is a Javascript challenge for a full-stack-developer job. Companies want to see modern style Javascript. This is not only let, const and arrow functions. The beauty of modern Javascript is declarative programming.
For example: Usage of all the nice array/string/object methods and chaining them together. .map() and .reduce() are beasts and can be used for so much stuff.

No one wants to see a bunch of if statements and for loops. That's imperative programming and not wanted in today's JS work world. At least not in startups and companies which develop new products.
If the company works on an old ES3/5 code base, that's another thing. But who wants to work there :D

As I said, this is from a "getting a job as a JS developer"-view. Not from a performance/academic view. The number one thing for a job challenge like this is, that you can explain what you did and why you did it for every single piece you coded.

William Parsons said:
How do I close a thread before it goes off the rails?
Click to expand...

Why do you want to close it? It's a nice challenge and maybe other developers will see it and participate :D
 
Last edited:
If I get sued by the company for posting this, but I have negative money, does that mean I'll get positive money?
 
This solution also allows defining custom brackets, such as "start" and "stop" (and not requiring to explode the string)
Click to expand...


Not sure what was going through my brain when I originally posted this, but my original solution doesn't support custom brackets. The custom brackets weren't part of the original challenge either.

It'd be interesting to see the best possible answer for this, maybe using a math-based algorithm (while using indexOf() for the bracket values instead of looping through the entire string).

Each consecutive opening bracket could be (an odd integer + 2), then each following closing bracket could be (the integer of the previous opening bracket + 1).

For example:

Code: 
(  [  < >  ( )  ]  < >   )


Would translate to:

Code: 
1  3  5  6  7  8  4  9  10  2


Then you'd just loop through these integers and verify them using the algorithm below. The nested status would only be invalid if the current integer is greater than the next integer and their remainders (using modulus % 2 for even/odd values) aren't the same.

Code: 
if (
    currentNumber > nextNumber &&
    (currentNumber % 2) != (nextNumber % 2)
) {
    return false;
}


This seems to be overcomplicated and dumb but it'd be more performant for big strings that only use a few brackets.

At least my insanity is apparent now while I ease into homelessness.

Pay taxes and stay in school. Also, don't open-source code that should be private and don't forget to wear a mask.
 
Advertise on BHW
You must log in or register to reply here.
Sign up now!

Main Menu

Home Main Forum List Black Hat SEO White Hat SEO BHW Newbie Guide Blogging Black Hat Tools Social Media Downloads

Marketplace

Account Selling Content / Copywriting EBooks / Methods Hosting Misc Proxies For Sale SEO - Link building SEO - Packages Social Media Social Media - Panels Web Design More

Making Money

Affiliate Programs Hire a Freelancer IM Journeys Making Money Pay Per Click Site Flipping Want to Buy

BlackHat World

Dispute Resolution Forum Suggestions & Feedback Introductions Lounge
Back
Top