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 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 3 - MinAvgTwoSlice

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 (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

For example, array A such that:

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

contains the following example slices:

• slice (1, 2), whose average is (2 + 2) / 2 = 2;
• slice (3, 4), whose average is (5 + 1) / 2 = 3;
• slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

The goal is to find the starting position of a slice whose average is minimal.

MY SOLUTION (100%, time complexity O(N))
class Solution { public int solution(int[] A) { int minI=0; double minValue = 100001.0; for (int i=0; i<A.Length-1; i++) { if (((A[i]+A[i+1])/2.0) < minValue) { minI=i; minValue=(A[i]+A[i+1])/2.0; } if (i < A.Length-2) { if (((A[i] +A[i+1]+A[i+2])/3.0)< minValue) { minI=i; minValue= (A[i] +A[i+1]+A[i+2]) / 3.0; } } } return minI; } }

It checks the average of all subarrays formed with 2 elements and 3 elements. Any group of more elements will have an average >= to one of these groups, so the smaller group would be optimal.

PR

codility.com (click here)