PROBLEM:

A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

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

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

A[0] = 3  A[1] = 2  A[2] = -6
A[3] = 4  A[4] = 0

the function should return 5 because:

• (3, 4) is a slice of A that has sum 4,
• (2, 2) is a slice of A that has sum −6,
• (0, 1) is a slice of A that has sum 5,
• no other slice of A has sum greater than (0, 1).

Assume that:

• N is an integer within the range [1..1,000,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000];
• the result will be 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.

Copyright 2009–2015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

SOLUTION (100%, time complexity O9N))

(click here for the full test report)

class Solution { public int solution(int[] A) { // write your code in C# 6.0 with .NET 4.5 (Mono) long max_end=-1000000; long max_slice=-1000000; int l= A.Length; if (l ==1) return A[0]; for (int i=0; i<l; i++) { max_end=Math.Max(A[i], max_end+A[i]); max_slice=Math.Max(max_slice, max_end); } return (int) max_slice; } }

The method is actually quite well explained here:

https://codility.com/media/train/7-MaxSlice.pdf

CODILITY - LESSON 6 - EquiLeader

PROBLEM:

A non-empty zero-indexed array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that:

    A[0] = 4
    A[1] = 3
    A[2] = 4
    A[3] = 4
    A[4] = 4
    A[5] = 2

we can find two equi leaders:

• 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
• 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

The goal is to count the number of equi leaders.

SOLUTION (100% score, time complexity O(N))

(click here to see the full test results)

class Solution { public int solution(int[] A) { int n = A.Length; int size =0; int value=0; Stack<int> s = new Stack<int>(); for (int i=0; i<n; i++) { if(size ==0) { size +=1; s.Push(A[i]); } else { if (s.Peek() != A[i]) size -=1; else size +=1; } } int candidate = -1; if (size>0) candidate = s.Peek(); int count =0; int leader= -1; for (int i=0; i<n; i++) { if (A[i] == candidate) count +=1; if (count > n/2) leader = candidate; } int equiLeaders=0; int leaders=0; for (int i=0; i<n; i++) { if (A[i] == leader) leaders++; if (leaders >(i+1)/2 && count-leaders >(n-1-i)/2) equiLeaders++; } return equiLeaders; } }

We can reuse the code that calculates the leader in the previous test (Lesson 6 - Dominator) and take advantage of having the leader and the number of occurrences of this leader.

Then we just loop the array from the first to the last element to see for those positions with the element leader are equi leaders.

PR

CODILITY - LESSON 5 - Fish

THE PROBLEM:

You are given two non-empty zero-indexed arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.

The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

• 0 represents a fish flowing upstream,
• 1 represents a fish flowing downstream.

If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:

• If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
• If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.

We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

For example, consider arrays A and B such that:

  A[0] = 4    B[0] = 0
  A[1] = 3    B[1] = 1
  A[2] = 2    B[2] = 0
  A[3] = 1    B[3] = 0
  A[4] = 5    B[4] = 0

Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.

THE SOLUTION (100% score, time complexity O(N))

(click here to see the full test results)

class Solution {

    public int solution(int[] A, int[] B) {

  Stack<int> aliveFishes = new Stack<int>();  

  for(int i = 0; i < A.Length; i++)

  {

       if(aliveFishes.Count==0)

       {

               aliveFishes.Push(i);

       }

       else

       {

               while(aliveFishes.Count!=0 
                        && B[i] - B[aliveFishes.Peek()] == -1 
                        && A[aliveFishes.Peek()] < A[i])  
               { aliveFishes.Pop(); }

               if (aliveFishes.Count !=0) 
               { if(B[i] - B[aliveFishes.Peek()] != -1) aliveFishes.Push(i); }

               else { aliveFishes.Push(i); }

        }

  }

  return aliveFishes.Count;

    }

}

This test took me a while, even though it is marked as 'easy'. I think because initially I tried without using a Stack.

Also because i din't read it throughly and missed the detail that while comparing two fishes, the first fish needs to have direction 1 and the second direction 0, and not 0-1.

The solution takes the first fish and pushes into the stack (as this is empty).

Then with the second and following fishes, it checks three possibilities:

• While the stack is not empty, if the direction of the fish is 1 and the direction of the last fish in the stack is 0 (aliveFishes.Peek()) and the size of the fish is bigger that the last fish in the stack, the we pop (delete) the last fish in the stack (as it has been eaten).
• If the stack is not empty, and the direction of the fish and the last fish of the stack is not the right one (gets to live) we push the fish into the stack.
• if above condition doesn't occur, so the stack is empty, we push the fish (it won't be eaten yet).

For more information about Stack follow the link:

msdn -> stack class and methods

JUNIOR DEVELOPER TEST - Strings

This is a test I did for a role of junior developer that a company was recruiting for.
It is just a small little problem and they gave us I think 15 or 20 minutes. Really, it is quite simple unless you haven't manipulated strings in a while :O, then it might take a little longer to do, but it'll be done.

THE PROBLEM:
Given a string S, such as "We are coders.   Forget CVs !" the aim is to break it down into sentences, like in the example would be "We are coders" and "Forget CVs ". the '.', '?' and '!' are delimiters, so we need to break the string into a sentence when only one of those three characters occur.  
Each sentence can be formed by 1 or more words, or it can be an empty sentence. So sentence "We are coders" would be formed by 4 blocks (3 words and empty sentence).
"  Forget CVs " is formed by 2 words and empty sentence =3.
The aim is to compute what is the maximum number of blocks given a string S. In this case it would be 4.
In the example "The mountain is tall. I rather be in the beach? Oh la la  !". The would be three sentences: "The mountain is tall"(5 blocks), "I rather be in the beach?"(7 blocks) and "Oh la la  "(4 blocks). The return answer would be 7.

QUICK SOLUTION:

public static int Blocks (string S)
{
   char [] sentenceDelimiters = {'.', '?', '!'};
   int result =0;
   
   string [] sentences= S.Split(sentenceDelimiters);
   
  for (int i=0; i<sentences.Length; i++)
  {
     int countWords;
     sentences[i]= sentences[i].Trim();  // eliminates any start/end white space
    
     if (String.IsNullOrEmpty(sentences[i])) countWords =1; // test says an empty sentence counts as 1.
     else countWords = sentences[i].Split().Length +1; // add 1 to count an empty sentence.

    if (countWords > result) result = countWords;
   }
    return result;
}

To refresh knowledge about class String and its methods:

msdn.com->string class and methods 

       
 It wasn't hard, but junior developer tests are like a lotto, you never know what topic out of a zillion you might get!

PR

CODILITY - LESSON 4 - NumberOfDiscIntersections

PROBLEM:

We draw N discs on a plane. The discs are numbered from 0 to N − 1. A zero-indexed array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:

