Golden Award for my Ferrum 2018 solution

From time to time I like to solve interesting algorithmic problems and a while ago I discovered Codility and their challenges. This time the active challenge is called Ferrum 2018 and I managed to get the Golden Award recognition which means that I solved the problem with optimal code execution time and memory complexity.

CodilityGoldenAward

If you like this kind of programming brain teasers you should try to get an award for this one. There are way more complex problems on Codility (for example the Chromium 2017 was one of the more demanding ones, at least for me) but let me give you brief introduction about the awards and the Ferrum 2018 challenge.

Codility Challenges and Awards

There is always one active challenge on Codility, at least in this short period while I’m following them, and plenty of training resources and lessons. when you post your solution it will be automatically tested, and it will need to pass many test cases. One group of test cases is measuring the Correctness of the solution, and the other group of test is measuring the Performance of your solution.
After your solution is being evaluated there are two types of awards that you can get,
Silver Award and Golden Award.
Silver Award is given for the solution that will pass all the test cases and return the correct result in all of them but has problems with the scalability i.e. the code doesn’t fit in the worst-case time complexity or worst-case space complexity.
Golden Award is given for the solution that besides passing all the test cases must fit in the wanted time and space complexity.  So if your code is perfect you will get this result screen:
PerfectTaskScore

Ferrum 2018 Challenge

The Ferrum 2018 challenge is pretty straight forward, you are given an array A consisting of the integers −1, 0 and 1. A slice of that array is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. Your task is to find the longest slice of A whose elements yield a non-negative sum.
The task is to write a function

class Solution { public int solution(int[] A); }

that, given an array A of length N, consisting only of the values −1, 0, 1, returns the length of the longest slice of A that yields a non-negative sum. If there’s no such slice, your function should return 0.

Also there are limitations for the time complexity and the space complexity.

  • expected worst-case time complexity is O(N*log(N));
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

The details about the challenge you can find here: Ferrum 2018.

My solution performance

First I made a working solution with O(N^2) complexity, which is the first thing I do, write a solution that works and then use that for testing other solutions. Because the worst-case time complexity was O(N*log(N)) at start I went into wrong direction trying to find a solution using some kind of a binary tree, but in the meanwhile I thought of even better solution with O(N) time complexity and minimal space complexity, approximately O(1).

Try this challenge by yourself.

Happy coding,

J.

Advertisements

One thought on “Golden Award for my Ferrum 2018 solution

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s