FloodDepth

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

Substring Size K

Problem:

Given a string s and an int k, return all unique substrings of s of size k with k distinct characters.

Example 1:

Input: s = "abcabc", k = 3
Output: ["abc", "bca", "cab"]

Example 2:

Input: s = "abacab", k = 3
Output: ["bac", "cab"]

Example 3:

Input: s = "awaglknagawunagwkwagl", k = 4
Output: ["wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag"]
Explanation: 
Substrings in order are: "wagl", "aglk", "glkn", "lkna", "knag", "gawu", "awun", "wuna", "unag", "nagw", "agwk", "kwag", "wagl" 
"wagl" is repeated twice, but is included in the output once.

Constraints:

  • The input string consists of only lowercase English letters¬†[a-z]
  • 0 ‚ȧ¬†k¬†‚ȧ 26

Solution:

Logic:

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

public class SusbstringSizeK {

    public static void printUniqueSubstrings(String s, int k) {

        if (k <= s.length()) {
            Set<Character> uniqueCharacters = new HashSet<>();
            Set<String> uniqueSubstrings = new HashSet<>();
            for (int i = 0; i <= s.length() - k; i++) {
                String shorterString = s.substring(i, i + k);
                for (int j = 0; j < k; j++) {
                    uniqueCharacters.add(shorterString.charAt(j));
                }
                if (uniqueCharacters.size() == k) {
                    uniqueSubstrings.add(shorterString);
                }
                uniqueCharacters.clear();
            }
            uniqueSubstrings.stream().forEach(value -> System.out.println(value));
        }
    }

    public static void main(String[] args) {
        printUniqueSubstrings("abcabc", 3);
        printUniqueSubstrings("awaglknagawunagwkwagl", 4);
    }
}

Partition Labels

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:

  • S¬†will have length in range¬†[1, 500].
  • S¬†will consist of lowercase English¬†letters ('a'¬†to¬†'z') only.

Solution:

Logic:

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class PartitionLabels {

    public static List<Integer> partitionLabels(String S) {
        List<Character> values = new ArrayList<>();

        for (int i=0; i< S.length(); i++) {
            if (!values.contains(S.charAt(i))) {
                values.add(S.charAt(i));
            }
        }

        List<String> partitions = new ArrayList<>();
        int partitionBegin = S.indexOf(values.get(0));
        int partitionEnd = S.lastIndexOf(values.get(0));


        for(int i=1; i< values.size(); i++) {
            int startIndex = S.indexOf(values.get(i));
            int endIndex = S.lastIndexOf(values.get(i));
            if ((startIndex> partitionEnd)) {
                partitions.add(S.substring(partitionBegin, partitionEnd + 1));
                partitionBegin = startIndex;
                partitionEnd = endIndex;
            } else if (endIndex > partitionEnd) {
                partitionEnd = endIndex;
            }
        }
        partitions.add(S.substring(partitionBegin, partitionEnd + 1));
        partitions.stream().forEach(x -> System.out.print(x + " " ));
        return partitions.stream().map(x -> x.length()).collect(Collectors.toList());
    }

    public static void main(String[] args) {
        List<Integer> values = partitionLabels("ababcbacadefegdehijhklij");
        values.stream().forEach(x -> System.out.print(x + " " ));
    }
}

Amazon Fresh Promotion

Problem:

Amazon Fresh is running a promotion in which customers receive prizes for purchasing a secret combination of fruits. The combination will change each day, and the team running the promotion wants to use a code list to make it easy to change the combination. The code list contains groups of fruits. Both the order of the groups within the code list and the order of the fruits within the groups matter. However, between the groups of fruits, any number, and type of fruit is allowable. The term “anything” is used to allow for any type of fruit to appear in that location within the group.
Consider the following secret code list: [[apple, apple], [banana, anything, banana]]
Based on the above secret code list, a customer who made either of the following purchases would win the prize:
orange, apple, apple, banana, orange, banana
apple, apple, orange, orange, banana, apple, banana, banana
Write an algorithm to output 1 if the customer is a winner else output 0.

Input
The input to the function/method consists of two arguments:
codeList, a list of lists of strings representing the order and grouping of specific fruits that must be purchased in order to win the prize for the day.
shoppingCart, a list of strings representing the order in which a customer purchases fruit.
Output
Return an integer 1 if the customer is a winner else return 0.
Note
‘anything’ in the codeList represents that any fruit can be ordered in place of ‘anything’ in the group. ‘anything’ has to be something, it cannot be “nothing.”
‘anything’ must represent one and only one fruit.
If secret code list is empty then it is assumed that the customer is a winner.

Example 1:

Input: codeList = [[apple, apple], [banana, anything, banana]] shoppingCart = [orange, apple, apple, banana, orange, banana]
Output: 1
Explanation:
codeList contains two groups - [apple, apple] and [banana, anything, banana].
The second group contains 'anything' so any fruit can be ordered in place of 'anything' in the shoppingCart. The customer is a winner as the customer has added fruits in the order of fruits in the groups and the order of groups in the codeList is also maintained in the shoppingCart.

