# 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!

## 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

• Raj kumar

Hi Rishikesh Patil, did you find the solution??

• Puneet Sindhwani

Hi Martin

Please let me know if following code is correct or not for finding the minimum number of students standing in a contiguous group who, after rearranging their positions, will cause the entire row to be ordered by height.

``` function solution(\$array) { \$newarray = \$array; sort(\$newarray); \$length = count(\$array); \$swaps = 0; \$b = 0; for (\$a = 0; \$a < \$length; \$a++) { if (\$array[\$a] == \$newarray[\$b]) { \$b = \$b + 1; } else { \$swaps = \$swaps + 1; } }```

``` return \$swaps; } ```

```\$array = array(1,2,6,5,5,8,9); ```

• Let me rephrase your question: Given an array A, find the smallest non-increasing sub-array A’. The issue which that definition is, that a non-sorted sub-array could contain elements that belong to a sorted part of A. You should be able to solve the problem with a two-directional caterpillar method. It will require a few pointers but it is possible in O(n). Is it a Credit Suisse interview question?

• Puneet Sindhwani

It is related to clicking the pictures of students of a class standing in a row.

Complexity:

1. expected worst-case time complexity is O(N*LOG(N))

2. expected worst-case space complexity is O(N), beyond input storage

• despina

Hello, got the same problem, solved with caterpillar two-way method, got good results when testing with the sample array and 3 other, then.. surprise: test score: 11%.. not sure what I missed..

• That would explain the expected O(NlogN) complexity. @puneetsindhwani:disqus does your algorithm solve the problem? If not, where is the issue?

• despina

Regarding @Puneet algoritm: Let’s suppose the test nonsorted array would have another element at the end with value 1.

Comparing this array against the sorted one would return the nr of swaps equal toate the array count. The expected result though should be count-3.

• Puneet Sindhwani

We got the score as 0% but we don’t know the reason for this. We ran around 8 test cases including the example given and all went well. We just need to know what was wrong in the code.

• despina

Hello, @puneetsindhwani:disqus. Again, your algorithm doesn’t work for the following test case:
\$array = array(1,2,6,5,5,8,9,1);

You are not returning “contiguous group who, after rearranging their positions, will cause the entire row to be ordered”, but rather compare the ordered and unordered arrays against each other. Simply adding another small value at the end of the sample array would demonstrate that.

• Pias Kumar Das

// you can also use imports, for example:
import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println(“this is a debug message”);

class Solution {
public int solution(int[] A) {
// write your code in Java SE 8
if(A.length==1)
return 0;

ArrayList al=new ArrayList();
//finding peak
for(int i=1;iA[i-1] && A[i]>A[i+1])
{
}

}

int s=al.size();
if(s==1)
return 1;
if(s==0)
return 0;

s=(int) Math.ceil(Math.sqrt(A.length));
while(s>=0)
{
int lp=al.get(0);
int c=1;

for(int i=1;i=s)
{

lp=al.get(i);
//System.out.println(lp+” “+f);
c++;
if(c==s)
return c;
}
}
s–;
}
return 0;
}
}

• pert hax

Hi Martin,

Can you give me a tip on how to solve this step by step? I’m not asking for solutions, just a tip or a guide. Thank you!

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
A[0] + A[1] + … + A[P−1] = A[P+1] + … + A[N−2] + A[N−1].
Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

For example, consider the following array A consisting of N = 8 elements:

A[0] = -1
A[1] = 3
A[2] = -4
A[3] = 5
A[4] = 1
A[5] = -6
A[6] = 2
A[7] = 1
P = 1 is an equilibrium index of this array, because:

A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:

A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:

A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
and there are no elements with indices greater than 7.

P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

Write a function:

class Solution { public int solution(int[] A); }

that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

For example, given array A shown above, the function may return 1, 3 or 7, as explained above.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

• Hi Pert,

if all numbers are positive, you can have a look at this variant of the problem https://www.martinkysel.com/hackerrank-sherlock-and-array-solution/

