Another programming task arrives

What you see is all too true! One more programming task is now available in all subscriptions. We haven’t stopped working during our January recruitment boom.

How to put up a free Codility commercial at the airport? :)

After the DLD Conference in Munich our team posted a free commercial at the airport. You can see it below – looks beautiful, doesn’t it?

Total audience reached: at least a few thousand
Satisfaction: unlimited

We offer a free Basic Subscription to anybody who does the same! ;-) Airports all around the world are permitted!

New programming challenge: “UnionOfIntervals”

Now available in our Plus and Max Subscription is another programming task: “UnionOfInterval". You can create a test and send it to your candidates.

And just in case it slipped your attention before, you can upgrade to the Max Subscription with a huge sign-up discount!

We would like to welcome new programming languages

After listening to our customers and programming community, we are pleased to announce the support for yet another two programming languages: Objective-C and Lua. 

 




Now each programming task is available in 13 langauges:

• C, 
• C++, 
• C#, 
• Java, 
• JavaScript, 
• Pascal, 
• Python, 
• PHP, 
• Perl, 
• Ruby , 
• Visual Basic, 
• Objective-C,
• Lua. 

Our family is growing fast!

Max Subscription Sign-up Discount on Codility Programming Tests

The beginning of a New Year is always replete with great new projects and work. That is why Codility would like to welcome the New Year with a very special Max Subscription Sign-up Discount!
The first month now costs over 50% less. Screen your candidates on a large scale and with the most sophisticated tasks to rack up the IT stars!

 What are the advantages of a Max Subscription?

• Allocation of 400 tests per month
• 12 months’ data retention
• Capacity to run 20 tests simultaneously
• Access to over 120 tasks (including 50 medium difficulty and 15+ hard tasks)
• 4 hours’ complimentary support

Make your screening process smarter!

Find out more on codility.com/pricing

Codility Programming Certificate- Nu 2011 certificate solution

Now that the New Year has arrived, it is time for a new Codility Certificate problem.  It is also time to reveal how the previous certificate problem, codenamed Nu, can be solved.  You can still give it a try, although no certificate will be granted.

In the Nu certificate problem, two arrays, A and B, of integers sorted in ascending order, are given.  Additionally, a sequence of queries is given in the following form: given two continuous segments, one in the first array and another in the second, find a median of numbers in both segments.  The result that should be computed is a median of answers to the given queries.

The main question is: how quickly can a median of a sequence of numbers be computed?  For an arbitrary sequence of N numbers, the median can trivially be computed in O(N log(N)) time.  Simply, one can sort the sequence and pick the middle element.  (Note that all the medians in this problem are taken from odd numbers of elements.)

More sophisticated algorithms, e.g. the algorithm of the five(s), can find the median in O(N) time.  (The name of the algorithm relates to two sources: one is that the given sequence is divided into groups of five elements; another is that the algorithm has five authors.)  However, these algorithms don't make use of the fact that the input sequences are sorted.  Using them, one can solve the problem in O(K*(N+M)) time, where K is the  number of queries and N and M are the lengths of the given sorted sequences.

We will show how to find the median of the union of two sorted sequences in a logarithmic time.  It will allow us to answer all the queries in O(K*log(N+M)) time.  Then, the result can be calculated even using sorting, which yields O(K*log(K+N+M)) total time complexity.  Let us assume that median(p, q, r, s) is a function returning a median of A[p..q] and B[r..s], where A and B are the given sorted arrays.  A solution coded in Python might be as follows:

def double_median(A,B,P,Q,R,S):
    n = len(A)
    m = len(B)
    k = len(P)
    medx = [0]*k
    for i in xrange(k):
        medx[i] = median(P[i], Q[i], R[i], S[i])
    medx.sort()
    return medx[k // 2]

We still have to implement the function median.  Let us define x = q−p+1, y = s−r+1, z = (|x−y|−1)/2; note that |x−y| is odd.  First, we will simplify the problem and reduce it to a case where x=y±1.  We can either drop the top z elements and bottom z elements from the larger of the ranges, p..q and r..s, or instantly point  to the result.  If med(p, q, r, s) is a function returning a median of A[p..q] and B[r..s] for q−p=r−s±1, then the implementation of function median can be as follows:

    def median(p, q, r, s):
        x = q-p+1
        y = s-r+1
        z = abs(x-y) // 2
        if (x > y):
            if (A[p+z] >= B[s]):
                return A[p+z]
            elif (A[q-z] <= B[r]):
                return A[q-z]
            else:
                return (med(p+z, q-z, r, s))
        else:
            if (B[r+z] >= A[q]):
                return B[r+z]
            elif (B[s-z] <= A[p]):
                return B[s-z]
            else:
                return (med(p, q, r+z, s-z))

Now, we have to implement function med.  We will do it using bisection.   The key observation is that if A[p+d] ≤ B[s−d], then we can drop the bottom d elements and top d elements by narrowing to the ranges p+d..q and r..s−d.  Similarly, if A[q−d] ≥ B[r+d], then we can narrow to the ranges p..q−d and r+d..s.  Moreover, if p+d ≤ q−d and r+d ≤ s−d, then A[p+d] ≤ A[q−d] and B[r+d] ≤ B[s−d]. Hence: 

• either A[p+d] ≤ B[s−d] and we can narrow to the ranges p+d..q and r..s−d;
• or A[q−d] ≥ A[p+d] > B[s−d] ≥ B[r+d] and we can narrow to the ranges p..q−d and r+d..s.

For x+y > 5 we can use bisection, taking d=⌊(x+y)/4⌋.  For smaller values of x+y, we can simply sort and pick the middle element.

    def med(p, q, r, s):
        x = q-p+1
        y = s-r+1
        if x + y <= 5:
            medi = A[p:q+1]+B[r:s+1]
            medi.sort()
            return medi[(x+y)//2]
        else:
            d = (x+y) // 4
            if A[p+d] < B [s-d]:
                return (med(p+d, q, r, s-d))
            else:
                return (med(p, q-d, r+d, s))

New Programming Task "FindSum"

We have added new task "FindSum"! Available to Basic, Simple, Plus, Premium and Max Subscribers! Check here for more!