Example 2:

Input: codeList = [[apple, apple], [banana, anything, banana]]
shoppingCart = [banana, orange, banana, apple, apple]
Output: 0
Explanation:
The customer is not a winner as the customer has added the fruits in order of groups but group [banana, orange, banana] is not following the group [apple, apple] in the codeList.

Example 3:

Input: codeList = [[apple, apple], [banana, anything, banana]] shoppingCart = [apple, banana, apple, banana, orange, banana]
Output: 0
Explanation:
The customer is not a winner as the customer has added the fruits in an order which is not following the order of fruit names in the first group.

Example 4:

Input: codeList = [[apple, apple], [apple, apple, banana]] shoppingCart = [apple, apple, apple, banana]
Output: 0
Explanation:
The customer is not a winner as the first 2 fruits form group 1, all three fruits would form group 2, but can't because it would contain all fruits of group 1.

Solution:

Logic:

public class FindFruitCombo {

    public static int winPrize(String[][] codeList, String[] shoppingCart) {
        // checking corner cases
        if(codeList == null || codeList.length == 0)
            return 1;
        if(shoppingCart == null || shoppingCart.length == 0)
            return 0;

        int i = 0, j = 0;
        while (i < codeList.length && j + codeList[i].length <= shoppingCart.length) {
            boolean match = true;
            for (int k = 0; k < codeList[i].length; k++) {
                if (!codeList[i][k].equals("anything") && !shoppingCart[j+k].equals(codeList[i][k])) {
                    match = false;
                    break;
                }
            }
            if (match) {
                j += codeList[i].length;
                i++;
            } else {
                j++;
            }
        }
        return (i == codeList.length) ? 1 : 0;
    }

    public static void test(String[][] codeList, String[] shoppingCart, int expect) {
        System.out.println(winPrize(codeList, shoppingCart) == expect);
    }

    public static void main(String[] args) {
        // test cases
        String[][] codeList1 = { { "apple", "apple" }, { "banana", "anything", "banana" } };
        String[] shoppingCart1 = {"orange", "apple", "apple", "banana", "orange", "banana"};
        String[][] codeList2 = { { "apple", "apple" }, { "banana", "anything", "banana" } };
        String[] shoppingCart2 = {"banana", "orange", "banana", "apple", "apple"};
        String[][] codeList3 = { { "apple", "apple" }, { "banana", "anything", "banana" } };
        String[] shoppingCart3 = {"apple", "banana", "apple", "banana", "orange", "banana"};
        String[][] codeList4 = { { "apple", "apple" }, { "apple", "apple", "banana" } };
        String[] shoppingCart4 = {"apple", "apple", "apple", "banana"};
        String[][] codeList5 = { { "apple", "apple" }, { "banana", "anything", "banana" } };
        String[] shoppingCart5 = {"orange", "apple", "apple", "banana", "orange", "banana"};
        String[][] codeList6 = { { "apple", "apple" }, { "banana", "anything", "banana" }  };
        String[] shoppingCart6 = {"apple", "apple", "orange", "orange", "banana", "apple", "banana", "banana"};
        String[][] codeList7= { { "anything", "apple" }, { "banana", "anything", "banana" }  };
        String[] shoppingCart7 = {"orange", "grapes", "apple", "orange", "orange", "banana", "apple", "banana", "banana"};
        String[][] codeList8 = {{"apple", "orange"}, {"orange", "banana", "orange"}};
        String[] shoppingCart8 = {"apple", "orange", "banana", "orange", "orange", "banana", "orange", "grape"};
        String[][] codeList9= { { "anything", "anything", "anything", "apple" }, { "banana", "anything", "banana" }  };
        String[] shoppingCart9 = {"orange", "apple", "banana", "orange", "apple", "orange", "orange", "banana", "apple", "banana"};

        // test
        test(codeList1, shoppingCart1, 1);
        test(codeList2, shoppingCart2, 0);
        test(codeList3, shoppingCart3, 0);
        test(codeList4, shoppingCart4, 0);
        test(codeList5, shoppingCart5, 1);
        test(codeList6, shoppingCart6, 1);
        test(codeList7, shoppingCart7, 1);
        test(codeList8, shoppingCart8, 1);
        test(codeList9, shoppingCart9, 1);
    }
}

Minimum Cost to Connect Ropes

Problem:

Given n ropes of different lengths, we need to connect these ropes into one rope. We can connect only 2 ropes at a time. The cost required to connect 2 ropes is equal to sum of their lengths. The length of this connected rope is also equal to the sum of their lengths. This process is repeated until n ropes are connected into a single rope. Find the min possible cost required to connect all ropes.

Example 1:

