codility

FloodDepth

| Masuma

Solution:

This java solution for the problem FloodDepth scored a 100%

Logic:

So the logic here is to imagine you are walking down the rocks..as you go down you try to set the minimum depth with how low you have reached, when you go up then at that point you must calculate the maximm depth so far and put it in a depths queue.

Also if you are climbing up higher than ever before then you need to actually reset the minimum node to null because its as good as entering a new valley. At this point reset the minimum depth to null and your highest altitude is also reset to this new high.

Keep doing that until you reach zero altitude, that is end of array!

And because we are collecting the depths in a PriorityQueue, whose comparator is set to maintain the elements in reverse order then in that case we have depths stored in descending order. so when you poll for the first time..you get your answer! maximum depth. Nevertheless if the size is zero..there was no water harvesting 🙂

I hope this makes sense with the algo I have written here, its the first pass..perhaps this can be enhanced with all optimised functions…I leave that to you coder!

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class FloodDepth {

    public int solution(int[] A) {

        Integer minNode = null;
        Integer highNode = A[0];
        Queue<Integer> depths = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 1; i < A.length; i++) {
            //we are going up

            if (A[i] > A[i - 1]) {
                if (A[i] > highNode && minNode != null) {
                    //new high, highest altitude, so entering new valley
                    int depth = highNode - minNode;
                    depths.offer(depth);
                    highNode = A[i];
                    minNode = null;
                } else if (A[i] <= highNode && minNode != null) {
                    //going up, though we are still in the valley
                    if (A[i - 1] > minNode) {
                        int depth = A[i] - minNode;
                        depths.offer(depth);
                    } else {
                        int depth = A[i] - A[i - 1];
                        depths.offer(depth);
                    }
                }
                if (A[i] > highNode) {
                    //we need this for boundary conditions
                    highNode = A[i];
                }
            } else {
                //we are going down
, lets evaluate our min node.
                if ((minNode == null) || A[i] < minNode) {
                    minNode = A[i];
                }
            }
        }
        if (depths.size() > 0) {
            return depths.poll();
        }
        return 0;
    }

    public static void main(String[] args) {
        FloodDepth floodDepth = new FloodDepth();
        int depth = floodDepth.solution(new int[] {1, 3, 2, 1, 2, 1, 5, 3, 3, 4, 2});
        System.out.println(depth);

        depth = floodDepth.solution(new int[]{100000000, 1, 2, 99999999});
        System.out.println(depth);
    }
}

TapeEquillibrium

| Masuma

Solution:

This java solution to the codility problem TapeEquillibrium scored 100%

Logic: First find the sum of all the integers in the array. Then start to iterate over from first partition point being the first position until the second last item and calculate the left sum and the right sum. Find the difference between them and compare it with the minimum difference so far calculated, if its less than that then set the minimum difference to this new lower value..continue.

With the end of the for loop the correct minimum difference is reached. Return that!

Also check out the Math functions..they are so convenient! abs and min!

    public int solution(int[] A) {
        long totalSum=0;
        int minDifference = Integer.MAX_VALUE;
        for (int i=0; i<A.length;i++) {
            totalSum = totalSum + A[i];
        }
        long leftSum = 0;
        long rightSum = 0;
        for (int i=0; i<A.length - 1; i++) {
            leftSum = leftSum + A[i];
            rightSum = totalSum - leftSum;
            int currentDifference = (int) Math.abs(leftSum - rightSum);
            minDifference = Math.min(currentDifference, minDifference);
        }
        return minDifference;
    }

PermMissingElem

| Masuma

Solution:

This java solution to codility problem PermMissingElem scored a 100%

Logic: Iterate over the array and add the elements to a set on which you can do a contains operation. Iterate over the hashset for the first n+1 numbers and if when a specific number is not found in the hashset then that is the missing element.

import java.util.HashSet;
import java.util.Set;
class PermMissingElement{
    public int solution(int[] A) {
        int n = A.length + 1;
        int missingNumber = 0;
        Set<Integer> values = new HashSet<>();
        for (int i=0; i<A.length; i++) {
            values.add(A[i]);
        }
        for (int i=1; i<=n; i++) {
            if (!values.contains(i)) {
                missingNumber = i;
            }
        }
        return missingNumber;
    }
}

Solution 2:

This java solution scored 80% as it failed with larger length (~100,000)

Logic: Calculate the sum of the first n+1 natural numbers. Then iterate over the array and deduct the value from the sum. Whats left of the sum is the missing number. But aha fails with bigger ranges..

    
class PermMissingElement{
   public int solution1(int[] A) {

        int n = A.length + 1;
        long sumOfFirstN = n * (n+1)/2;
        for (int i=0; i<A.length; i++) {
            sumOfFirstN = sumOfFirstN - A[i];
        }
        return (int)(sumOfFirstN);
    }
}

FrogJmp

| Masuma

Solution

This java solution to codility problem FrogJmp scored 100%

Logic: Find the distance between X and Y, then divide that distance by the hop size that is D. If there is remainder then one more hop is needed so add 1 to the hops. Return the hops. Can you make this better?

public class FrogJump {

    //Detected time complexity : 0(1)
    public int solution(int X, int Y, int D){
        int distance = Y - X;
        int hops = distance/D;

        if (distance%D >0) {
            hops++;
        }
        return hops;
    }

}

OddOccurrencesInArray

| Masuma

Solution

This java solution to codility problem OddOccurrencesInArray scored 100%

Logic: Iterate over the elements, one by one, add the element to a set only if it does not exist in the set, if it exists then remove the element. At the end of the iteration only the unpaired element will remain in the set and that is what you return. Can you make this better?

import java.util.HashSet;
import java.util.Set;

//Detected time complexity:
//O(N) or O(N*log(N))
public class OddOccurrencesInArray {

    public int solution(int[] A) {
        Set<Integer> values = new HashSet<>();
        for (int i = 0; i<A.length; i++) {
            if (values.contains(A[i])) {
                values.remove(A[i]);
            } else {
                values.add(A[i]);
            }
        }
        return values.iterator().next();
    }
}