I didn’t know how to name this problem, that’s why I named it as it’s written in the post title. This is a problem 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 brackets in the left and close brackets 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.
Solution
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.
- https://github.com/paljinov/php-codility/blob/e4d2ee85e872ddc18d6ab2834c89ce7664e5a193/Lesson%2007%20-%20Stacks%20and%20Queues/Nesting.php
- 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
function solution($S) { if (empty($S)) { return 0; } // write your code in PHP7.0 $brackets = str_split($S); $splitPoint = 1; do { $part1 = array_slice($brackets, 0, $splitPoint); $part2 = array_slice($brackets, $splitPoint, count($brackets) - $splitPoint); $openC = calcOpen($part1); $closeC = calcClose($part2); if ($openC != 0 && $closeC != 0 && $openC == $closeC) { return $splitPoint; } $splitPoint++; } while ($splitPoint < count($brackets)); return count($brackets); } function calcOpen($arr) { $sum = 0; foreach ($arr as $each) { if ($each == '(') { $sum += 1; } } return $sum; } function calcClose($arr) { $sum = 0; foreach ($arr as $each) { if ($each == ')') { $sum += 1; } } return $sum; } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
/** * FASTER !!! * * @param $S * @return int */ function solution2($S) { if (empty($S)) { return -1; } $splitPoint = 1; do { $part1 = substr($S, 0, $splitPoint); $part2 = substr($S, $splitPoint); $openC = calcOpen2($part1); $closeC = calcClose2($part2); if ($openC != 0 && $closeC != 0 && $openC == $closeC) { return $splitPoint; } $splitPoint++; } while ($splitPoint < strlen($S)); return -1; } function calcOpen2($part1) { $counts = count_chars($part1, 1); return isset($counts[40]) ? $counts[40] : 0; } function calcClose2($part2) { $counts = count_chars($part2, 1); return isset($counts[41]) ? $counts[41] : 0; } |
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 comparison. 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//379464 $start = (float)array_sum(explode(' ', microtime())); var_dump(solution2('(())))(')); $end = (float)array_sum(explode(' ', microtime())); print "Processing time: " . sprintf("%.4f", ($end - $start)) . " seconds." . PHP_EOL; echo memory_get_usage() . PHP_EOL; $start = (float)array_sum(explode(' ', microtime())); var_dump(solution2('()())(())(()()(')); $end = (float)array_sum(explode(' ', microtime())); print "Processing time: " . sprintf("%.4f", ($end - $start)) . " seconds." . PHP_EOL; echo memory_get_usage() . PHP_EOL; $start = (float)array_sum(explode(' ', microtime())); var_dump(solution2('))))(')); $end = (float)array_sum(explode(' ', microtime())); print "Processing time: " . sprintf("%.4f", ($end - $start)) . " seconds." . PHP_EOL; echo memory_get_usage() . PHP_EOL; //---- //379464 $start = (float)array_sum(explode(' ', microtime())); var_dump(solution('(())))(')); $end = (float)array_sum(explode(' ', microtime())); print "Processing time: " . sprintf("%.4f", ($end - $start)) . " seconds." . PHP_EOL; echo memory_get_usage() . PHP_EOL; $start = (float)array_sum(explode(' ', microtime())); var_dump(solution('()())(())(()()(')); $end = (float)array_sum(explode(' ', microtime())); print "Processing time: " . sprintf("%.4f", ($end - $start)) . " seconds." . PHP_EOL; echo memory_get_usage() . PHP_EOL; $start = (float)array_sum(explode(' ', microtime())); var_dump(solution('))))(')); $end = (float)array_sum(explode(' ', microtime())); print "Processing time: " . sprintf("%.4f", ($end - $start)) . " seconds." . PHP_EOL; echo memory_get_usage() . PHP_EOL; |
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:
|
1 2 3 4 5 6 7 |
solution 1 //0.1196 solution 2 //0.0045 - 0.0063 |
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.
