So I was recently introduced to the service Codility which provides programming challenges for people looking for a job in the industry. I’m not looking for a job, but I do like interesting programming challenges, so I thought I’d try it out.
Apparently, once a month they release a new algorithmic problem to solve and test your solution for correctness and good time complexity. You can get a “silver” award if your program is correct and a “gold” award if it also has good time complexity. They give you a time limit of 2 hours, but I’ve figured out first hand that you can simply retake the test as many times as you like.
After three tries I got my shiny gold medal. My first attempt was almost completely correct if it wasn’t for a very small edge case that they specified in the problem. I only had to change one line of code to make it correct.
Anyway, in short the problem statement is to find the number of ranges within an array where the Max(range) - Min(range) <= K.
I’m not sure If I’m allowed to post my solution online - so I’m sorry if this is bad form…
#include <set>
#include <vector>
using namespace std;
// Target space complexity: O(n) Actual O(n)
// Target time complexity: O(n) Actual O(nlogn) due to multiset
int solution( int K, vector<int> &A )
{
int left = 0;
int right = 0;
int count = 0;
multiset<int> values;
// Prime our sorted range with the first value
values.insert( A[0] );
// Stop once our left edge has exceeded the input values
while( left < A.size() )
{
// While the range we are looking at is a legal span,
// try to increase our right edge
while( values.empty() || *values.rbegin() - *values.begin() <= K )
{
// Don't increase it if we're at the right edge of the input
if( right == A.size() - 1 )
{
break;
}
// The new value that we're concidering to insert into our sorted range
int newVal = A[ right + 1 ];
// If this value would cause us to exceed the spanning limit K,
// don't add it to the range
if( !values.empty() )
{
if( ( newVal > *values.rbegin() && newVal - *values.begin() > K ) ||
( newVal < *values.begin() && *values.rbegin() - newVal > K ) )
{
break;
}
}
//
values.insert( A[ ++right ] );
}
// We can no longer increase the spanning range
// Add to our count the number of spans that start with our left edge
count += right - left + 1;
// Edge case... Report at most 1000000000 spans
if( count >= 1000000000 )
{
return 1000000000;
}
// Move our left edge to the right
// and remove the left value from our sorted range
values.erase( values.find( A[ left++ ] ) );
}
return count;
}So apparently this code was good enough to get a gold sticker, but I don’t think it’s actually O(n) time complexity. In the worst case I could create a multiset of size n. Since erasing a single value takes O(logn) time, then erasing them all one by one should take O(nlogn). But since sets and maps are so awesome, maybe they don’t always have a good way of judging the time complexity.
Either way, it was a pretty fun challenge and I’d like to complete more of them. They appear to have a whole set of training challenges at codility.com/demo/train/.
- Isaiah Hines