4 ms·

>hopefully none of your candidates need anywhere near 1/2 hour to code stuff that simple IDK, is it that simple for everyone in tech to finish it in way less t

>hopefully none of your candidates need anywhere near 1/2 hour to code stuff that simple IDK, is it that simple for everyone in tech to finish it in way less than 30 min? I think I would definitely need more than 30 min for the nested brackets validation problem and I've been in SW dev for 10 years and I'm about average in my area compared to everyone I know (non-faang/non-big-tech). The thing is, I haven't touched algorithmic riddles like that since I graduated university over 10 years ago, and none of my daily assignments at my coding jobs since, were ever anything close to that, and nor do interviews in my area (Europe) ever require those kinds of problems to be solved, so I would definitely need some time to warm up, grab a piece of paper, and think of a solution for that one. New-grad version of me who did a lot of algorithmics assignments, lab work and interview prep back in the days could definitely be faster, but this version of me who's head is filled with solving the issues assigned at work, not so much, and would need longer. When I apply to jobs in my area, most companies here just check if you have domain knowledge related to the problems you'd have to solve if you got the job. Coding riddles like that seems more of a US, big-tech, VC-unicorn kind of thing that's missing in the companies I applied at. I wouldn't mind such riddles as an interview, but I definitely would fail them if they were strictly timeboxed. I guess I'm not employee material for his company.

jon-wood 4y ago
I bet you wouldn’t, it’s not something I’ve come across before, but having seen it now I’m absolutely stealing it because it has the wonderful property of seeming complex on the surface and actually being incredibly simple.
chihuahua 4y ago
The balanced bracket problem is one step above FizzBuzz.
- ChuckNorris89 4y ago
  I had no idea what fizzbuzz is without googling it. I think HN is some bubble I'm not part of.
sokoloff 4y ago
Do you have a language that allows you to easily create a stack? Push open brackets onto the stack, when you get a closing bracket, pop the stack and make sure it's the "right" one. When the input is exhausted, if the stack is empty, the input was balanced.
- tzs 4y ago
  Since the only thing you are pushing onto the stack are open brackets you don't actually need the stack. Just keep a count of how many brackets would have been on the stack. Increment the count when you see an open bracket. Decrement the count when you see a close bracket. If the count every goes negative there was a mismatch. If the count does not end up at 0 when you've processed all the brackets there was a mismatch. It can also be treated as a text transformation problem. Every non-empty string of matched brackets must contain at least one '()', and deleting a '()' from a string does not change whether or not the string is balanced. That gives an approach of repeatedly finding and deleting '()' from the string until there are no more '()'s to delete. If that gives you an empty string the original string was all matched. If the final string is not empty then the original string had a mismatch. Here's that as a shell script. #!/bin/sh S=`echo $1 | tr -c -d '()'` P=x while [ "$S" ]; do if [ "$S" = "$P" ]; then echo "Mismatch" exit 1 fi P=$S S=`echo $S | sed -e 's/()//g'` done echo "All match" exit 0
  - sokoloff 4y ago
    It depends on the problem definition (specifically on the definition of the word "brackets"). If you want to ensure the proper balancing of all of {}, [], and () [while excluding improper nesting], you need a stack [or equivalent]. If you only want to ensure () balancing, you can just do a count. IMO: ({[]}) // has balanced brackets ({[}]) // has imbalanced brackets
bell-cot 4y ago
If - guessing from the given example - the brackets problem only involves a single type of bracket, then the solution is micro-sized: OpenCount = 0 until( Exhausted( input ) ) { if( NextChar( input ) == '(' ) OpenCount++ if( NextChar( input ) == ')' ) OpenCount-- if( OpenCount < 0 ) ERROR( "Negative Nesting Level in Input" ) IncrementPointer( input ) } if( OpenCount != 0 ) ERROR( OpenCount." Unclosed Nesting Level(s) in Input" ) Print( "Nesting okay in Input" ) It took me <10 seconds to think up that algorithm, and I haven't written parsing code (that cared about such things) in years.
- ChuckNorris89 4y ago
  I think your algo just checks if there are exact number of open and closed brackets, but it doesn't check that they actually match together in a valid way.
  - bell-cot 4y ago
    Do you mean input such as ")(" or "())("? (If so, that would trigger the "Negative Nesting Level" error.)
