Solution to Brackets by codility

22 Jan

Question: http://codility.com/demo/take-sample-test/brackets

Question Name: Brackets

Classic application of stacks.

UPDATE (2016-07-19): Much appreciate Jeffrey’s comment and suggestion:

I’m surprised so few people didn’t do a simple modulo at the start to check whether there is an even number of chars. In production, you wouldn’t want this algorithm to run against a big string and only terminate at the end when one closing token is missing. You’d want it to terminate as soon as it’s possible

26 Replies to “Solution to Brackets by codility

  1. Ruby Version

  2. C# Solution.

  3. I don’t know if you’ve tested this in a IDE, but this is the correct C# solution 100%:

      • Above code had compilation errors even algorithm is correct but does not compile correctly. I will suggest the code below:

        See the results for this over the codility:
        https://codility.com/demo/results/demo4KD3BK-X89/

        • Interestingly, in C#, if you use generic

          to avoid all “.ToString()”s same code will fail on codility.com by performance – shows only 40%. Changing it back to

          gives 100%.

  4. I was talking about Kaiser’s solution. Apparently “<pre>” tag somehow formatted my Dictionary<string,string> VS 2013 won’t recognize Dictionary as a Generic Collection

  5. This works same as a stack and it is a bit shorter (still O(n)):

    • Good idea. Actually you are doing a stack by your self.
      For the other readers with other programming languages, please notice that the top pointer might be negative value. For example, the test input might be “)))”.

  6. Here’s a Java 100/100 Solution:
    https://codility.com/demo/results/demo97TPVG-CPP/

  7. A C# solution:

  8. I’m surprised so few people didn’t do a simple modulo at the start to check whether there is an even number of chars. In production, you wouldn’t want this algorithm to run against a big string and only terminate at the end when one closing token is missing. You’d want it to terminate as soon as it’s possible

  9. Py:

  10. Swift solution 100%

  11. Completely uneccessary solution using numbers. Python solution – O(N).

  12. Thanks for this blog post! I was banging my head against the wall thinking this is a simple / short solution, where you just build a stack and scan each item popped for validity.
    Your solution is way more elegant than mine but I set out not to use anything as complex as a dictionary.

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!