Best solutions for Codility Lessons.
Some time ago I found on Codility website a wonderful set of training tasks which covers many subjects of questions using by big companies on interview. Codility calls this set of tasks the “Lessons”. Each lesson has a link to a PDF file with theoretical description subject of the lesson. The tasks are intended to show examples of the practical application of knowledge obtained from the description, but almost every task has a solution much better than what the authors of the lessons imply, this solution usually uses a different approach, not described in the topic of the lesson. I really like them and I believe most of them are just brilliant. Let me explain why this set of tasks made me so excited. Below I described common problems of training tasks which you can find in Internet and why the tasks from the Lessons set are different. I don’t want to advertise Codility, they have problems too, for example their editor of programming code is not so advanced like on Leetcode.com, but they made a good job when they collected these tasks. I’ve got big pleasure to solve them and decided to share my experience here:
Often the tasks have ambiguous description. I guess it happens because when their authors writing these descriptions they already know the answer and they consider of many things as obvious, but when you read this description for first time you have a lot of questions but you can’t ask them because you can’t contact with the author. Or even example of the programming code in the task contains errors or undefined behavior. I got in this trouble for many times.
The tasks from this set have perfect descriptions and always have examples. No one time I had problem with understanding or had unanswered questions;
Often the tasks are boring. Solving of them don’t make you happy. When you finished solving of the task you feel like you just finished a hard job if the task was hard enough or you feel like you lost time if the task was easy.
The tasks from this set are hard enough to make you feel challenge. They usually are much deeper than they seem at first glance. Often your final solution use completely different approach than your first wrong solution.
Often the tasks have the only exact answer. When the task have the only answer it is bad if you want to measure of qualification level and experience of a programmer.
Most of the tasks from this set possible to solve in many ways. Depending on your knowledge you may write the answer with time complexity O(Log N), O(N), O(N²) or even O(M^n) you may use arrays, trees, bit sets or even don’t use additional memory at all. All these solutions will be correct but they will show your professional level.
Often the websites where the tasks collected have very poor system of tests which checks the solution. Most of web sites of such kind check only several simple test cases.
Test system for tasks for this set is the most advanced which I ever seen. All the tasks checked against minimum 15 well designed test cases. Only perfect solutions which handle all corner cases get score 100%. Good support. When I’ve got a doubt that the test system works correctly and sent a letter with my doubt to the support. I’ve received an answer tomorrow with detailed description of a problem in my code and explanation why the test system works correctly in this case.
I never thought I am perfect so, after I was finishing to write of my own solution, I was trying to find how other people solved the same task. I have found several genial approaches which reach theoretical limit on a given tasks, when most of other solutions have bad and very bad quality. Even worse, bad solutions are more popular and have more up votes, stars or other scores because they easy for understanding than the best solutions. Sometimes many people rewriting some popular piece of code without understanding how it works and then the newcomers use it just because all others use it and consider it as a perfect example. For example this happens with a kind of a Knapsack Problem which calls a Set Partition Problem. The most popular in internet solution of this problem use dynamic programming and based on building of matrix of sums of elements of the set. This approach is fast and always find the best solution but it consumes too much memory if values of the set exceed some small limit. We need to divide the set to two parts so we should build the matrix only for one half of the possible sums. I found about 20 websites with description of this algorithm where the description correctly told about the matrix for one half of the possible sums but in the code they built the matrix for whole range of the sums which doubled memory consumption. It looks that all these guys had rewriting the same description by their own words and had rewriting the code without understanding the algorithms. Despite the fact that this algorithms perfectly described on Wikipedia with example of code and even with picture of the built matrix.
So I decided to write this set of articles where I show the best, in my opinion, solutions for each task and describe how they work and why they are the best. Of course if you know even better solution and you share it with me I will be happy to correct the article. I will use C++ but I can add the solutions in other languages if somebody need it. I will be adding links to new articles to this table when the corresponding article gets ready.
You might be interested to read similar sets of articles about the best solutions for Microsoft interview tasks here and for Amazon here.
Table of contents:
Lesson 8 Leader
Lesson 9 Maximum slice problem
Lesson 10 Prime and composite numbers
Lesson 11 Sieve of Eratosthenes
Lesson 12 Euclidean algorithm
Lesson 13 Fibonacci numbers
Lesson 14 Binary search algorithm
Lesson 15 Caterpillar method
Lesson 16 Greedy algorithms
Lesson 17 Dynamic programming
