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.
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
- 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.”
- 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
So try to solve this challenge and don’t forget to enjoy while doing it.
Happy problem solving,