In the Codility Equi case, you can have negative values. Simply create an array with prefix sums. That can be computed in O(n) time in a single pass. Afterwards compare the sum of all elements on the left (the prefix sum) to the sum on the right (calculated from the prefix sum and the sum of all elements).

• Abhishek patro

A java program to Decompose int into sum of ints having no consecutive 1s in binary form.

A non-negative integer N is called sparse if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is “101001” and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is “11010” and it contains two consecutive 1s.

Two non-negative integers P and Q are called a sparse decomposition of integer N if P and Q are sparse and N = P + Q.
could you hel me with that please.

• Hi Abhishek,

unless there are additional rules to the task, I would say that simply selecting odd/even bits from the number should be sufficient.

When you binary AND the pattern 10101010 you guarantee that every other bit will be a 0, effectively breaking down all series of 1s.

``` foo = 131 #1010 print(foo & 0xAAAAAAAAAA) #0101 print(foo & 0x5555555555) ```

• Abhishek patro

Thanks Martin …
Please find the full problem as follows

A non-negative integer N is called sparse if its binary representation does not contain two consecutive bits set to 1. For example, 41 is sparse, because its binary representation is “101001” and it does not contain two consecutive 1s. On the other hand, 26 is not sparse, because its binary representation is “11010” and it contains two consecutive 1s.

Two non-negative integers P and Q are called a sparse decomposition of integer N if P and Q are sparse and N = P + Q.

For example:

· 8 and 18 are a sparse decomposition of 26 (binary representation of 8 is “1000”, binary representation of 18 is “10010”);

· 9 and 17 are a sparse decomposition of 26 (binary representation of 9 is “1001”, binary representation of 17 is “10001”);

· 2 and 24 are not a sparse decomposition of 26; though 2 + 24 = 26, the binary representation of 24 is “11000”, which is not sparse.

Write a function:

class Solution { public int solution(int N); }

that, given a non-negative integer N, returns any integer that is one part of a sparse decomposition of N. The function should return −1 if there is no sparse decomposition of N.

For example, given N = 26 the function may return 8, 9, 17 or 18, as explained in the example above. All other possible results for N = 26 are 5, 10, 16 and 21.

Assume that:

· N is an integer within the range [0..1,000,000,000].

Complexity:

· expected worst-case time complexity is O(log(N));

· expected worst-case space complexity is O(1).

• Abhishek patro

What I followed is I decomposed the integer as sum of integers and tried checking if each of the number is sparse or not ..

• I gave you the solution above 🙂 Only works for 4 byte numbers such as int in C++. If you want 8 bytes (long long) you have to AND 0xAA AA AA AA AA AA AA AA. Int in java is 4 bytes.

• Abhishek patro

Ease suggest some best internet sites to practice as I an new and naive to Java and want to try my luck with data structures using Java.
I want to try more of problems …

• Levi Kitrossky

Hi! The current challenge Manganum 2017 seems theoretically impossible. It is equivalent to passing a one directional weighted graph. Since we need to check edges it cannot be less than N*N while they expect N*Log(N).
I arrived to a silver award with correct functionality and overall 53% due to scalabilty problems. Am I mistaken that one cannot reach the goal performance?
Thanks, Levi

• Hi Levi,

I would think of the problem as a weighted graph of line intersections. Each node in the graph represents an intersection that can lead to the next jump and each edge is the weight of that jump. I would generate the graph from the pawns, so the number of intersections would quickly explode. It would be a function of the number of pawns. There is a maximum of N^2 pawns.

The graph is not directed, it is circular. Each edge can only be visited once. This makes the solution a variant of the *longest simple path problem* and makes in NP hard.

Your N^2 is better than my naive solution.

• Levi Kitrossky

So, the Codility authors made an error with their demand of N*Log(N)?

• I am reluctant to make such a claim. Since people have solved the task in the problem under the hard N*LogN limit, it must be solvable. Unless of course the solution can be micro-optimised to pass the time, but not really the claimed complexity.

It is much more probable, that there is a solution in N*LogN that does not involve graphs.