A story about a real struggle with an algorithm

I don’t have that much of a free time but from the one I have I try to make the most of it, and I think that is very important to have quality hobbies. For some people that is crossword puzzles, for some is reading books, for me that is running and from this year I’m taking participation in Codility Coding Challenges as well.

pcthinking.jpg
In this post I would like to share my experience with the latest Codility challenge – Cuprum 2018. I would like to mention here that I never have time to start the challenge as soon as they are published, because they are published on Saturday at 19:00 my local time and then is almost impossible to get near my PC because of the high demanding family obligations, I have practically two babies (2 year & 6 months old daughters) and I can log in with not that big interruptions when at least one of them is at sleep and I have some energy left to even think about complex algorithms.

The struggle with Cuprum 2018

To be perfectly honest I don’t think I can solve the challenges as fast as some guys out there even if I have perfect environment for that, for example for the last challenge the fastest perfect solution was delivered in only 5 minutes. I mean, come on man, I need 10 minutes only to read the assignment, and I’m doing that with a nice hot cup of coffee and I have 15-20 minutes tops to deliver the perfect solution before the situation emerges (which is usually enough time just to think of an approach and not enough to code an test the complete solution) again and I hear crying in the background.

For this challenge the process was similar as described above, I read the assignment and I thought – GREAT! I HAVE AN IDEA AND KNOW HOW TO GET A GOLDEN SOLUTION!

And I typed the code in my Visual Studio made few test cases they were working great and I posted the solution. And boom, it was not working properly. Ok, I closed my Codility tab, grabbed one of the babies to feed and I quickly figured it out where the issue was and I made quick (but wrong) conclusion that this is a dead end and dropped off that approach for the solution.

I already had another approach in my head that I knew it’s going to be correct but it will not satisfy the performance criteria for this challenge. In the next occasion that happened after few days I typed that ‘silver award’ solution, it was working but I didn’t send to Codility because I was waiting to see if I’ll get an idea to improve the performance with this approach – I didn’t because this time this was really a dead end.

I was thinking about the improvements from time to time (not in front of my PC) but I didn’t get any idea, so I decided to satisfy with “Silver Award”, I knew I would have time to try different combination at home and it would be first award of this type, all the previous were “Golden Award” solutions. After few days with absolutely no progress and no ideas for improvement I posted the solution and got the “Silver Award” for that.

SilwerAwardScore.png

And just 5 minutes after that I was sitting relaxed playing with my kids, the update for the initial approach that I have just came to me, I wasn’t even focused on that. Yes, for that solution that I got after 15 minutes, I just needed minor update to make that work and it was the approach that I rejected so easy and so fast. So I have quickly made the update there, posted the new solution and I got my “Golden Award” for that! So that is 5/5 for me this year on Codility.

GoldenAwardScore.png

Cuprum 2018 Challenge Requirements

I think there are few more days left for this challenge so these are the general requirements if you like to try it by yourself.

Write a function:

class Solution { public int solution(string S); }

that, given a non-empty string S consisting of N characters, returns the length of the longest contiguous substring (possibly empty) of string S in which every character occurs an even number of times.

For example, given S = “6daa6ccaaa6d“, the function should return 8. The longest valid password taken from S is “a6ccaaa6“; it contains four letters a, and two each of the digit 6 and letter c. Any longer substring must contain either five letters a or one letter d. Given S = “abca“, the function should return 0 (note that aa is not a contiguous substring of S).

Assume that:

  • the length of S is within the range [1..100,000];
  • S consists only of lowercase letters and digits.

Complexity:

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

You can find more details about the Cuprum 2018 Challenge here.

Happy coding,

J.

Advertisements

7 thoughts on “A story about a real struggle with an algorithm

  1. Hi Jordan, congratulations on the medals. I got a golden medal as well. I find it a bit strange that they ask for a worst-case O(N log N) solution, while an average-case O(N) solution is also possible. By the way tomorrow we should get the results for the ASML challenge!

    Liked by 1 person

    • Hi Albert, thanks and congratulations to you as well. I agree that O(N) solution is possible and natural for this problem, although I must admit mine was O(N log N), after I posted I realized that with one minor update I could make it O(N) but I got lazy and I think I already spent too much unnecessary time on this.
      Yeah I think so, tomorrow will find out what will happen with the ASML “judges selection” 🙂

      Like

      • On May 25 I got an email with this:
        [quote]

        T-shirts
        The good news is that all the Gold award contestants (67 people with a 100% score) will receive an ASML T-shirt (limited edition). We will reach out for your address information via separate email.

        And more
        Moreover, we promised to select 25 people whom we will invite to come over to the Netherlands to visit the ASML campus and learn more about software development within ASML. Next week our software department will select 25 people out of the 67 Gold award winners. The selection criteria are based on their score, coding language used and potential match with ASML. We will inform those winners separately next Friday.”

        [/quote]
        That Friday was last Friday and I haven’t heard anything. Also no email to “reach out for my Tshirt-email”, so something must be wrong. @Jordan I suppose you didn’t hear anything either?

        Like

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