Future training - TreeHeight

Here is another codility problem solution from the codility lessons (TreeHeight -Compute the height of a binary tree.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
 public int solution(Tree T) {
                // to remove the first node from the calculation
  return computeTreeHeight(T) - 1;
 }

 private int computeTreeHeight(Tree T) {
  if (T == null) return 0;
  int leftT = 1 + computeTreeHeight(T.l);
  int rightT = 1 + computeTreeHeight(T.r);

  return Math.max(rightT, leftT);
 }
}

Prefix Sums - GenomicRangeQuery

Here is another codility problem solution from the codility lessons (GenomicRangeQuery-Find the minimal nucleotide from a range of sequence DNA..) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	HashMap < Integer, Integer > ListOfA = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfC = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfG = new HashMap < Integer, Integer > ();
	HashMap < Integer, Integer > ListOfT = new HashMap < Integer, Integer > ();
	public int[] solution(String S, int[] P, int[] Q) {
		// write your code in Java SE 8
		int sum = getSum(S);
		fillMap(S);
		int[] queries = new int[P.length];
		for (int i = 0; i < P.length; i++) {
			int startIndex = P[i];
			int endIndex = Q[i];
			int sumA = ListOfA.get(endIndex) - ListOfA.get(startIndex);

			if (S.charAt(startIndex) == 'A') sumA++;

			if (sumA > 0) {
				queries[i] = 1;
			} else {
				int sumC = ListOfC.get(endIndex) - ListOfC.get(startIndex);
				if (S.charAt(startIndex) == 'C') sumC++;

				if (sumC > 0) {
					queries[i] = 2;
				} else {
					int sumG = ListOfG.get(endIndex) - ListOfG.get(startIndex);
					if (S.charAt(startIndex) == 'G') sumG++;

					if (sumG > 0) {
						queries[i] = 3;
					} else {
						int sumT = ListOfT.get(endIndex) - ListOfT.get(startIndex);
						if (S.charAt(startIndex) == 'T') sumT++;

						if (sumT > 0) {
							queries[i] = 4;
						}
					}
				}
			}

			// System.out.println(queries[i]+"========"+P[i]+"========"+Q[i]);
		}

		// System.out.println(S);

		return queries;
	}

	private void fillMap(String S) {
		int sumA = 0;
		int sumC = 0;
		int sumG = 0;
		int sumT = 0;
		int len = S.length();
		for (int i = 0; i < len; i++) {
			char c = S.charAt(i);
			switch (c) {
				case 'A':
					sumA++;
					break;
				case 'C':
					sumC++;
					break;
				case 'G':
					sumG++;
					break;
				case 'T':
					sumT++;
					break;

			}
			ListOfA.put(i, sumA);
			ListOfC.put(i, sumC);
			ListOfG.put(i, sumG);
			ListOfT.put(i, sumT);


		}

	}
	private int getSum(String S) {
		int sum = 0;
		int len = S.length();
		for (int i = 0; i < len; i++) {
			sum += mapChartoInt(S.charAt(i));
		}
		return sum;

	}
	private int mapChartoInt(char c) {
		int mappedVal = -1;
		switch (c) {
			case 'A':
				mappedVal = 1;
				break;
			case 'C':
				mappedVal = 2;
				break;
			case 'G':
				mappedVal = 3;
				break;
			case 'T':
				mappedVal = 4;
				break;

		}
		return mappedVal;
	}
}

Prefix Sums - PassingCars

