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. 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
The next Codility challenge I will be covering is the IsPermutation challenge in chapter 2. The question can be seen in the gist below:
The question asks us to return 1 if an inputted array is a permutation, or 0 if it is not a permutation. As we know, a permutation is an array of elements containing all elements from 1..n, once and only once. Using that, we know that an array will fail any tests if an element is less than 0, or greater than the lengths of the array. We also know that if an element appears more than once, it is not a permutation. A good solution to checking if an element has already been encountered is to use a counter. Either a boolean or an integer counter would be appropriate, as long as it is possible to determine if an element has been checked before. My solution can be found below, I scored 100% correctness and 100% performance:
As always, check out the Git for this problem.
This is the first solution I will be providing for chapter 2 on the Codility site. Te second chapter is about counting elements. The reading material is very interesting, if a bit short, and perhaps unclear. It took me a couple of read throughs, it briefly discusses methods of storing numerical data in arrays. Within the first couple of paragraphs, I was already surprised to discover a counter array; storing the occurrence of a number within an array. Using this method, you can store the same amount of data, in much less storage space.
Back to the challenge though. The question itself can be found here:
The question says, find the minimum missing positive Integer from within the array. The array may not be sorted and elements may appear multiple times. Checkout my solution to the problem below, this achieved 100% performance and 100% correctness. However, I am guilty of going back and changing my result due to using counter.length + 1, instead of counter.length at a point in my code. Unfortunately, this caused a index out of bounds error, giving me only 60% performance, initially.
Also, check out my Git repository with the solution in.
The second question within the chapter covering Time Complexity on Codility asks you to find a missing element within an Array. The question is below:
Each element within the Array is unique and within the range 1…n+1, however a single element is missing. The Array is initially unordered. The result of the method should return the missing element. The problem is simple to solve; reorder the array and iterate through until a number is found missing from it. When it is found, return the value. There are a couple of cases that can mean no further processing will be necessary:
- The Array is empty – Return 1, the missing element should be between 1…n+1, or in this instance between 1..0+1->1…1. (This can happen before sorting the array.)
- The first element in the array is not 1. Return 1. (Must happen after sorting the Array)
- The last element of the array is not n+1. Return Array Length + 1. (Must happen after sorting)
Now you have read the brief explanation above, check out my solution below:
Also, check out the Git Repository.
Since writing this blog post, I have just searched up how other people resolved this issue, and whilst I got 100% on both score and functionality, I was way off the best solution. Going back to my solution for the first puzzle. The key is to calculate the expected element length for the number of elements, then subtract each element of the array, this gives you the remaining element. Here is a link to the Stack Exchange answer where I found the answer. I can’t believe I didn’t think of that.
The Frog Jump challenge is the third challenge within Codility’s first chapter on time complexity. This challenge is pretty simple, the question is as follows:
The question simply says, how many jumps of D length will it take for the frog to cover at least distance between Y and X. The key part to take away from the question is that the distance covered won’t be exact; the distance covered by the number of jumps has to be greater than or equal to the distance.
Below is my solution to the issue; it scored 100% on accuracy and on performance.
I made a Git repository for the code on my GitHub, check it out here.
Codility is a great site for learning, and testing your knowledge regarding some complex programming theories. Whilst the site contains many challenges, but there is a helpful section called lessons. Each lesson covers a topic and provides challenges for you to test your knowledge on.
The first of the chapter within the Codility is about Time Complexity. The first challenege within this section is named TapeEquilibrium, with it’s short description being: Minimize the value |(A + … + A[P-1]) – (A[P] + … + A[N-1])|. Huh. Let’s take a look at the problem and the final solution for it. The description of the issue is below:
The question is simple, an Array, A, with N elements is passed into a method. Loop through each element of the Array from A … A[n-1] each time calculating the difference between the sums of each side of the current key in the array.
The question tells us that the worst case time complexity should be O(n). We know that this is linear time, but it will likely end if a certain condition is reached.
Below I have put my final solution into a GIST. Using this, I achieved 100% correctness and 100% on performance.
I made a Git repository for the code on my GitHub, check it out here.