Codility Solutions

On this page I am sharing my solutions to the codility.com problem sets. They can be found here. Enjoy and share your comments!

1) Time Complexity

2) Counting Elements

3) Prefix Sums

4) Sorting

5) Stacks and Queues

6) Leader

7) Maximum Slice Problem

8) Prime and composite numbers

9) Sieve or Eratosthenes

10) Euclidean Algorithm

11) Fibonacci Numbers

12) Binary Search

13) Caterpillar method

14) Greedy algorithms

15) Dynamic Programming

16) Future Training

X) Challenges


Based on the Codility Terms of Service it is allowed to share training solutions and solutions to past challenges.

8.1.  Any Task, statement or information on the Site (including Tests Sessions and Test Session results) is confidential information. You agree not to:

(a)   disclose, publish or reproduce (including posting on any webpage or blog) such information; or

(b)   disclose to others details of a recruitment Task, ongoing monthly Challenge or ongoing competition Task (including details relating to its completion).

8.2.  This clause does not apply to: Training section of Codility service, Training Tasks and Past Challenges, their solutions and assessment results.

  • Sritharan

    Hi Martin, Yesterday I had a test in codility, i solved it but it is showing only 50% CORRECT pls help on this. It would be of great help.

    Q:

    You would like to find the sentence containing the largest numberof words in some given text.

    For example given S = “We test coders. Give us a try?”, there are three sentences. “We test coders”, “Give us a try” and “”. The second sentence contains four words: “Give”, “us”, “a” and “try”. The third sentence is empty: the function should return 4 as the solution

    A:
    The answer should return the number of words in the longest sentence.
    public static void main(String args[]) {

    String string = “fdsfdsfdsf erfdsfgf. sarfsafdsf?”;

    System.out.println(solution(string));

    }

    public static int solution(String s) {

    if (s == null || s.length() == 0) {

    return 0;

    }

    Pattern re = Pattern.compile(“[^.!?\s][^.!?]*(?:[.!?](?![‘”]?\s|$)[^.!?]*)*[.!?]?[‘”]?(?=\s|$)”, Pattern.MULTILINE | Pattern.COMMENTS);

    Matcher reMatcher = re.matcher(s);

    int max = 0;

    while (reMatcher.find()) {

    String splitarr[]= reMatcher.group().split(“\s+”);

    max = splitarr.length;

    }

    return max;

    }

    • Hey Sritharan,

      first of all. Forget regular expressions, they are extremely slow.

      Here is a short Python code that does that.
      https://ideone.com/qrxdWX

      It is still unoptimised because it creates a copy of the array, which is actually not necessary. You would be better off if you tested each character in the array for being a letter or a non-letter. Words are defined as sequences of letters. Not every non letter is a new word, sequence of non-letters does not define a new word. Sentences end with [.!?] If you manage to translate this description into code, you will solve the problem with optimal runtime.

      I won’t give you the exact code, it is probably against Codility’s copyright.

      Also, test your code against extreme cases. Does the text “” and “…” return max length 0 or 1?

      Best,
      Martin

      • Sritharan

        Thank You Marin, for your help. Have a great day. I see a point in your question and i solved the question exactly as per your guidance. Thanks once again.

    • Yogendra

      C# Code :

      string _myName = “My Name is Yogendra Dubey “;
      var LongestWord = _myName.Split(‘ ‘).OrderByDescending(r => r.Length).FirstOrDefault();

  • Michael Smith

    toptalcodility@gmail.com send me an email and I will send you a solution for codility tasks

  • Rishikesh Patil

    Hi Martin, help solving me this question.
    A non-empty zero indexed array A consisting of N non negative integers is given. Its binarian is defined as:
    binarian(A)=pow2(A[0])+pow2(A[1])+….+pow2(A[N-1])
    pow2(K)= 2^k
    For example, the binarian of array A such that:
    A[0] = 1
    A[1] = 5
    A[2] = 4
    equals 50

    binarian (A)=pow2(A[0]) + pow2(A[1]) + pow2(A[2])
    = pow2(1) + pow2(5) + pow2(4)
    = 2 + 32 +16
    = 50
    write a function.
    class function ( public int solution ( int[] A);}
    that given an array A consisting of N non negative integers, returns the length of the shortest arraythat has the same binarian as array A.
    For example, given array A such that:
    A[0] = 1
    A[1] = 0
    A[2] = 2

    Complexity
    expected worse case time complexity is O(log(N))
    expected worse case space complexity is O(1)

    • Hi Rishikesh,

      I don’t solve stuff for people as it might be part of any ongoing contest or a task they have been given by their future employers. But I will tell you how to solve it.

      Do you know the Coin Counting Problem? http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

      The solution to your question is a variation of the CCP.
      – Use Dynamic Programming (or memoization) to speed up sub-parts of the problem.
      – iterate over all numbers up to sqrt(binarian(A))
      – sqrt(N) is generally considered to be log(N) complexity

      Example 50:
      sqrt(50) = 7.07
      7*7 + 1*1 = 50
      6*6 + 2*2 = 50
      5*5 + 5*5 = 50
      5*5 + 4*4 + 3*3 = 50