Brackets equality problem

brackets

I didn’t know how to name this , that’s why I named it as it’s written in the post title. This is a  from another coding test on one of these coding challenge platforms. I still think that these platforms are just an automation of this weird “whiteboard coding” process. And it’s a pity that companies still believe that such tests could indicate really good programmers. Probably I would write a post with my thoughts on this topic later…

Description

The problem is to find a position in a string, where left part of a string and right part will contain the same number of open in the left and close in the right parts.
For example, this string “(())))(” should output 4. because in position 4 (counting from 0) we have two parts, “(())” and “))(“, and between this two parts, we have the same number of open and close brackets. For the same reason an output for a string “()())(())(()()(” is 7.

 

In the beginning, I would like to provide two links on a codility learning exercises solutions. They are placed in the same repository with all learning solutions in PHP. They solve other problems with brackets but could help to choose optimal ways to work with string and brackets.

  1. https://github.com/paljinov/php-codility/blob/e4d2ee85e872ddc18d6ab2834c89ce7664e5a193/Lesson%2007%20-%20Stacks%20and%20Queues/Nesting.php
  2. https://github.com/paljinov/php-codility/blob/e4d2ee85e872ddc18d6ab2834c89ce7664e5a193/Lesson%2007%20-%20Stacks%20and%20Queues/Brackets.php

And now I will publish a solution which I created during a test.

It works. But the problem here is a performance. Too many iterations could be done in calcClose and calcOpen methods. Just imagine a string of 20000 brackets inside. And a solution for such string could be 8470.

 

Better performance solution

After a test when I had a free time I decided to optimize my solution. We need to avoid these iterations through arrays of brackets somehow. And I found built in PHP function which counts a number of character was used in a string. The code is:

The second solution code looks smaller. 40 and 41 is a code of open and close brackets respectively. And the most interesting part here is a performance . How much faster could solution become if we would just move iterations with a C build in function? Let’s see.

There is almost no difference with small strings and with string without a solution.

The same amount of memory was allocated and execution timings are miserable. (0,000)

But the test on a really big string shows a difference. On an 1854 chars string with an answer equals to 847, the difference is:

This is what counted by these test platforms and leads to 66% vs 100% solutions.

 

Conclusion

Probably the second one solution could lead to 100% score in the test. The first one gave me only 66%. But in Russia, we have a phrase which literally could be translated as “After a fight, they do not wave their fists”. It means, that it’s too late to do something when the fight is over and you are loose. :) Only one thing that left is an experience. And to share these experience is one of the purposes of this post. I hope it could help somebody.