Today I finally decided to get back into working my way through the Codility lessons. I started off by getting stuck into Lesson 4 on sorting found here: https://codility.com/programmers/lessons/4. The first task is called MaxProductOfThree.
The challenge description is in the gist below:
The idea of the task is to find the highest value of any triplet in an array. A triple may be represented as (P, Q, R) where P is greater than or equal to 0, Q is greater than P and R is greater than R. P, Q and R are indexes of an array.
The input array may be unsorted and it will have a length of 3 to 100,000. Any value in the array will be between -1,000 and 1,000.
My first attempt at answering this question only got 44% correctness. I thought the answer would be super easy, below is my first, incorrect solution:
It took me a while to understand why this may not work and I had to cave in and took a look through Google to see where I was going wrong. I found a solution similar to below and I made some changes to improve performance by a tiny bit (every little helps):
What is happening here? It took me a little bit of time staring at this solution to completely understand what was happening below is a pseudocode example of what is going on:
Below is a visual example using a sample array:
Using my first answer to the question I would have found -15 (-5 * 1 * 3) to be the highest result from a triple in the this array.
Using my second answer the highest result from a triple would have been 165 (-11 * -5 * 3).
But why!? How could including two of the smallest numbers in the result create a higher result. The reason is simple. Two negatives make a positive. So the two lowest numbers, if both negative could create a larger positive number than any positive numbers in the array. Below is the result from cordiality with 100%: https://codility.com/demo/results/demoAYEMBX-C94/
The test was completed quickly because I wrote my answer in IntelliJ and copied it over once I has worked it out. Below is a repo with my answer for you to check out: https://github.com/jordanterry/MaxProductOfThree