Input: ropes = [8, 4, 6, 12]
Output: 58
Explanation: The optimal way to connect ropes is as follows
1. Connect the ropes of length 4 and 6 (cost is 10). Ropes after connecting: [8, 10, 12]
2. Connect the ropes of length 8 and 10 (cost is 18). Ropes after connecting: [18, 12]
3. Connect the ropes of length 18 and 12 (cost is 30).
Total cost to connect the ropes is 10 + 18 + 30 = 58

Example 2:

Input: ropes = [20, 4, 8, 2]
Output: 54

Example 3:

Input: ropes = [1, 2, 5, 10, 35, 89]
Output: 224

Example 4:

Input: ropes = [2, 2, 3, 3]
Output: 20

Solution:

Logic:

This is rather simple. Here you push all the elements in a PriorityQueue, which on polling will return the values in ascending order (as it applies the natural ordering for integers as priority).

So as you go over the priority queue, you always pick the two smallest rope segments, join them and put them the joined rope segement back in the priority queue..at last you are left with one joined rope segment and one loose rope segment which you join to form the full connected rope and also during the process keep a log of the minimum cost by adding the values to it at every join.

Got that? I would maybe later on do an illustration..that would be fun! For now check out the code below.

import java.util.PriorityQueue;

public class MinCostToConnectRopes {

    private static int minCost(int[] ropes) {
        PriorityQueue<Integer> values = new PriorityQueue<>();
        for (int i=0; i<ropes.length; i++) {
            values.offer(ropes[i]);
        }
        int minCost = 0;
        while (values.size() != 1) {
            int value1 = values.poll();
            int value2 = values.poll();
            minCost = minCost + value1 + value2;
            values.offer(value1 + value2);
        }
        return minCost;
    }

    public static void main (String[] args) {
        System.out.println(minCost(new int[]{8, 4, 6, 12}));
    }
}

Critical Routers

Problem:

You are given an undirected connected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all articulation points in the given graph.

Input:
The input to the function/method consists of three arguments:

  • numNodes, an integer representing the number of nodes in the graph.
  • numEdges, an integer representing the number of edges in the graph.
  • edges, the list of pair of integers – A, B representing an edge between the nodes A and B.

Output:
Return a list of integers representing the critical nodes.

Example:

Input: numNodes = 7, numEdges = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]

Solution:

Logic:

  • First find all the numbers in the connected graph into a unique set
  • Order the list of pairs such in ascendence of the first pair element.
  • For every element in the unique set,
    • find all the connected edges (pairs) which does not contain this element
    • Pick the first pair from these and build a list of all the elements that can be reached for this pair.
    • Then check if this list size is one less than the size of the unique elements, if so that means the graph is connected, if not then this element is critical. Add this element to the connections set
  • Return the list of these connections.

You with me? critical yeah!

import java.util.*;

public class CriticalRouters {

    public static void main(String[] args) {
        List<PairInteger> pairs = new ArrayList<>();
        pairs.add(new PairInteger(0, 1));
        pairs.add(new PairInteger(0, 2));
        pairs.add(new PairInteger(1, 3));
        pairs.add(new PairInteger(2, 3));
        pairs.add(new PairInteger(2, 5));
        pairs.add(new PairInteger(5, 6));
        pairs.add(new PairInteger(3, 4));

        Set<Integer> vertexes = criticalRoutersList(7, 7, pairs);
        for (Integer v : vertexes) {
            System.out.print(" " + v + ", ");
        }

    }

    public static Set<Integer> criticalRoutersList(int nodesNum, int edgesNum, List<PairInteger> pairs) {
        Set<Integer> uniqueSet = new HashSet<>();
        Set<Integer> connections = new HashSet<>();
        Collections.sort(pairs, (a, b) -> Integer.compare(a.first, b.first));
        pairs.stream().forEach(list -> {
            uniqueSet.add(list.first);
            uniqueSet.add(list.second);
        });

        for (Integer value : uniqueSet) {
            List<PairInteger> newPairs = new ArrayList<>();
            for (PairInteger paire : pairs) {
                if (paire.first != value && paire.second != value) {
                    newPairs.add(paire);
                }
            }
            Set<Integer> buildList = new TreeSet<>(Arrays.asList(newPairs.get(0).first, newPairs.get(0).second));
            for (int inner = 1; inner < newPairs.size(); inner++) {
                mergeTag(buildList, newPairs.get(inner));
            }
            if (buildList.size() < uniqueSet.size() - 1) {
                connections.add(value);
            }
        }

        return connections;

    }


    private static void mergeTag(Set<Integer> buildList, PairInteger pairString) {
        if (buildList.contains(pairString.first) && buildList.contains(pairString.second))
            return;
        if (buildList.contains(pairString.first)) {
            buildList.add(pairString.second);
        } else if (buildList.contains(pairString.second)) {
            buildList.add(pairString.first);
        }
    }
}

public class PairInteger {
    int first;
    int second;

    public PairInteger(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

TapeEquillibrium

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

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

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

}