Four In A Row – Golden Award For Cutting Complexity Challenge

Another Codility Challenge is out there, this one is called “Cutting Complexity Challenge” and it’s the fourth that is published this year. The same as the previous three, my solution was awarded with “Golden Award“. What is different about this challenge is that was sponsored by ASML company that is the world’s leading manufacturer of chip making equipment and there are some nice prizes for the best solutions that will be announced after the challenge is over.

CuttingComplexityResults.png  So let’s go briefly through the prizes and the challenge rules that are officially published on ASML website.

Prizes you can win for this challenge

When participating in ASML’s coding challenge you can win one of the following prizes: 

1 x Amazon Echo Show (smart speaker)

25 x Visit to the ASML campus in the Netherlands including:
– Interactive sessions about ASML and especially software development within ASML.
– A guided tour to discover the ‘Silicon Valley’ of the Netherlands.
– A 2-night-stay in a design hotel in central Eindhoven.

50 x T-shirt
You’ll get an exclusive coding shirt (limited edition).

I got my “Golden Award” let’s see if that is enough to win some of these prices

CuttingComplexityGoldenAward.png

Challenge Rules

  • By participating in the Cutting Complexity Challenge you may be eligible for prizes including an all-expenses-paid trip to visit us at our ASML campus in Eindhoven, Netherlands, an Amazon Echo, or a limited edition ASML T-shirt.
  • It’s possible to attempt the challenge more than once. When selecting prize winners we will consider all of your challenge submissions.
  • All solutions must be submitted before the challenge closes
  • C# and Java are the only 2 available coding languages
  • After each attempt you will receive feedback with your score result
  • All tasks have to be solved on your own. Any cases of plagiarism will result in disqualification
  • In case of ambiguity, the Codility judge’s decision is final
  • The challenge winners will receive an e-mail informing them that they have won a prize

More about the challenge problem

The problem is that you need to find a minimum of changes that needs to be done to a string array to get some condition and the problem is from the area in which ASML operates. This is the challenge description:

“A long time ago, when the most basic model of an HP3000 computer used to cost $95,000 (over half a million in today’s dollars), a very wise man called Gordon Moore made predictions about how computers would become cheaper and more powerful each year. According to Moore, the number of components per integrated circuit would double every two years. Thanks to the creative, determined engineers working in circuit printing technology, we do indeed have smaller, cheaper and more powerful computers today.

Circuit printing, as we call photolithography, is an extremely complex yet rewarding field, and ASML needs the best software engineers in the world to make this magic happen. We work closely with our clients to help them print their circuits in the most effective way. One of our clients requests us to write a method to optimize their circuit efficiency. The circuit is represented as a string consisting of the letters “M” and “L”, where M represents Memory units and L represents Logic units. The efficiency of the circuit is measured as the length of the longest interval of letters “M”. For example, given input string “LMMMLMMMMLLLM”, the longest interval is 4.

Our customer wants to change the circuit in such a way that the longest M-interval will be equal to K. We can change any unit at any position in the circuit, i.e. either we can change any “M” to “L” or any “L” to “M”. The objective of this challenge is to calculate the minimum number of changes we have to make in order to achieve the desired longest M-interval length K.”

Complexity requirements:

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

If you like to read more about the previous Codility challenges that I’ve taken visit some of the following links

Nickel 2018 Challenge

Cobaltum 2018 Challenge

Ferrum 2018 Challenge

So try to solve this challenge and don’t forget to enjoy while doing it.

Happy problem solving,

J.

Advertisements

8 thoughts on “Four In A Row – Golden Award For Cutting Complexity Challenge

  1. Hi Jordan, Have you heard anything from ASML yet? I also got a golden medal and even within the deadline, so I should be in the top 76 price winners. But I haven’t heard anything from them.

    Like

      • No no it’s not about the $ for me either, I’m just on a two hour very cheap Wizz Air flight from there… for me the reward would be a valid permission to skip two days of constant watching of Despacito with my daughters 😀

        Like

  2. Have you heard anything about any of the prizes regarding this challenge? There is another ASML sponsored challenge right now that says top 50 for a trip, so just wanted to know wheter it is genuine?

    Liked by 1 person

Leave a Reply to Visiting the most important high tech company you’ve probably never heard of – A Jordan Cancel 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