  A[0] = 1
  A[1] = 5
  A[2] = 2
  A[3] = 1
  A[4] = 4
  A[5] = 0

There are eleven (unordered) pairs of discs that intersect, namely:

• discs 1 and 4 intersect, and both intersect with all the other discs;
• disc 2 also intersects with discs 0 and 3.

Write a function:

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

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, 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 [0..2,147,483,647].

SOLUTION (93% score, time complexity O(N*log(N)) or O(N)) 
(click here to go to codility.com and see test results)

using System; using System.Collections.Generic; class Solution { public int solution(int[] A) { int N = A.Length; long [] AX = new long[N]; long [] AY = new long[N]; for (int i = 0; i < N; i++) { AX[Math.Max(0, i - A[i])]++; AY[Math.Min(N-1, i + A[i])]++; } long result = 0; long discsAtIndex = 0; for (int i = 0; i <N; i++) { if (AX[i] > 0) { result += discsAtIndex * AX[i] + (AX[i] * (AX[i] - 1) / 2); discsAtIndex += AX[i]; } discsAtIndex -= AY[i]; } if (result <= 10000000) return (int) result; else return -1; } }

This solution fails one test;

overflow arithmetic overflow tests	0.055 s	RUNTIME ERROR tested program terminated unexpectedly
stderr: Unhandled Exception: System.IndexOutOfRangeException: Array index is out of range. at Solution.solution (System.Int32[]

The solution is easier to understand if you see each pair XY as the start and end points of a line. You would be counting how many lines are at each index.

The array AX counts how many times a line (or circle) starts before or at the index. I.e. at position 0, 4 lines (or circles) have their starting point before or at 0.

The array AY counts how many times a line (or circle) ends at the index. I.e. at position 0 no line (or circle) ends there. At position 1, one line (or circle) ends.

There are two counts; the int result (which will be the answer) and we also need to count how many lines(discs) are at each index while we loop.

For this one, I had to check some forums in order to get the result count working properly,  as i wasn't accounting for pairs already counted in the result variable ((AX[i] * (AX[i] - 1) / 2);)

PR

CODILITY - LESSON 4 - Distinct

PROBLEM:

Write a function

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

that, given a zero-indexed array A consisting of N integers, returns the number of distinct values in array A.

Assume that:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−1,000,000..1,000,000].

For example, given array A consisting of six elements such that:

A[0] = 2    A[1] = 1    A[2] = 1
A[3] = 2    A[4] = 3    A[5] = 1

the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.

Complexity:

• expected worst-case time complexity is O(N*log(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.

MY SOLUTION (100% score, time complexity O(N) or O(N*log(N)))

(codility.com click here to see test results)

class Solution { public int solution(int[] A) { int [] newA = A.Distinct().ToArray(); if (A.Length <=0) return 0; else return newA.Length; } }

Taking advantage .NET libraries and the methods already built-in.

PR

CODILITY - LESSON 4 - Triangle

PROBLEM :

A zero-indexed array A consisting of N integers is given. A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

For example, consider array A such that:

  A[0] = 10    A[1] = 2    A[2] = 5
  A[3] = 1     A[4] = 8    A[5] = 20

Triplet (0, 2, 4) is triangular.

GOOD SOLUTION (93% score, time complexity O(N*log(N))

(codility.com click here to see breakdown of the test results)

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

Array.Sort(A); if (A.Length <3) return 0; for (int i=0 ; i<A.Length-2 ; i++) { if (A[i] + A[i+1] > A[i+2] ) {return 1; break; } } return 0; } }

I made one mistake here which I realised only once all the test results were ran: I didn't account if the triplet is formed by 3 maxValue integers (C# will wraparound the result of the sum of two maxValues).

BETTER SOLUTION (100% score, time complexity O(N*log(N)))

(codility.com click here to see breakdown of the test results)

class Solution { public int solution(int[] A) { Array.Sort(A); if (A.Length <3) return 0; for (int i=0 ; i<A.Length-2 ; i++) { if (A[i] + A[i+1] > A[i+2] ) {

return 1; break; } if (A[i] == A[i+2] && 

A[i+2] == A[i+1] && 

A[i] == Int32.MaxValue) {

return 1; break; } } return 0; } }

PR