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)

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.