Here is another codility problem solution from the codility lessons (PassingCars-Count the number of passing cars on the road.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

class Solution {
	public int solution(int[] A) {
		// write your code in Java SE 8
		boolean isZero = false;
		int zeroCount = 0;
		int pairCount = 0;

		for (int i = 0; i < A.length; i++) {
			if (A[i] == 0) {
				isZero = true;
				zeroCount++;
			} else if (A[i] == 1) {
				if (isZero) {
					pairCount = pairCount + zeroCount;
					if (pairCount > 1000000000) return -1;
				} else {
					continue;
				}
			}

		}


		return pairCount;
	}
}

Prefix Sums-CountDiv

Here is another codility problem solution from the codility lessons (CountDiv-Compute number of integers divisible by k in range [a..b].) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

class Solution {
	public int solution(int A, int B, int K) {
		// write your code in Java SE 8
		int count = 0;
		int div1 = 0;
		int div2 = 0;

		div1 = A / K;
		div2 = B / K;
		count = div2 - div1;
		if (A % K == 0) count++;

		return count;
	}
}

Prefix Sums - MinAvgTwoSlice

Here is another codility problem solution from the codility lessons (MinAvgTwoSlice-Find the minimal average of any slice containing at least two elements.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

class Solution {
	public int solution(int[] A) {
		long min = Long.MAX_VALUE;
		int index = -1;
		//we have A+B/2 to be comapred with A+B+C/3
		//to make things easiler we are going to multuply both side with 6


		for (int i = 0; i < A.length - 2; i++) {

			long res1 = ((A[i] + A[i + 1])) * 3;
			long res2 = ((A[i] + A[i + 1] + A[i + 2])) * 2;



			long minRes = Math.min(res1, res2);

			if (minRes < min) {
				min = minRes;
				index = i;
			}

		}
		if ((A[A.length - 2] + A[A.length - 1]) * 3 < min) {
			return A.length - 2;
		}

		return index;
	}
}

Stacks and Queues - Fish

Here is another codility problem solution from the codility lessons (Fish-N voracious fish are moving along a river. Calculate how many fish are alive.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	public int solution(int[] A, int[] B) {

		int count = 0;
		Stack < Integer > previousFishes = new Stack < Integer > ();

		for (int i = 0; i < A.length; i++) {
			int currentFish = A[i];
			int currentFlow = B[i];
			if (currentFlow == 1) {
				previousFishes.push(currentFish);
			}
			if (!previousFishes.empty() && currentFlow == 0) {
				while (!previousFishes.empty() && currentFish > previousFishes.peek()) {
					int fish = previousFishes.pop();
				}
			}
			if (previousFishes.empty() && currentFlow == 0) {
				count++;
			}

		}
		return count + previousFishes.size();
	}
}

Stacks and Queues - Nesting

Here is another codility problem solution from the codility lessons (Nesting -Determine whether given string of parentheses is properly nested.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	public int solution(String S) {
		// write your code in Java SE 8
		if (S.length() % 2 != 0) return 0;
		if (S.length() == 0) return 1;



		Stack < Character > st = new Stack < Character > ();
		for (int i = 0; i < S.length(); i++) {

			if (isOpenTag(S.charAt(i))) {
				st.add(S.charAt(i));
			} else {
				if (!st.empty()) {
					char sc = st.pop();
					if (getCloseTag(sc) != S.charAt(i)) return 0;
				} else {
					return 0;
				}
			}

		}
		if (!st.empty()) return 0;

		return 1;


	}

	private char getCloseTag(char c) {
		switch (c) {
			case ('('):
				return ')';
			default:
				return ' ';

		}
	}

	private boolean isOpenTag(char c) {
		switch (c) {
			case ('('):
				return true;


			default:
				return false;

		}
	}

}

Maximum slice problem - MaxDoubleSliceSum

Here is another codility problem solution from the codility lessons (MaxDoubleSliceSum -Find the maximal sum of any double slice.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	public int solution(int[] A) {
		int[] fromLiftDoubleSlices = new int[A.length];
		int[] fromRightDoubleSlices = new int[A.length];
		int max_ending = 0;
		for (int i = 1; i < A.length - 1; i++) {
			max_ending = Math.max(0, max_ending + A[i]);
			fromLiftDoubleSlices[i] = max_ending;
		}
		max_ending = 0;
		for (int i = A.length - 2; i > 0; i--) {
			max_ending = Math.max(0, max_ending + A[i]);
			fromRightDoubleSlices[i] = max_ending;
		}
		int maxSum = 0;
		for (int i = 1; i < A.length - 1; i++) {
			maxSum = Math.max(maxSum, fromLiftDoubleSlices[i - 1] + fromRightDoubleSlices[i + 1]);
		}



		return maxSum;
	}
}

Maximum slice problem - MaxSliceSum

Here is another codility problem solution from the codility lessons (MaxSliceSum - Find a maximum sum of a compact subsequence of array elements. ) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

Please be aware that the following code scores 92% only failed in on test case so if you could find where is the bug I will be glade to tell me.

class Solution {
	public int solution(int[] A) {
		// write your code in Java SE 8
		int sum = 0;
		int maxPosSeries = Integer.MIN_VALUE;
		int sumPos = 0;
		int maxVal = Integer.MIN_VALUE;
		boolean isPosFound = false;
		boolean containsPos = false;
		for (int i = 0; i < A.length; i++) {
			sum += A[i];
			maxVal = Math.max(maxVal, A[i]);
			if (A[i] >= 0) {
				isPosFound = true;
				containsPos = true;
				sumPos += A[i];
				maxPosSeries = Math.max(sumPos, maxPosSeries);

			} else if (A[i] < 0) {
				sumPos = 0;
				isPosFound = false;
			}


		}
		int min = Integer.MAX_VALUE;
		int ans = 0;
		int commulativeSUm = 0;

		for (int i = 0; i < A.length; i++) {
			commulativeSUm += A[i];
			int def = sum - (commulativeSUm);
			if (def < min) {
				min = def;
				ans = commulativeSUm;
			}

		}
		if (!containsPos) return maxVal;
		return Math.max(ans, maxPosSeries);

	}
}

Maximum slice problem - MaxProfit

Here is another codility problem solution from the codility lessons (MaxProfit -Given a log of stock prices compute the maximum possible earning. ) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

class Solution {
	public int solution(int[] A) {
		// write your code in Java SE 8

		int max = 0;
		int min = Integer.MAX_VALUE;
		int profit = Integer.MIN_VALUE;
		if (A.length < 2) return 0;
		for (int i = 0; i < A.length; i++) {

			min = Math.min(min, A[i]);
			int def = A[i] - min;
			profit = Math.max(profit, def);


		}

		return Math.abs(profit);
	}
}

Leader - EquiLeader

Here is another codility problem solution from the codility lessons (EquiLeader -Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same. ) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
 public int solution(int[] A) {
  // write your code in Java SE 8


  Integer[] equi = findEquiLeader(A);
  if (equi == null) return 0;
  else {
   int equiLeader = equi[0];
   int count = equi[1];
   int startCount = 0;
   int equileaderCount = 0;
   for (int i = 0; i < A.length; i++) {
    if (A[i] == equiLeader) startCount++;

    if (startCount > (i + 1) / 2 && (count - startCount) > (A.length - (i + 1)) / 2) {
     equileaderCount++;
    }
   }
   return equileaderCount;
  }

 }
 private Integer[] findEquiLeader(int[] A) {
  int len = A.length;
  int size = 0;
  Integer value = null;
  for (int i = 0; i < A.length; i++) {
   if (size == 0) {
    value = A[i];
    size++;
   } else {
    if (value == A[i]) {
     size++;
    } else {
     size--;
    }
   }
  }
  if (size > 0) {
   int count = 0;
   for (int i: A) {
    if (i == value) count++;
   }
   if (count > A.length / 2) {


    return new Integer[] {
     value, count
    };

   }


  }

  return null;

 }


}



///Using Hashmap

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        HashMap< Integer,Integer> hm = new HashMap();
        for( int i: A)
        {
            if(hm.containsKey(i))
                hm.put(i,hm.get(i)+1);
            else
                 hm.put(i,1);
        }
        int maxNum=0;
        int maxCount=0;
        for(int j: hm.keySet())
        {
            int currentCount=hm.get(j);
            if(maxCount< currentCount)
            {
                maxCount=currentCount;
                maxNum=j;
            }
        }
        //System.out.println(maxCount+" "+maxNum);
        int countOfMax=maxCount;
        int firstPart=0;
        int equiLeader=0;
        for(int i =0;i< A.length-1;i++)
        {
            if(A[i]==maxNum)
            {
                countOfMax--;
                firstPart++;
            }
          
            if((A.length-(i+1))/2< countOfMax&&(i+1)/2< firstPart)
            {
                equiLeader++;
            }
        }
        return equiLeader;
    }
}

Leader - Dominator

Here is another codility problem solution from the codility lessons (Dominator-Find an index of an array such that its value occurs at more than half of indices in the array.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	public int solution(int[] A) {
		Integer[] equi = findEquiLeader(A);
		if (equi == null) return -1;
		else {
			int equiLeader = equi[0];
			int value = equi[1];
			return value;
		}
	}
	private Integer[] findEquiLeader(int[] A) {
		int len = A.length;
		int size = 0;
		Integer value = null;
		for (int i = 0; i < A.length; i++) {
			if (size == 0) {
				value = A[i];
				size++;
			} else {
				if (value == A[i]) {
					size++;
				} else {
					size--;
				}
			}
		}
		if (size > 0) {
			int count = 0;
			int index = 0;
			for (int i = 0; i < A.length; i++) {
				if (A[i] == value) {
					count++;
					index = i;
				}
			}
			if (count > A.length / 2) {
				return new Integer[] {
					value, index
				};
			}


		}
		return null;

	}
}