- monksy 4y ago
  https://scastie.scala-lang.org/monksy/oHy8eviuTYeHCj0B8qSCJw/21 https://scastie.scala-lang.org/monksy/oHy8eviuTYeHCj0B8qSCJw... Could be improved as a collect.. but that was a first pass. [Did take some go overs to fix a few typos]

jon-wood 4y ago

I bet you wouldn’t, it’s not something I’ve come across before, but having seen it now I’m absolutely stealing it because it has the wonderful property of seeming complex on the surface and actually being incredibly simple.

chihuahua 4y ago

The balanced bracket problem is one step above FizzBuzz.

ChuckNorris89 4y ago
I had no idea what fizzbuzz is without googling it. I think HN is some bubble I'm not part of.

sokoloff 4y ago

Do you have a language that allows you to easily create a stack? Push open brackets onto the stack, when you get a closing bracket, pop the stack and make sure it's the "right" one. When the input is exhausted, if the stack is empty, the input was balanced.

tzs 4y ago
Since the only thing you are pushing onto the stack are open brackets you don't actually need the stack. Just keep a count of how many brackets would have been on the stack. Increment the count when you see an open bracket. Decrement the count when you see a close bracket. If the count every goes negative there was a mismatch. If the count does not end up at 0 when you've processed all the brackets there was a mismatch. It can also be treated as a text transformation problem. Every non-empty string of matched brackets must contain at least one '()', and deleting a '()' from a string does not change whether or not the string is balanced. That gives an approach of repeatedly finding and deleting '()' from the string until there are no more '()'s to delete. If that gives you an empty string the original string was all matched. If the final string is not empty then the original string had a mismatch. Here's that as a shell script. #!/bin/sh S=`echo $1 | tr -c -d '()'` P=x while [ "$S" ]; do if [ "$S" = "$P" ]; then echo "Mismatch" exit 1 fi P=$S S=`echo $S | sed -e 's/()//g'` done echo "All match" exit 0
- sokoloff 4y ago
  It depends on the problem definition (specifically on the definition of the word "brackets"). If you want to ensure the proper balancing of all of {}, [], and () [while excluding improper nesting], you need a stack [or equivalent]. If you only want to ensure () balancing, you can just do a count. IMO: ({[]}) // has balanced brackets ({[}]) // has imbalanced brackets

bell-cot 4y ago

If - guessing from the given example - the brackets problem only involves a single type of bracket, then the solution is micro-sized: OpenCount = 0 until( Exhausted( input ) ) { if( NextChar( input ) == '(' ) OpenCount++ if( NextChar( input ) == ')' ) OpenCount-- if( OpenCount < 0 ) ERROR( "Negative Nesting Level in Input" ) IncrementPointer( input ) } if( OpenCount != 0 ) ERROR( OpenCount." Unclosed Nesting Level(s) in Input" ) Print( "Nesting okay in Input" ) It took me <10 seconds to think up that algorithm, and I haven't written parsing code (that cared about such things) in years.

ChuckNorris89 4y ago
I think your algo just checks if there are exact number of open and closed brackets, but it doesn't check that they actually match together in a valid way.
- bell-cot 4y ago
  Do you mean input such as ")(" or "())("? (If so, that would trigger the "Negative Nesting Level" error.)
monksy 4y ago
https://scastie.scala-lang.org/monksy/oHy8eviuTYeHCj0B8qSCJw/21 https://scastie.scala-lang.org/monksy/oHy8eviuTYeHCj0B8qSCJw... Could be improved as a collect.. but that was a first pass. [Did take some go overs to fix a few typos]