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)

CODILITY - LESSON 3 - GenomicRangeQuery

THE PROBLEM:

A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and Thave impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?

The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).

For example, consider string S = CAGCCTA and arrays P, Q such that:

    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6

The answers to these M = 3 queries are as follows:

• The part of the DNA between positions 2 and 4 contains nucleotides G and C(twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
• The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
• The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.

Write a function:

class Solution { public int[] solution(string S, int[] P, int[] Q); }

that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

SIMPLE SOLUTION - 100% correctness, 0% performance:

using System;

using System.Collections.Generic;

using System.Linq;

class Solution {

    public int[] solution(string S, int[] P, int[] Q) {

        string dna = "0ACGT";

        int m = P.Length;

        int [] result = new int [m];

          

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

        {

          string subS= S.Substring(P[i], (Q[i]-P[i]+1));

          char [] charSubS= subS.ToCharArray();

          Array.Sort(charSubS);

          result[i]=dna.IndexOf(charSubS[0]);

         

        

        }

        return result;

      

    }

}

100% SCORE SOLUTION:

class Solution {

    public int[] solution(string S, int[] P, int[] Q) {

            var nucleo = new int[S.Length + 1, 4];

            for (var count = 0; count < S.Length; count++)

            {    

                if (count > 0)

                {              

                    for (var index = 0; index < 4; index++)

                    {

                        nucleo[count + 1, index] += nucleo[count, index];

                    }

                }

                switch (S[count])

                {

                    case 'A':

                        nucleo[count + 1, 0]++;

                        break;

                    case 'C':

                        nucleo[count + 1, 1]++;

                        break;

                    case 'G':

                        nucleo[count + 1, 2]++;

                        break;

                    case 'T':

                        nucleo[count + 1, 3]++;

                        break;

                }

            }

            var result = new int[P.Length];

            for (var count = 0; count < P.Length; count++) {

                if(P[count] == Q[count])

                {

                   switch(S[P[count]]) {

                        case 'A':

                            result[count] = 1;

                            break;

                        case 'C':

                            result[count] = 2;

                            break;

                        case 'G':

                            result[count] = 3;

                            break;

                        case 'T':

                            result[count] = 4;

                            break;

                    }

                } else {

                    for(var index = 0; index < 4; index++) {

                        if((nucleo[Q[count] + 1, index] - nucleo[P[count], index]) > 0) {

                            result[count] = index + 1;

                            break;

                        }

                    }

                }

            }

            return result;

    }

}

PR

simpler solution?

TESDOME - Test for Jr Developer - Epic Fall!

I have just done a little test that it'd be presented to a junior developer. It wasn't difficult at all, but time ran out before I corrected my mistake! So easy to become slow in what you don't use daily!

THE TEST:

Find the index of the longest run in a give string. For example, in the string
 str ="abbcccddddcccbbaa" the value to return would be 6, which is the index of the first "d" (the char repeated 4 times in a run).

A SIMPLE SOLUTION:

char[] c = str.ToCharArray();
int count =1;
int longestRun=0;
int longestPosition=0;
int position=0;

for (int i=0; i< c.Length-2; i++)
{
    position =i;
    if (c[i] == c[i+1]) count++;
    else
      {
         if (longestRun < count)
         {
              longestRun = count;
              longestPosition = position - count +1;       
          }
          else count =1;
      }
}
Console.WriteLine(longestPosition);



Given the IDE of TestDome which doesn't allow you for much testing or displaying values to check how you are doing, neither the time give is enough to investigate what the IDE can do for you, this is the best line of though I could improvise. Needless said that I didn't have time to copy the code to visual studio, debug and paste the working code back on time! :O I might be too slow...

PR

I would love to see a good solution!!!!

TESTDOME - PALINDROME

TEST C#:

Write a function that checks if a given sentence is a palindrome. A palindrome is a word, phrase, verse, or sentence that reads the same backward or forward. Only the order of English alphabet letters (A-Z and a-z) should be considered, other characters should be ignored.

For example, IsPalindrome("Noel sees Leon.") should return true as spaces, period, and case should be ignored resulting with "noelseesleon" which is a palindrome since it reads same backward and forward.

SOLUTION (100%):

public class Palindrome

{

    public static bool IsPalindrome(string str)

    {        

        str = str.ToLower();

        var newStr = String.Join("", str.Where(char.IsLetterOrDigit));

        int l = newStr.Length;

        var reverse = String.Empty;       

        

        for (int i= l-1; i>=0; i--) reverse +=newStr[i];

        

        if (newStr == reverse) return true;

        else return false;            

            

    }

    public static void Main(string[] args)

    {      

        Console.WriteLine(IsPalindrome("Noel sees Leon."));

    }

}

PR

TESTDOME - Anagrams

TestDome is a tool used by companies to test online the coding skills of candidates. It has a couple of free tests for developers.

TEST PROBLEM (difficulty = easy) ANAGRAMS

An anagram is a word formed from another by rearranging its letters, using all the original letters exactly once; for example, orchestracan be rearranged into carthorse.

Write a function that checks if two words are each other's anagrams.

For example, AreStringsAnagrams("momdad", "dadmom") should return true as arguments are anagrams.

POSSIBLE SOLUTION (100%)

using System;

public class AreAnagrams

{

    public static bool AreStringsAnagrams(string a, string b)

    {

        if (string.IsNullOrEmpty(a) || string.IsNullOrEmpty(b) || (a.Length != b.Length))return false;

        

        foreach (char c in b)

            {

            int i= a.IndexOf(c);

                if (i>=0) a = a.Remove(i,1);

                else return false;

            }

        return string.IsNullOrEmpty(a);

    }

    public static void Main(string[] args)

    {

        Console.WriteLine(AreStringsAnagrams("momdad", "dadmom"));

    }

}

PR

CODILITY - LESSON 3 - divCount

PROBLEM:

Write a function:

class Solution { public int solution(int A, int B, int K); }

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Assume that:

• A and B are integers within the range [0..2,000,000,000];
• K is an integer within the range [1..2,000,000,000];
• A ≤ B.

Complexity:

• expected worst-case time complexity is O(1);
• expected worst-case space complexity is O(1).

MY SOLUTION (THINKING IN CODE) (100% correctness, 0%performance!, time complexity O(B-A)
class Solution { public int solution(int A, int B, int K) { // write your code in C# 6.0 with .NET 4.5 (Mono) int result = 0; for (int i=A; i<=B; i++)
{
if (A[i]%K == 0) count++;
}
return result; }


MATHEMATICAL SOLUTION (100%, time complexity O(1))
class Solution { public int solution(int A, int B, int K) { // write your code in C# 6.0 with .NET 4.5 (Mono) int result = 0; if (A%K == 0) { result = ((B-A)/K)+1; } else { result = (B/K - ((A/K)+1))+1; } return result; }

The for loop is the 1st thing that comes to mind while thinking code, but it comes with a expensive time complexity, while the second one is barely a coding challenge but a purely mathematical problem.

CODILITY - LESSON 3 - passingCars

PROBLEM:

A non-empty zero-indexed array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

• 0 represents a car traveling east,
• 1 represents a car traveling west.

The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

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

We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

MY SOLUTION (100% score, time complexity O(N))
class Solution { public int solution(int[] A) { int l = A.Length; int countZero =0; int countPairs=0; int exceed = 1000000000; for (int i=0; i<l; i++) { if (A[i]==1) countPairs += countZero; else countZero++; } if (countPairs > exceed || countPairs <0) return -1; else return countPairs; } }


The key is to remember that the pairs needs to be all (0,1) as 0 passes before 1 in time. So pairs can't combine (1,0).

Reading the array from position A[0] to A[N] each zero will combine with subsequent 1s only.

PR

CODILITY.COM - LESSON 2 - MaxCounters

THE PROBLEM

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,
• max counter − all counters are set to the maximum value of any counter.

A non-empty zero-indexed array A of M integers is given. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

For example, given integer N = 5 and array A such that:

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

the values of the counters after each consecutive operation will be:

    (0, 0, 1, 0, 0)
    (0, 0, 1, 1, 0)
    (0, 0, 1, 2, 0)
    (2, 2, 2, 2, 2)
    (3, 2, 2, 2, 2)
    (3, 2, 2, 3, 2)
    (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Assume that:

• N and M are integers within the range [1..100,000];
• each element of array A is an integer within the range [1..N + 1].

MY SOLUTION (88% - 100% results, 80% performance, time complexity O(n+M))

using System;

using System.Collections.Generic;

using System.Linq;

class Solution {

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

        int l = A.Length;

        int [] result = new int [N];

        int maxCounter=0;                

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

        {

           if (A[i]>=1 && A[i]<=N)        

             {   

                result[A[i]-1] +=1;

                if ((result[A[i]-1]) > maxCounter)    

                     maxCounter = result[A[i]-1];        

             }

           if (A[i] == N+1)

            {                          

             for (int j=0; j<N; j++) result[j] = maxCounter;              

            }            

        }

        return result;        

    }

}

There is one performance test that fails:

extreme_large all max_counter operations

>6.000 s

TIMEOUT ERROR running time: >6.00 sec., time limit: 0.49 sec.

www.codility.com

PR

CODILITY.COM - LESSON 1 - PermMissingElement

THE PROBLEM:

A zero-indexed array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

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

that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

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

the function should return 4, as it is the missing element.

Assume that:

• N is an integer within the range [0..100,000];
• the elements of A are all distinct;
• each element of array A is an integer within the range [1..(N + 1)].

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

class Solution {

    public int solution(int[] A) {

        Array.Sort(A);

        int l = A.Length;

        int missing=l+1;

        if (l == 0) return missing=1;

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

        {

            if (A[i] != i+1)

            {

             missing = i+1;

             break;

            }

        }

        return missing;

    }

}

WWW.codility.com

There are two situations: 

• when the array length is = 0 which needs to return 1 as missing element. 
• And when the array length is != 0,then it needs to find the missing element (1, ... N+1).

If the array gets sorted, every present element before the missing element will have an index = the element itself - 1 as indexes start with 0 and the array elements start with 1.

Which brings the condition to check A[i] != i + 1, and if it is, then the missing element should be there (which is i+1). After finding it, break as no need to continue.

PR