DEV Community

Valid parentheses, solving a Facebook interview question.

Akhil on June 27, 2020

This is one of the most commonly asked screeing questions, Especially if the interview is conducted by Hackerrank, there's a good chance that they ...

Read full post

Nam Hoang Le • Jun 27 '20 • Edited

You can check a number is not equal to zero by if (n) {} or check empty string by if (!s) ....
Of course, just use object literal for you map. :)

The last statement should be return !stack.length.

Bonus point: we can solve it shorter by using recursion and String replace method.

Akhil • Jun 27 '20

I wrote this way for code readability :)

Nam Hoang Le • Jun 27 '20 • Edited

Yes, that way is better for products. But the boundary between readability and cleaning is not always clear. :)

Akhil • Jun 27 '20

True that.

JS Bits Bill • Jun 27 '20

Also tried the standard for loop approach which actually proved easier to deal with than every:

const isValid = function(s) {

  const pairs = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

  const openParens = [];
  for (let i = 0; i < s.length; i++) {
    const endParen = pairs[s[i]];

    if (endParen) openParens.push(endParen);
    else if (openParens[openParens.length - 1] === s[i]) openParens.pop();
    else return false;
  } 

  return openParens.length ? false : true;
};

Akhil • Jun 28 '20

Awesome work man ! keep up !

Nam Hoang Le • Jun 28 '20

It’s me again. Here’s my solution.

function isValid(s) {
    const t = s.replace(/\(\)|\[\]|\{\}/g, "");
    return s == t ? !s : isValid(t);
};

Akhil • Jun 28 '20

Test it here: leetcode.com/problems/valid-parent...

As far as I know, the regex will manipulate string and string manipulation is a bit time consuming heavy in javascript.

But smart and concise code though !

Nam Hoang Le • Jun 28 '20 • Edited

It’s true. C/C++ can solve it in almost 0ms.

JS Bits Bill • Jun 27 '20 • Edited

I gave this a shot! Similar to yours, my approach was to split the string and track the expected closing parens in a separate array. I used the every method instead of a for...of loop which works nicely with the empty string case.

const isValid = function(str) {

  const pairs = {
    '(': ')',
    '[': ']',
    '{': '}'
  };

  const closingParens = [];
  return [...str].every(validate);

  function validate(char, i, arr) {
    const isLastChar = i === arr.length - 1;

    // If char found in pairs, push closing paren to arr
    if (pairs[char] && !isLastChar) {
      closingParens.push(pairs[char]);
      return true;

    } else {
      // If char has no closing paren, return false
      if (!closingParens.length) return false;

      // Check if current char is last in arr
      const lastCharInArray = closingParens.pop();

      // If last char and unmatched parens, return false
      if (isLastChar && closingParens.length) return false;

      // If pair found, continue
      if (char === lastCharInArray) return true;
    }
  }
};

What do you think?

Akhil • Jun 27 '20

For :"{[]}" it returns false.

Try solving it here : leetcode.com/problems/valid-parent...

JS Bits Bill • Jun 27 '20

@akhil I updated it to meet that condition!

vladflorescu94 • Mar 21 '21 • Edited

I conduct interviews (not at Facebook), I don't ask questions about algorithms, but I wouldn't probably hire someone who writes code like that, especially if it's a mid-senior position, because there are too many bad practices:

var shouldn't be used anymore;
variables should have more descriptive names and start with a lowercase character;
always ===, never ==;
static constants should be defined outside functions;
renturn stack.length === 0 is cleaner.

I wrote the implementation below and I find it much cleaner.

const CLOSING_BRACKET_BY_MATCH = {
  '(': ')',
  '[': ']',
  '{': '}',
};

const testBrackets = (input) => {
  const stack = [];
  let len = 0;

  if (input.length % 2 !== 0) {
    return false;
  }

  for (const character of input) {
    if ('([{'.indexOf(character) !== -1) {
      stack.push(character);
      len += 1;
    } else {
      const lastCharacterPushed = stack[len - 1];

      if (len === 0 || (CLOSING_BRACKET_BY_MATCH[lastCharacterPushed] !== character)) {
        return false;
      }

      stack.pop();
      len -= 1;
    }
  }

  return len === 0;
};

mayank joshi • Jun 27 '20

Amazing post. I loved the concept.🥳

Just one thing, try moving this from webdev to #algorithms tag for better reach among algo geeks.

Akhil • Jun 27 '20

My bad, it was meant to be #tutorial.

Thanks a lot for reading :)