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; } }

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