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 6 - Dominator

THE PROBLEM:

A zero-indexed array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

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

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

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

that, given a zero-indexed array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

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].

THE SOLUTION (100% score, time complexity O(N) or O(N*log(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; } return Array.IndexOf(A, leader); } }

This problem was actually quite simple as we just need to follow the explanation given in the reading material of lesson 6.

PR

CODILITY - LESSON 5 - StoneWall

THE PROBLEM:

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by a zero-indexed array H of N positive integers. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall's left end and H[N−1] is the height of the wall's right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.

Write a function:

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

that, given a zero-indexed array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.

For example, given array H containing N = 9 integers:

  H[0] = 8    H[1] = 8    H[2] = 5
  H[3] = 7    H[4] = 9    H[5] = 8
  H[6] = 7    H[7] = 4    H[8] = 8

the function should return 7. The figure shows one possible arrangement of seven blocks.

THEIR SOLUTION:

(click here to go to their blog for more explanation)

(click here to see the full test results for this solution in c#)

class Solution {

    public int solution(int[] H) {

        // write your code in C# 6.0 with .NET 4.5 (Mono)

      

        int L = H.Length;

        int stones =0;

        int [] wall = new int [L];

        int wallNum=0;

        

        for (int i=0; i<L; i++)

        {

            while (wallNum>0 && wall[wallNum-1] > H[i]) wallNum -=1;   

            if (wallNum >0 && wall[wallNum -1] == H[i]) continue;

            else 

                {

                    stones +=1;

                    wall[wallNum] = H[i];

                    wallNum +=1;     

                }

        }

        return stones;

    }

}

It took me forever to understand the problem, and then it took me forever to come up with a solution that didn't fully work. I ended up checking their blog to see if the problem was better explained and then I read their solution and just couldn't take it off my mind. So I re wrote it in C#. Then it was just too late to come up with something completely mine! (specially because I didn't like the problem)

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 5 - Nesting

PROBLEM:

A string S consisting of N characters is called properly nested if:

• S is empty;
• S has the form "(U)" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

class Solution { public int solution(string S); }

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

MY INITIAL SOLUTION (87% score, time complexity O(N))

(click here to see the full test results at codility.com)

I did this solution in few different ways and all the time got 87% overall, missing one correctness test:

negative_match invalid structure, but the number of parentheses matches

0.061 s

WRONG ANSWER got 1 expected 0

class Solution { public int solution(string S) { int l = S.Length; int count=0; if (l == 0) return 1; foreach (char c in S) { if (c == '(') count++; else count--; } if (count ==0 && S[0]=='(' && S[l-1]==')') return 1; else return 0; } }

Until I realised I wasn't taking into account strings such as "( ( ) ( ) )" which has the right amount of pairs but it is wrongly nested. After this, it took me a while to realise the silly extra line that would correct this little error...

MY IMPROVED SOLUTION (100%, time complexity O(N))

(click here to see the full test results at codility.com)

class Solution { public int solution(string S) { // write your code in C# 6.0 with .NET 4.5 (Mono) int l = S.Length; int count=0; if (l == 0) return 1; foreach (char c in S) { if (c == '(') count++; else count--; if(count <0) return 0;//CORRECTING ABOVE ERROR! } if (count ==0 && S[0]=='(' && S[l-1]==')') return 1; else return 0; } }