CareerCup

Take this, super easy, No need to read long post. Apply same logic we apply for binary tree.

**
     * *                             10
     * *
     * *                 2           20              12
     * *
     * *         1           7    8      9       21  24  25
     * *
     * * Serialized: 10,$,2,20,12,$,1,7, $, 8, 9,  $, 21, 24 , 25, $
     * *
     *
     * @param root
     * @return
     */
    @Override
    public String serialize(NArrayTreeNode root) {
        if (root == null)
            return "";

        final String levelSep = NULL_INDICATOR + SEPARATOR;
        Queue<NArrayTreeNode> queue = new LinkedList<>();

        StringBuilder serialize = new StringBuilder();


        queue.offer(root);
        serialize.append(root.val);
        serialize.append(SEPARATOR).append(levelSep); //Defines the Level end

        while (!queue.isEmpty()) {

            NArrayTreeNode treeNode = queue.poll();

            if (treeNode.children != null) {
                for (NArrayTreeNode child : treeNode.children) {
                    serialize.append(child.val);
                    serialize.append(SEPARATOR);
                    queue.offer(child);
                }
                serialize.append(levelSep); //Defines the Level end
            }
        }
        serialize.setLength(serialize.length() - 1); //Remove last ,

        return serialize.toString();
    }

    /**
     * *                             10
     * *
     * *                 2           20              12
     * *
     * *         1           7    8      9       21  24  25
     * *
     * * Serialized: 10,$,2,20,12,$,1,7, $, 8, 9,  $, 21, 24 , 25, $
     * *
     *
     * @return
     */
    @Override
    public NArrayTreeNode deserialize(String data) {
        if (data == null || data.isEmpty())
            return null;

        NArrayTreeNode root = new NArrayTreeNode();

        int index = 0;

        String[] content = data.split(SEPARATOR);
        root.val = Integer.parseInt(content[index++]);

        Queue<NArrayTreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty() && index < content.length - 1) {

            NArrayTreeNode node = queue.poll();
            index++;

            while (!content[index].equals(NULL_INDICATOR)) {
                if (node.children == null)
                    node.children = new ArrayList<>();

                NArrayTreeNode child = new NArrayTreeNode();
                child.val = Integer.parseInt(content[index++]);
                node.children.add(child);

                queue.offer(child);
            }


        }

        return root;
    }

Here is the solution

class Node implements Comparable<Node> {
    int sum, ai, bi;

    public Node(int s, int a, int b) {
        this.sum = s;
        this.ai = a;
        this.bi = b;
    }

    @Override
    public int compareTo(Node o) {
        return this.sum - o.sum;
    }

    @Override
    public String toString() {
        return "Node{" +
                "sum=" + sum +
                ", ai=" + ai +
                ", bi=" + bi +
                '}';
    }
}



/**
 * Duplicate sum Not allowed
 * Algo:
 * 1. create all the sum nodes for a[i] + b[0]
 * 2. Build priority queue using above nodes
 * 3. For each poll
 * *    3.1: Insert the appropriate pair in PQ either a[i+1]+b[j] or a[i]+b[j+1] if not seen as pair, not seen as sum
 *
 * Time Complexity:  N length of a[], M length of b[]
 * Step 1: O(N)
 * Step 2: O(N) Priority queue could be build in O(n)
 * step 3: In worst case, all the sum are unique and we need to find the last element. This case PQ will contain max(N,M)+1 elements since we remove 1 and add 2 so effectively adding 1 element.
 * That takes O(log(Max(N,M)) time run for n times { n= nth sum element}
 * O(n * log(Max(N,M) )
 *
 * O(N) + O(N) + O(n * log(Max(N,M) )  => O(n * log(Max(N,M) )
 *
 * Space: O(Max(N,M))
 *
 */
class SolutionNthItemInSumOfTwoArraysDuplicateSumNotAllowed {


    public int nthItem(int[] a, int[] b, int n) {

        if (a == null || a.length == 0) {
            if (b.length >= n)
                return b[n - 1];
            else
                return Integer.MIN_VALUE;
        }

        if (b == null || b.length == 0) {
            if (a.length >= n)
                return a[n - 1];
            else
                return Integer.MIN_VALUE;
        }

        return nthItem(a, b, a.length, b.length, n);
    }


    private int nthItem(int[] a, int[] b, int aLength, int bLength, int n) {


        Set<int[]> seenPair = new HashSet<>();
        Set<Integer> sumSeen = new HashSet<>();
        List<Node> nodes = new ArrayList<>();

        //O(aLength)
        for (int i = 0; i < a.length; i++) {
            int sum = a[i] + b[0];
            if (!sumSeen.contains(sum)) {
                nodes.add(new Node(a[i] + b[0], i, 0));
                sumSeen.add(sum);
                seenPair.add(new int[]{i, 0});
            }
        }

        //O(aLength)
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(nodes);

        int i = 0;
        Node currentPair = null;


        while (i < n && !priorityQueue.isEmpty()) {

            currentPair = priorityQueue.poll();

            int[] pairWithA = {currentPair.ai + 1, currentPair.bi};
            int[] pairWithB = {currentPair.ai, currentPair.bi + 1};

            if (!seenPair.contains(pairWithA) && currentPair.ai + 1 < aLength && !sumSeen.contains(a[currentPair.ai + 1] + b[currentPair.bi])) {
                seenPair.add(pairWithA);
                sumSeen.add(a[currentPair.ai + 1] + b[currentPair.bi]);
                priorityQueue.offer(new Node(a[currentPair.ai + 1] + b[currentPair.bi], currentPair.ai + 1, currentPair.bi));
            }

            if (!seenPair.contains(pairWithB) && currentPair.bi + 1 < bLength && !sumSeen.contains(a[currentPair.ai] + b[currentPair.bi + 1])) {
                seenPair.add(pairWithA);
                sumSeen.add(a[currentPair.ai] + b[currentPair.bi + 1]);
                priorityQueue.offer(new Node(a[currentPair.ai] + b[currentPair.bi + 1], currentPair.ai, currentPair.bi + 1));
            }
            i++;

        }

        if (i < n)
            return Integer.MAX_VALUE;
        assert currentPair != null;
        return currentPair.sum;
    }
}

You code produce wrong ouptut,
Take this case
a[] {2,3,4,5} and target 18
your code would produce null
whereas the output is
(((2*5)-4)*3)=18

but if you say that () allowed only once, then
with example: {1, 3, 4,6}, target: 12
Your code produce
6+(4+(3-1)) = 12
Which usese multiple ()

I solved this problem in varies ways [ we can also use trie to solve this ]

public class BuildStringWordsInDictionary {

    public static void main(String args[]) {
        test1();
        test2();
        test3();
        test4();
        test5();


    }

    //false
    private static void test5() {
        String s = "abcabab";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 1);


        System.out.println("\nGiven String : " + s + " Expected output :" + false);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));

    }

    //true
    private static void test4() {
        String s = "abcabab";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }

    //false
    private static void test3() {
        String s = "abcx";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + false);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }

    //true
    private static void test1() {

        String s = "abcabcabcabca";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 2);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));
    }


    //true
    private static void test2() {

        String s = "abcabcaabbc";
        HashMap<String, Integer> wordCount = new HashMap<>();
        wordCount.put("abc", 3);
        wordCount.put("ab", 1);
        wordCount.put("abca", 1);

        System.out.println("\nGiven String : " + s + " Expected output :" + true);
        System.out.println("SolutionDFSByStringWords ->" + SolutionDFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords2 -> " + SolutionDFSByStringWords.wordBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionBFSByStringWords -> " + SolutionBFSByStringWords.canBreak(s, new HashMap<>(wordCount)));
        System.out.println("SolutionDFSByMapWords -> " + SolutionDFSByMapWords.canBreak(s, new HashMap<>(wordCount)));


    }


}


/**
 * NOTE: Not working
 */
class SolutionBFSByStringWords {


    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakBFS(str, wordCount);


    }

    private static boolean canBreakBFS(String str, Map<String, Integer> wordCount) {

        int n = str.length();
        final Queue<Integer> queue = new LinkedList<>();

        final Map<String, Integer> visited = new HashMap<>();

        queue.offer(0);

        while (!queue.isEmpty()) {

            int start = queue.poll();

            for (int i = start ; i < str.length(); i++) {

                //Try this word : forward ->
                String temp = str.substring(start, i + 1);

                if (!visited.containsKey(temp))
                    visited.put(temp, 0);

                //Check is this possible ?
                if (wordCount.containsKey(temp) && wordCount.get(temp) > visited.get(temp)) {

                    visited.put(temp, visited.get(temp) + 1);

                    //if possible,the remove this string and recurse for rest of the string;
                    wordCount.put(temp, wordCount.get(temp) - 1);

                    //recurse for rest of the string;
                    queue.offer(i);

                    if (i == str.length())
                        return true;


                }
            }

        }


        return false;
    }
}

/**
 * This solution won't handle the cases when you can remove the word in-between and form a new workd by ends
 * Example:
 * s = "abcabcaabbc";
 * {"abc": 3, "ab": 1, "abca": 1}
 * <p>
 * Your code produce False where it is possible ;
 * abcabcaabbc -> aabbc [remove two "abc"] {"abc": 1, "ab": 1, "abca": 1}
 * aabbc -> abc [remove one "ab" ] {"abc": 1, "ab": 0, "abca": 1} [**** This is not supported ***]
 * abc -> "" [ remove one "abc" ] {"abc": 0, "ab": 1, "abca": 1}
 */
class SolutionDFSByStringWords {


    /**
     * DFS 1:
     * By keeping the index of recursion
     *
     * @param str
     * @param wordCount
     * @return
     */
    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakRec(str, wordCount, 0);


    }

    /**
     * Keep taking a sub-string from given string specified by "start" index and keep checking does this is possible break
     * which leads to a solution
     *
     * @param str
     * @param wordCount
     * @param start
     * @return
     */
    private static boolean canBreakRec(String str, Map<String, Integer> wordCount, int start) {

        //If we have remove all the chars, then success
        if (start == str.length())
            return true;

        for (int i = start; i < str.length(); i++) {

            //Try this word : forward ->
            String temp = str.substring(start, i + 1);

            //Check is this possible ?
            if (wordCount.getOrDefault(temp, -1) > 0) {

                //if possible,the remove this string and recurse for rest of the string;
                wordCount.put(temp, wordCount.get(temp) - 1);

                //recurse for rest of the string;
                if (canBreakRec(str, wordCount, i + 1)) {
                    return true;
                }
                //Couldn't find the solution, backtrack
                wordCount.put(temp, wordCount.get(temp) + 1);

            }


        }

        return false;
    }


    /**
     * DFS 2
     * By breaking string into sub-strings
     *
     * @param word
     * @param map
     * @return
     */

    public static boolean wordBreak(String word, Map<String, Integer> map) {
        int len = word.length();
        if (len <= 0) return true;
        for (int i = 1; i < len + 1; i++) {
            String a = word.substring(0, i);
            Integer I = map.get(a);
            if (I == null || I <= 0)
                continue;

            map.put(a, I - 1);

            if (i <= len && wordBreak(word.substring(i, len), map))
                return true;

            map.put(a, I);
        }
        return false;
    }
}


class SolutionDFSByMapWords {


    public static boolean canBreak(String str, Map<String, Integer> wordCount) {

        if (str.isEmpty())
            return true;

        return canBreakRec(str, wordCount);


    }

    /**
     * DFS the tree.
     * check using current count in map of a word, does string can be broken ?
     * if yes, then decrease the number of counts and recurse for further. Try all
     *
     * @param str
     * @param wordCount
     * @return
     */
    private static boolean canBreakRec(String str, Map<String, Integer> wordCount) {
        if (str.isEmpty())
            return true;

        /**
         * find all the keys present in str and remove them as many times as said
         */
        for (String key : wordCount.keySet()) {


            int count = wordCount.get(key);

            //Can we still use this word from dict?
            if (count > 0) {

                int oldCount = count;

                String oldString = str;

                //Find and remove the occurrence
                while (str.contains(key) && count > 0) {
                    str = str.replaceFirst(key, "");
                    count--;
                }

                //if we tried to remove but no occurrence found for given key in string, then continue to next word in map
                if (count == wordCount.get(key))
                    continue;
                else {

                    //decrease the count of occurrence
                    wordCount.put(key, count);

                    //Recurse
                    if (canBreakRec(str, wordCount)) {
                        return true;
                    }

                    //Put back: Backtrack
                    str = oldString;
                    wordCount.put(key, oldCount);

                }


            }

        }
        return false;
    }

}

another way would be using modulo

/**
             *  considers the last N values.
             */
//            if (this.size < this.maxSize)
//                return ((double) sum / this.size); //Note here we divide by the current size of array
//            else
//                return ((double) sum / this.maxSize); //Note here we divide by the max size of array

            //considers the last N values.
            return (double) sum / (this.size % (this.maxSize + 1));

public double getAverage(int item) {

            this.sum += item;

            //if this reach max sized then, remove head element from sum
            if (this.size == maxSize) {

                this.sum -= circularQueue[head];

                //proceed the head pointer to next cell
                head = (head + 1) % this.maxSize;
            } else {
                //update this size
                this.size++;
            }

            //add this element in queue
            circularQueue[tail] = item;
            tail = (tail + 1) % this.maxSize;

            /**
             *  considers the last N values.
             */
            if (this.size < this.maxSize)
                return ((double) sum / this.size); //Note here we divide by the current size of array
            else
                return ((double) sum / this.maxSize); //Note here we divide by the max size of array

        }

I think this is against the question.
Question says "consider last N values" and you are considering all values in the given array using Size.
You should divide based on either N or current size ( when current size is < N )

instead do like this

private static List<Integer> interleavedListSimple(List<List<Integer>> lists) {

        List<Integer> interleaveList = new ArrayList<>();

        int maxSize = 0;

        for (List<Integer> list : lists)
            maxSize = Math.max(maxSize, list.size());

        int index = 0;
        while (index < maxSize) {
            for (int i = 0; i < lists.size(); i++) {
                if (index < lists.get(i).size()) {
                    interleaveList.add(lists.get(i).get(index));
                }
            }
            index++;
        }


        return interleaveList;
    }

Another version of easy code ;

private static List<Integer> interleavedListSimple(List<List<Integer>> lists) {

        List<Integer> interleaveList = new ArrayList<>();

        int maxSize = 0;

        for (List<Integer> list : lists)
            maxSize = Math.max(maxSize, list.size());

        int index = 0;
        while (index < maxSize) {
            for (int i = 0; i < lists.size(); i++) {
                if (index < lists.get(i).size()) {
                    interleaveList.add(lists.get(i).get(index));
                }
            }
            index++;
        }


        return interleaveList;
    }

here is the correct code

private static List<Integer> interleavedListSimple(List<List<Integer>> lists) {

        List<Integer> interleaveList = new ArrayList<>();

        int maxSize = 0;

        for (List<Integer> list : lists)
            maxSize = Math.max(maxSize, list.size());

        int index = 0;
        while (index < maxSize) {
            for (int i = 0; i < lists.size(); i++) {
                if (index < lists.get(i).size()) {
                    interleaveList.add(lists.get(i).get(index));
                }
            }
            index++;
        }


        return interleaveList;
    }

Code is wrong; this assume the last list is always greater then other list size;
try below input
[[1,2,3], [9,0],[5,9], [-4] ]

output you produce is
[1, 9, 5, -4, 2, 0, 9]
where as it should be
[1, 9, 5, -4, 2, 0, 9, 3]

Here is my solution, works in all corner cases... well tested

public class ListCombination {

    public static void main(String args[]) {


        Map<String, char[]> input = new HashMap<>();

        input.put("1", new char[]{'A', 'B', 'C'});
        input.put("2", new char[]{'D', 'E'});
        input.put("3", new char[]{'P', 'Q'});
        input.put("12", new char[]{'X'});
        input.put("4", new char[]{'T', 'S'});
        input.put("23", new char[]{'Z', 'N'});
        input.put("34", new char[]{'O', 'M'});
        input.put("234", new char[]{'W', 'Y'});
        input.put("1234", new char[]{'@', '#'});

        String test = "1234";
        try {
            List<String> output = generateCombination(input, test);
            System.out.println(output);



        } catch (InvalidArgument invalidArgument) {
            invalidArgument.printStackTrace();
        }


    }

    private static List<String> generateCombination(Map<String, char[]> input, String test) throws InvalidArgument {

        if (null == input || input.isEmpty() || null == test || test.isEmpty())
            return Collections.EMPTY_LIST;

        //Build list of string that need to traverse recursively
        List<List<String>> considerList = buildConsiderList(input, test);

        return considerList.stream().map(list -> generateCombination(list)).flatMap(Collection::stream).collect(Collectors.toList());

    }

    private static List<List<String>> buildConsiderList(Map<String, char[]> input, String pattern) throws InvalidArgument {

        List<List<String>> toConsider = new LinkedList<>();

        /**
         * Consider of key;
         * Here we use key a loop runner because we could have case where from pattern multiple (off different size) string present in input map,
         * then if we traverse over pattern then we need to generate n^2 sub string and check all of them in map, that corresponding list present or not
         */
        for (String key : input.keySet()) {

            List<String> subListsToConsider = new ArrayList<>();

            //If this key does not include in the first place of the pattern list, then don't consider all list by it
            //Example: Key = 2, pattern=123 -> since 123 does not start with 2, which means all the list by 2 we can't consider since it has to be like 123
            if (!pattern.startsWith(key))
                continue;

            //process for current key array
            char[] current = input.get(key);
            subListsToConsider.add(new String(current));

            //Take the remaining length to consider
            //example key = 1, pattern=123, then remaining is = 23 which we'll consider one by one
            String remainingPattern = pattern.substring(key.length());


            //Case 1: character by character
            //process remaining
            for (int i = 0; i < remainingPattern.length(); i++) {

                //if this does not present in input; input is corrupt
                if (!input.containsKey(String.valueOf(remainingPattern.charAt(i))))
                    throw new InvalidArgument("Input " + pattern + "is invalid");

                char[] temp = input.get(String.valueOf(remainingPattern.charAt(i)));
                subListsToConsider.add(new String(temp));


            }


            //case 2: whole remaining list
            if (remainingPattern.length() > 1 && input.containsKey(remainingPattern)) {
                List<List<String>> withRemaining = new ArrayList<>();
                List<String> rem = new ArrayList<>();
                rem.add(new String(input.get(key)));
                rem.add(new String(input.get(remainingPattern)));

                withRemaining.add(rem);
                toConsider.addAll(withRemaining);
            }

            toConsider.add(subListsToConsider);


        }

        return toConsider;
    }


    private static List<String> generateCombination(List<String> input) {
        List<String> output = new LinkedList<>();

        generateCombination(input, 0, output, "");
        return output;
    }

    private static void generateCombination(List<String> input, int index, List<String> output, String temp) {

        if (temp.length() == input.size()) {
            output.add(temp);
            return;
        }

        String current = input.get(index);

        for (int i = 0; i < current.length(); i++) {
            temp = temp + current.charAt(i);
            generateCombination(input, index + 1, output, temp);
            temp = temp.substring(0, temp.length() - 1);
        }
    }



}

using adr help;

public class ThiefInRoomOfSensors {

    static class Subsets {
        int parent;
        int rank;

        public Subsets(int parent, int rank) {
            this.parent = parent;
            this.rank = rank;
        }

        @Override
        public String toString() {
            return "{" +
                    "parent=" + parent +
                    ", rank=" + rank +
                    '}';
        }
    }

    static class GraphUnionFind {
        Subsets parent[];

        public GraphUnionFind(int nodes) {
            parent = new Subsets[nodes + 1]; //since id start from 1

            for (int i = 1; i <= nodes; i++) {
                parent[i] = new Subsets(i, 1);
            }

        }

        public int find(int i) {
            if (parent[i].parent == i)
                return i;
            return parent[i].parent = find(parent[i].parent);
        }

        public void union(int i, int j) {

            int p1 = find(i);
            int p2 = find(j);
            if (p1 != p2)
                if (parent[p1].rank < parent[p2].rank)
                    parent[p1].parent = p2;
                else if (parent[p1].rank > parent[p2].rank)
                    parent[p2].parent = p1;
                else {
                    parent[p2].parent = p1;
                    parent[p1].rank++;
                }


        }
    }


    static class Sensors {
        int id ;
        double x, y;
        double r;

        public Sensors(double x, double y, double r, int id) {
            this.x = x;
            this.y = y;
            this.r = r;
            this.id = id;
        }

        @Override
        public String toString() {
            return "{" +
                    "id=" + id +
                    ", x=" + x +
                    ", y=" + y +
                    ", r=" + r +
                    '}';
        }
    }

    static class Room {
        double height;
        double width;

        List<Sensors> sensors;

        public Room(int s, double h, double w) {
            sensors = new ArrayList<>(s);
            height = h;
            width = w;
        }

        public void putSensors(double x, double y, double r, int id) {
            sensors.add(new Sensors(x, y, r, id));
        }
    }

    public static void main(String args[]) {

        Room room = new Room(5, 1, 1);

        room.putSensors(0, 0, 0.5, 1);
        room.putSensors(0.5, 0.2, 0.5, 2);
        room.putSensors(0.7, 0.4, 0.5, 3);
        room.putSensors(0.6, 0.6, 0.5, 4);
        room.putSensors(1, 1, 0.5, 5);


        Room room2 = new Room(3, 1, 1);

        room2.putSensors(0, 0, 0.5, 1);
        room2.putSensors(0.5, 0.2, 0.5, 2);
        room2.putSensors(0.7, 0.4, 0.5, 3);


        System.out.println(canGoFromLeftToRight(room));
        System.out.println(canGoFromLeftToRight(room2));
    }

    private static boolean canGoFromLeftToRight(Room room) {
        double roomH = room.height;
        List<Sensors> sensors = room.sensors;


        List<Sensors> sensorsCoveringTop = new ArrayList<>();
        List<Sensors> sensorsCoveringBottom = new ArrayList<>();

        //Find that overlaps room height
        for (int i = 0; i < sensors.size(); i++) {
            Sensors s = sensors.get(i);

            if (s.y + s.r >= roomH) // overlap top; from the center of the sensors, if we add radius to its height(y) and its beyond or touch room height
                sensorsCoveringTop.add(s);

            if (s.y <= s.r) //overlap bottom; as y is the y-th coordinates, r is radius (as height) ; lets suppose height of room is H; then height of y coordinate is (H-y)
                            // remaining height is (H-(H-y)= y, hence y<=r then touches
                sensorsCoveringBottom.add(s);
        }

        if (sensorsCoveringBottom.isEmpty() || sensorsCoveringTop.isEmpty())
            //nothing overlaps;
            return true;

        //means either of them overlap, find the overlaps and combine them
        GraphUnionFind graphUnionFind = new GraphUnionFind(sensors.size());

        //Combine overlapping top sensors
        for (int i = 0; i < sensorsCoveringTop.size() - 1; i++) {
            Sensors x = sensorsCoveringTop.get(i);
            Sensors y = sensorsCoveringTop.get(i + 1);
            graphUnionFind.union(x.id, y.id);
        }

        //Combine overlapping bottom sensors
        for (int i = 0; i < sensorsCoveringBottom.size() - 1; i++) {
            Sensors x = sensorsCoveringBottom.get(i);
            Sensors y = sensorsCoveringBottom.get(i + 1);
            graphUnionFind.union(x.id, y.id);
        }

        //Combine overlapping top & bottom sensors
        for (int i = 0; i < sensors.size(); i++) {
            for (int j = i + 1; j < sensors.size(); j++) {

                //if they overlap
                Sensors x = sensors.get(i);
                Sensors y = sensors.get(j);

                if ((Math.pow((x.x - y.x), 2) + Math.pow((x.y - y.y), 2)) <= 4 * Math.pow(x.r, 2)) { //x^2 + y^2 <= 4*r^2
                    graphUnionFind.union(x.id, y.id);
                }
            }
        }
        return (graphUnionFind.find(sensorsCoveringTop.get(0).id) != graphUnionFind.find(sensorsCoveringBottom.get(0).id));
    }
}

Logic drive from simple math;
odd + odd = even
odd + even = odd
even + even = even
0 + even = even
0 + odd = odd

It should be post order traversal with below way of cal

If leaf
=>Item: odd
.      Return ( 0, value)
=> item : even
.      Return ( value, 0)

If not leaf
=> item even
    // through both child's creating max subtree
.    max = MAX ( max, MAX(left.even+ right.even, left.odd+ right.odd) + value) 

      return ( 
       even-> MAX ( MAX ( left.even, right.even) + value, value), 
	odd ->( left.odd, right.odd) + value ) 
       ) 

=> item odd
    // through both child's creating max subtree
.    max = MAX ( max, left.odd +  right.odd + value) 

      return ( 
       even-> ( left.odd, right.odd) + value), 
	odd -> MAX ( left.even, right.eve) + value, value ) 
       ) 

if any situation the value at odd position is even, then put 0 instead 
Like tree
  6 here even sum is not possible (6+2 = even, 6+4= even, 2+4+6 = even) not possible odd sum( 10,0)
2  4

Same for even.

Grt bro,
Its my dumbness even explaining her plenty of times, I did not see simple thing that only possible character is 1 more than the last character start FROM A.

Others pls see above explanation.

I think u missed the last part of question or I may not understood ur solution, pls elobrate

You can optimise further using Fibonacci numbers; o(logn) time

DP

package Java;

import java.util.Arrays;

/**
 * Author: Nitin Gupta
 * Date: 26/04/19
 * Description:
 */
public class NumberOfWaysToDecodeDigitSeq {


    public static void main(String args[]) {

        String s = "1212";

        System.out.println(ways(s));
    }

    private static int ways(String s) {
        if (s == null || s.isEmpty())
            return 0;

        int n = s.length();

        int count[] = new int[n + 1];

        Arrays.fill(count, 0);

        count[0] = 1; //every single character can be transform
        count[1] = 1;

        char digits[] = s.toCharArray();
        for (int i = 2; i <= n; i++) {

            if (digits[i - 1] > '0')
                count[i] += count[i - 1];

            if (digits[i - 2] == '1' || digits[i - 2] == '2' && digits[i - 1] < '7')
                count[i] += count[i - 2];
        }

        return count[n];
    }
}

Here is the correction and solution:
It easy, once you find the ending index, you need to backtrack it and find out where they were equal, the least index would be the starting point;

package Java;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 26/04/19
 * Description:
 */
public class EqualXandY {

    public static void main(String[] args) {
        int[] arr = {1, 5, 7, 6, 8, 5, 7, 6, 5, 7, 7, 5, 5, 7};
        print(arr, arr.length, 5, 7);


        int[] arr2 = {7, 42, 5, 6, 42, 8, 7, 5, 7, 6, 7};
        print(arr2, arr2.length, 7, 42);


        int[] arr3 = {7, 42, 5, 6, 42, 8, 7, 5, 3, 6, 7};
        print(arr3, arr3.length, 7, 42);


        int[] arr4 = {5, 6, 7, 42, 42, 8, 7, 5, 3, 6, 7};
        print(arr4, arr4.length, 7, 42);
    }


    public static void print(int arr[], int n, int X, int Y) {

        // counters for X and Y

        int nx = 0, ny = 0;


        int result = -1;
        int count = 0;
        int resultCount = 0;

        for (int i = 0; i < n; i++) {

            // If value is equal to X increment counter of X

            if (arr[i] == X)

                nx++;


            // If value is equal to X increment counter of X

            if (arr[i] == Y)

                ny++;


            // If counters are equal(but not zero) save

            // the result as i

            if ((nx == ny) && (nx != 0 && ny != 0)) {
                count = nx;
                result = i;
            }

        }

        nx = 0;
        ny = 0;
        resultCount = count;
        count = 2 * count;
        int start = -1;
        for (int i = result; i >= 0; i--) {

            if (arr[i] == X) {
                count--;
                nx++;
            }

            if (arr[i] == Y) {
                count--;
                ny++;
            }

            if (nx == ny)
                start = i;

            if (count == 0)
                break;

        }

        System.out.println("s : " + start + " end " + result + " total count : " + resultCount);


    }

}

outputs

s : 1 end 13 total count : 5
s : 0 end 7 total count : 2
s : 0 end 9 total count : 2
s : 2 end 9 total count : 2

You just gave bell number recursive eq. Which I already mentioned.

solution of approach 2; but still don't know how to do the improvement that i mentioned;

static int subArrays(int arr[], int k) {

        int count = 0;
        Set<Integer> set = new HashSet<>();

        //Count single length
        for (int i = 0; i < arr.length; i++) {
            count += set.contains(arr[i]) ? 0 : 1;
            set.add(arr[i]);
        }


        int s = 0;
        int oddCount = 0;

        int i = 0;
        for (; i < arr.length; i++) {

            if (arr[i] % 2 != 0)
                oddCount++;

            //count length > 1
            if (i - s > 0 && oddCount == k) {
                count++;
            }

            //Slide the window
            if (oddCount > k) {

                while (oddCount > k && s < i) {


                    if (arr[s] % 2 != 0)
                        oddCount--;
                    s++;

                    if (i - s > 0 && oddCount == k) {
                        count++;
                        break;

                    }

                }
            }
        }
        i--;

        //if left over array has more then 2 element, count them too
        while (i - s + 1 >= 2) {
            s++;
            if (i - s + 1 >= 2)
                count++;

        }


        return count;
    }

that i answered and coded too.

interviewer did not told about that neither i asked,
i believe its not important, you can assume some other character or numbers ...so its regardless
like we can use small alphabet (a,b,c) or numbers 1,2,3 etc

Here is some code;
Bruteforce and optimised;

package Java;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 16/04/19
 * Description:
 */
public class StringRotationMatch {

    static class Pair {
        String s1, s2;

        @Override
        public String toString() {
            return "{" + s1 + "," + s2 + '}';
        }

        public Pair(String s1, String s2) {
            this.s1 = s1;
            this.s2 = s2;
        }
    }

    public static void main(String args[]) {
        String[] arr1 = {"AB", "BC", "FOO", "ZA", "BAZ"};
        System.out.println(rotationPairsBruteForce(arr1));
        System.out.println(rotationPairs(arr1));

        String[] arr2 = {"AB", "BC", "FOO", "ZA", "BAZ", "CBA"};
        System.out.println(rotationPairsBruteForce(arr2));
        System.out.println(rotationPairs(arr2));
    }


    //O(Ln^2)
    private static List<Pair> rotationPairsBruteForce(String arr[]) {
        String str = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        List<Pair> out = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) { //O(n)
            for (int j = i + 1; j < arr.length; j++) { //O(n)
                if (i == j)
                    continue;

                String s1 = arr[i];
                String s2 = arr[j];

                if (s1.length() != s2.length())
                    continue;

                char c1 = s1.charAt(0);
                char c2 = s2.charAt(0);
                int diff = getDiff(c1, c2, str);
                int k;
                for (k = 1; k < s1.length(); k++) { //O(L)

                    if (diff != getDiff(s1.charAt(k), s2.charAt(k), str))
                        break;
                }

                if (k == s1.length()) {
                    out.add(new Pair(s1, s2));
                }

            }
        }
        return out;
    }

    private static int getDiff(char c1, char c2, String str) { //O(1)

        int index1 = str.indexOf(c1);
        int index2 = str.indexOf(c2);

        if (index2 < index1)
            return 26 - (index1 - index2);
        return index2 - index1;
    }

    //Optimized-> O(nL)
    private static List<Pair> rotationPairs(String[] arr) {

        List<Pair> out = new ArrayList<>();
        List<String> transformed = transform(arr); //O(nL)

        Map<String, List<Integer>> duplicates = new HashMap<>();

        int i = 0;
        //This loop will run at most O(n) time since in inner loop even all of them map to one entry only, then each element will touch at most 2 times
        for (String s : transformed) { //O(n)

            List<Integer> entries = duplicates.getOrDefault(s, new ArrayList<>());


            for (Integer entry : entries) {

                out.add(new Pair(arr[entry], arr[i]));
            }
            entries.add(i);
            duplicates.put(s, entries);
            i++;
        }


        return out;
    }

    //O(nL)
    private static List<String> transform(String ar[]) {
        List<String> transformed = new ArrayList<>();

        for (int i = 0; i < ar.length; i++) { //O(n)

            String x = ar[i];

            int delta = 'A' - x.charAt(0);

            StringBuilder str = new StringBuilder();
            for (int j = 0; j < x.length(); j++) { //O(L)
                char current = x.charAt(j);

                current = (char) ((int) current + delta);

                if (current < 'A')
                    current = (char) ((int) current + 26);

                str.append(current);
            }
            transformed.add(str.toString());
        }

        return transformed;

    }
}

for approach 2
O(mkn^2)

Complexity of last code is
O(mklogn) in worst case
as it might possible that single node is connected to all nodes in restricted list

No, don't check directly to k list (which will be O(k) ) rather build hash to set list; and then check

What is Hash to set List of K?
put a node as key and all node that it connects to as set being value in map
make sure you put in reverse way to
like
1,4
1,5

1 -> (4,5)
4->1
5->1

to check efficiently in k list

Complexity O(L* n^2)
L is max length of word.

You don't need to find rotation n all. Just find index of both character
Say cik and cjk obtained at index i and j of kth item.
Index of the is i1 and i2.
If i2 < i1 then
Return 26-(i1-i2)
Otherwise
Return i1-i2

Its not necessary that movie name that can concat occurs sequenceally

Here is the complete implementation of multi level cache

IMultiLevelCache api to client
----------------------

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public interface IMultiLevelCache<K extends CacheKey, V> {

    /**
     * this will add the element at a particular level along with from top to this level
     *
     * @param key
     * @param value
     */
    void add(K key, V value);

    Collection<V> remove(K key);

    V get(K key);

    void update(K key, V value);

    void show();
}


Cache key agreement 
---------------------

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public class CacheKey {

    private final int levelId;

    public CacheKey(int levelId) {
        this.levelId = levelId;
    }

    public int getLevelId() {
        return levelId;
    }

}

//Base cache using linkedHashMap LRU

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> implements Serializable {


    //Since this is lru cache, so if this cache get filed (over capacity), it will kick least recently used item.
    private int capacity;


    public LRUCache(int capacity) {
        // Call constructor of LinkedHashMap with accessOrder set to true to
        // achieve LRU Cache behavior
        super(capacity, 1.0f, true);
        this.capacity = capacity;
    }

    // Remove the eldest element whenever size of cache exceeds the capacity
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return (this.size() > capacity);
    }


}

//Multi level cache implementation 

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public final class MultiLevelCache<K extends CacheKey, V> implements IMultiLevelCache<K, V> {

    private int levels = 1;
    private int capacity;
    private Map<Integer, LRUCache<K, V>> multiLevelCache;
    private final int levelStart;
    private final int levelEnd;


    public MultiLevelCache(int levels, int capacity) {
        this.multiLevelCache = new HashMap<>(levels);
        this.levels = levels;
        this.capacity = capacity;
        this.levelStart = 10;
        this.levelEnd = levelStart * levels;
        init();
    }

    public MultiLevelCache(int capacity) {
        this.multiLevelCache = new HashMap<>(levels);
        this.levels = 1;
        this.capacity = capacity;
        this.levelStart = 10;
        this.levelEnd = levelStart * levels;
        init();
    }

    private final void init() {
        //Init all the cache at each level
        for (int i = levelStart; i <= levelEnd; i += levelStart) {
            multiLevelCache.put(i, new LRUCache<>(capacity));
        }

    }


    private final Set<Integer> getDesiredLevels(int ownLevel) {

        Set<Integer> desiredLevels = new HashSet<>();

        int expectedLevel = ownLevel % levelEnd;

        if (expectedLevel < levelStart) {
            desiredLevels.add(levelStart);
            return desiredLevels;
        }

        for (int l = levelStart; l <= levelEnd; l += levelStart) {


            if (expectedLevel > l) {
                desiredLevels.add(l);
            } else if (expectedLevel <= l) {
                desiredLevels.add(l);
                break;
            }

        }

        return desiredLevels;
    }

    @Override
    public void add(K key, V value) {
        int level = key.getLevelId();
        Set<Integer> desiredLevels = getDesiredLevels(level);

        for (Integer levelId : desiredLevels) {
            multiLevelCache.get(levelId).put(key, value);
        }


    }

    @Override
    public Collection<V> remove(K key) {
        List<V> values = new LinkedList<>();
        int level = key.getLevelId();
        Set<Integer> desiredLevels = getDesiredLevels(level);

        for (Integer levelId : desiredLevels) {
            if (multiLevelCache.get(levelId).containsKey(key)) {
                values.add(multiLevelCache.get(levelId).remove(key));
            }
        }

        return values;

    }

    @Override
    public V get(K key) {
        for (Integer levelId : multiLevelCache.keySet()) {
            if (multiLevelCache.get(levelId).containsKey(key)) {
                return multiLevelCache.get(levelId).get(key);
            }
        }

        return null;

    }

    @Override
    public void update(K key, V value) {
        for (Integer levelId : multiLevelCache.keySet()) {
            if (multiLevelCache.get(levelId).containsKey(key)) {
                multiLevelCache.get(levelId).put(key, value);
            }
        }
    }

    @Override
    public void show() {
        for (Integer levelId : multiLevelCache.keySet()) {

            System.out.println("Level:" + levelId + " value: " + multiLevelCache.get(levelId).values().stream().collect(Collectors.toList()));

        }
    }
}

Sample Test:

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 15/04/19
 * Description:
 */
public class Driver {


    static class MyCacheKey extends CacheKey {

        String key;

        public MyCacheKey(int levelId, String key) {
            super(levelId);
            this.key = key;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            MyCacheKey that = (MyCacheKey) o;
            return Objects.equals(key, that.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }

    static class MyCacheValue<T> {
        T value;

        public MyCacheValue(T value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "{" +
                    "value=" + value +
                    '}';
        }
    }

    public static void main(String args[]) {

        IMultiLevelCache<MyCacheKey, MyCacheValue<String>> multiLevelCache = new MultiLevelCache<>(3, 50);


        multiLevelCache.add(new MyCacheKey(29, "Key1"), new MyCacheValue<>("Key1Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key1")));
        multiLevelCache.add(new MyCacheKey(80, "Key2"), new MyCacheValue<>("Key2Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key2")));
        multiLevelCache.add(new MyCacheKey(900, "Key3"), new MyCacheValue<>("Ke31Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key3")));
        multiLevelCache.add(new MyCacheKey(290, "Key4"), new MyCacheValue<>("Key4Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key4")));
        multiLevelCache.add(new MyCacheKey(12, "Key5"), new MyCacheValue<>("Key5Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key5")));
        multiLevelCache.add(new MyCacheKey(9, "Key6"), new MyCacheValue<>("Key6Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key6")));
        multiLevelCache.add(new MyCacheKey(121, "Key7"), new MyCacheValue<>("Key7Value"));
        System.out.println(multiLevelCache.get(new MyCacheKey(20, "Key7")));


        System.out.println(multiLevelCache.remove(new MyCacheKey(20, "Key1")));

        multiLevelCache.show();

    }
}

Output:

{value=Key1Value}
{value=Key2Value}
{value=Ke31Value}
{value=Key4Value}
{value=Key5Value}
{value=Key6Value}
{value=Key7Value}
[{value=Key1Value}, {value=Key1Value}]
Level:20 value: [{value=Key2Value}, {value=Key4Value}, {value=Key5Value}]
Level:10 value: [{value=Key2Value}, {value=Ke31Value}, {value=Key4Value}, {value=Key5Value}, {value=Key6Value}, {value=Key7Value}]
Level:30 value: [{value=Key1Value}]

Great write up, i feel there are multiple follow up questions;
1. is it possible that top level cache gets full and spill over to next level cache ?
if so then we need to check the key in all below level cache until we find it or we don't find till end

2. What happen when duplicate key comes, should we update the cache at all level where this key is present (since in q 1 it can spill over)

3. do we need to provide any remove from cache method ?

and many more

Some code of last Algo;

package Java;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 14/04/19
 * Description:
 * google-interview-questions7
 * <p>
 * Give an array A of n integers where 1 <= a[i] <= K.
 * Find out the length of the shortest sequence that can be constructed out of numbers 1, 2, .. k that is NOT a subsequence of A.
 * eg. A = [4, 2, 1, 2, 3, 3, 2, 4, 1], K = 4
 * All single digits appears. Each of the 16 double digit sequences, (1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2) ... appears. Because (1, 1, 2) doesn't appear, return 3.
 */
public class ShortestSequence {


    static class Node implements Comparable<Node> {
        int item;
        int freq;


        public Node(int item, int freq) {
            this.item = item;
            this.freq = freq;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.freq, o.freq);
        }
    }

    public static void main(String args[]) {


        int array[] = {4, 2, 1, 2, 3, 3, 2, 4, 1};

        test(array, 4);
        test(array, 3); //does not follow the rule

        int array2[] = {1, 2, 3, 4, 1, 2, 3, 4};
        test(array2, 4);

        int array3[] = {1, 1, 3, 4, 2, 2, 3, 4};
        test(array3, 4);

        int array4[] = {1, 1, 3, 2, 2, 2, 3, 3};
        test(array4, 4); //should return 1

        int array5[] = {1, 1, 2, 3, 4, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4}; //all till 4 length seq kicked out
        test(array5, 4);


    }

    private static void test(int array[], int k) {
        System.out.println(shortestSequence(array, k));
    }

    //O(n) + O(n*logk) = O(n*logk)
    private static int shortestSequence(int[] array, int k) {

        if (null == array)
            return -1;

        //O(n)
        if (!ofSize1(array, k))
            return 1;

        if (!validateInput(array, k)) {

            PriorityQueue<Node> pq = new PriorityQueue<>(k); //create a pq of size k only;
            Map<Integer, Node> map = new HashMap<>();

            for (int i = 0; i < array.length; i++) {
                if (map.containsKey(array[i])) {
                    Node n = map.get(array[i]);

                    n.freq++; //since this same node is also present in pq, so pq will automatically hepify it self due to cross reference

                } else {
                    Node n = new Node(array[i], 1);
                    map.put(array[i], n);
                    pq.offer(n);
                }
            }

            if (pq.isEmpty())
                return -1;
            Node n = pq.poll();


            return n.freq + 1;

        }

        return -1;
    }

    //O(n)
    private static boolean ofSize1(int[] array, int k) {
        IntStream stream = IntStream.range(1, k + 1);
        Set<Integer> set = stream.boxed().collect(Collectors.toSet());
        for (int i = 0; i < array.length; i++)
            if (set.contains(array[i]))
                set.remove(array[i]);


        return set.isEmpty();
    }


    private static boolean validateInput(int[] array, int k) {
        return Arrays.stream(array).filter(x -> !(x >= 1 && x <= k)).count() > 0;
    }
}

I agree, this solution won't work. Please check my comment and find out the different approach and the way to approach.

Seeing no one is talking about progressively how to approach the problem, i though to take the chance and present a way to approach the problem;
now lets take a example;
A = [4, 2, 1, 2, 3, 3, 2, 4, 1], K = 4 => X[1,2,3,4]

Brute Force:
Here what we are trying to do is basically try to find is there any subsequence of length (L) which present in X but not in A, right. What about if we just generate
all subsequence of lenght 1 to k and check does it present in A or not, the one which does not present is your answer;

Algo:
1. first check does all numbers are present in A or not ( L=1); if not return 1 othrewise go to step 2;
2. Start generating different subsequence of L = 2 ... k, Let say this subsequence name is Y
2.1 for each subsequence check LCS(A,Y)!=len(Y) [ we find the longest common subsequence of A and Y and if there is a subsequence in A of Y length then this is not your answer] otehrwise its your answer len(Y)
3. Keep doing it until you find a seq Y which follow the rule LCS(A,Y)!=len(Y) ; if no one then answer is -1;

Complexity:
Step 1: O(n)
Step 2: Generating all the subsequence of each length is big, which is in a nutshell generating all the subsequence, In k length array there are K^k subsequence.
Step 2.1 checking each in A, will take O(n*K)
Hence; O(K^k*n*K) = O(n*K^(k+1)) = O(n*K^k)

Bottle neck; K^k

Brute Force 2: with slight improvement
Instead blindly generating of every length subsequence from X, first find the longest common subsequence in LCS(A,X), why? this will gurentee to you that
this length subsequence is present in A and all the shorter than this also present in A (this is what LCS does).

Algo:
0. first check does all numbers are present in A or not ( L=1); if not return 1 othrewise go to step 1;
1. Find the LCS(A,X) = len
2. generate all the subsequence of length len from X, Say Y and keep matching them in A; LCS(A,Y)!=len(Y); then one don't match is your answer;
Complexity:
Step 1: O(n*k)
Step 2: Generating all the subsequence of len length is also big, which is in a nutshell generating all the subsequence of length (len), In k length array there are len^k subsequence.
Step 2.1 checking each in A, will take O(n*len)
Hence; O(n*k) + O(n*len*len^k) = O(n*len^(k+1))
This is just a slight improvement though the worst case is still O(n*K^k) [ i guess; correct me if i'm wrong]

Bottle neck; len^k

Bleed Force :
What we are doing wrong in above brute force is generating blindly checking all subsequence of length len in A, right? We can avoid them

1. first check does all numbers are present in A or not ( L=1); if not return 1 othrewise go to step 1;
2. Find the LCS(A,X) = len
3. Backtrack the LCS array and find out all the subsequence of length len and keep them in a set;
4. generate all the subsequence of length len from X, Say Y which is not in set and keep matching them in A; LCS(A,Y)!=len(Y); then one don't match is your answer;

Complexity:
Step 1: O(n*k)
Step 2: Generating all the subsequence of len length is also big, which is in a nutshell generating all the subsequence of length (len), In k length array there are len^k subsequence.
Step 2.1 checking each in A, will take O(n*len)
Hence; O(n*k) + O(n*len*(len^k)/fact(len)) [ simplify it :P ]
This is just a slight improvement though the worst case is still O(n*K^k) [ i guess; correct me if i'm wrong]

Still ; Bottle neck; len^k


Better solution:
If we observe carefully, what we are doing is just finding the subsequence of len size and checking them in A, which is nothing but marking out the bad possibility of subsequence of length len;
if we some how mark them in bit faster way, we can find our SCS is much faster way.

Algo:
1. Create an frequency array of size K+1; Y
2. count the frequency of each item of A and store them in the Y. [ this will tell all the subsequence of length present A of Y, each element tells the subsequence made by him from A ]
3. Find the minimum and return min+1; Since all the subsequence of len=min is present in A and all the subsequence of length > min is also present in A [ there could be some combination which is not present but we are intersted in smallest]

Complexity:
Step 2: O(n);
Step 3: O(k)

Complexity: O(n+k); yupee

Can we do more better? Yes we can (slightly)

Best Solution:
Better solution:
If we observe carefully, what we are doing is just finding the subsequence of len size and checking them in A, which is nothing but marking out the bad possibility of subsequence of length len;
if we some how mark them in bit faster way, we can find our SCS is much faster way.

Algo:
1. Create an min heap size K; heap; it contains two element in each node ( element, frequency) and heapify based on frequency; also keep a map for cross reference so that you can update the value in heap in constant time; Map<Integer, Node>
2. now, start doing step 2 of above algo, every time you increase the frequency of element (from 1...k) update it in heap too and heapify.
3. Find the minimum and return min+1; constant time

Complexity:
Step 2: O(n*logk) amortized;
Step 3: O(1)
Complexity: O(nlogk); amortized; yupee

package Java;

import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 13/04/19
 * Description:
 * <p>
 * Given two string check if they can be made equivalent by performing some operations on one or both string.
 * <p>
 * swapEven:swap a character at an even-numbered index with a character at another even-numbered index
 * <p>
 * swapOdd:swap a character at an odd-numbered index with a character at another odd-numbered index
 * <p>
 * Given : s="cdab" , x="abcd"
 * s -> cdab ->swap a and c ->adcb (swapEven)-> swap b and d (swapOdd) -> s="abcd" = x="abcd"
 * <p>
 * Given: s="dcba" , x="abcd"
 * no amount of operation will move character from an odd index to even index, so the two string will never be equals
 * <p>
 * Given: s="abcd" ,x="abcdcd"
 * x length to big so will never be equals
 */
public class StringToStringTransformEvenOdd {

    public static void main(String args[]) {

        System.out.println(canTransform("abcd", "adcb"));
        System.out.println(canTransform("abcd", "dacb"));
        System.out.println(canTransform("adcba", "abcda"));
        System.out.println(canTransform("adcba", "bacda"));

    }

    private static boolean canTransform(String s1, String s2) {
        Map<Character, Integer> evenIndex = new HashMap<>();
        Map<Character, Integer> oddIndex = new HashMap<>();

        char s1Chars[] = s1.toCharArray();
        char s2Chars[] = s2.toCharArray();

        for (int i = 0; i < s1.length(); i++)
            if (i % 2 == 0)
                evenIndex.put(s1Chars[i], evenIndex.getOrDefault(s1Chars[i], 0) + 1);
            else
                oddIndex.put(s1Chars[i], oddIndex.getOrDefault(s1Chars[i], 0) + 1);

        for (int i = 0; i < s2.length(); i++)
            if (i % 2 == 0)
                evenIndex.put(s2Chars[i], evenIndex.getOrDefault(s2Chars[i], 0) - 1);
            else
                oddIndex.put(s2Chars[i], oddIndex.getOrDefault(s2Chars[i], 0) - 1);

        //evey value should be zero since they will cut each of them due to above count way
        return evenIndex.values().stream().filter(x -> x != 0).collect(Collectors.toList()).isEmpty()
                &&
                oddIndex.values().stream().filter(x -> x != 0).collect(Collectors.toList()).isEmpty();
    }
}

This chat box mess up the trie;
--a
c-b
--a
--b-c
--a
--c

Read top to bottom

You can do this in O(n^2) time using Trie.
Here is the algo;
We need to build trie along with smartLCP map which consist below things
1. start index, lcpLenght -> this will help us to return the query in constant time

How to build them in O(n^2);
Well here it is ;
1. start from the original string and put it into the trie, and insert in smartLCP (0, len(input))
2. now, start taking substring from index 1 onwards;
before inserting it into trie, check that the first character of this substring is same as first char
of input string or not; if not discard
if yes, start inserting into trie (may go to existing branch or create a new branch), as you
go down, check if it starting a new branch or continued it, get the length of matching(prefix)
and put in smartLCP

Trie would look like this for given above example; SmartLCP{(0,6), (2,3), (4,1)}
a
c b
a
b c
a
c

now its constant time to say the length of each lcp using smartLcp array.

Complexity: Building trie for a string is O(n) since there are n^2 substrings (which we can't avoid)
so complexity of creating trie is O(n^2) in worst case ( worst case occurs when all the character is same)

Simple piece of cake solution;
Keep doing DFS, keep a set to check the cycle, and keep a path array to note, that path has been explored or not so that you don't visit them again

public class SourceToDestinationWithCycleNecessaryConnected {

    public static void main(String args[]) {

        int vertices = 9;
        IGraph directedGraph = new DirectedGraph(vertices);

        directedGraph.addEdge(2, 3);
        directedGraph.addEdge(2, 4);
        directedGraph.addEdge(3, 4);
        directedGraph.addEdge(3, 6);
        directedGraph.addEdge(3, 5);
        directedGraph.addEdge(4, 5);
        directedGraph.addEdge(4, 2); // Cycle
        directedGraph.addEdge(4, 6);
        directedGraph.addEdge(5, 4); // Cycle
        directedGraph.addEdge(5, 7);
        directedGraph.addEdge(7, 8);

        System.out.println(isNecessaryConnected(directedGraph, vertices, 2, 8));


        IGraph directedGraph2 = new DirectedGraph(vertices);

        directedGraph2.addEdge(2, 3);
        directedGraph2.addEdge(2, 1);
        directedGraph2.addEdge(2, 4);
        directedGraph2.addEdge(3, 4);
        directedGraph2.addEdge(3, 6);
        directedGraph2.addEdge(3, 5);
        directedGraph2.addEdge(4, 5);
        directedGraph2.addEdge(4, 2); // Cycle
        directedGraph2.addEdge(4, 6);
        directedGraph2.addEdge(5, 4); // Cycle
        directedGraph2.addEdge(5, 7);
        directedGraph2.addEdge(7, 8);

        System.out.println(isNecessaryConnected(directedGraph2, vertices, 2, 8));

    }

    private static boolean isNecessaryConnected(IGraph directedGraph, int vertices, int source, int destination) {
        if (source > vertices || destination > vertices || source < 0 || destination < 0)
            return false;

        Set<Integer> visited = new HashSet<>();
        boolean path[] = new boolean[vertices];
        Arrays.fill(path, false);

        visited.add(source);
        dfs(directedGraph, visited, path, source, destination, source);

        for (int node : directedGraph.getAdjList()[source]) {
            if (path[node] == false)
                return false;
        }
        return true;
    }

    private static boolean dfs(IGraph directedGraph, Set<Integer> visted, boolean[] path, int source, int destination, int current) {

        //if this path already been computed
        if (path[current])
            return true;

        for (int node : directedGraph.getAdjList()[current]) {
            if (!visted.contains(node)) {

                //add this node so that we won't visit again (to avoid cycle)
                visted.add(node);

                if (node == destination)
                    path[node] = true;

                if (dfs(directedGraph, visted, path, source, destination, node)) {
                    path[current] = true;
                    return true;
                }

                visted.remove(node);
            }
        }


        return false;
    }
}

We can do it via queue manner ;
Queue Node{
int set[],
int min, max;
}
in each queue node, keep the index of element instead element( that will utilise in step 2)
1. start pushing element in the queue until no more element left, of length
1 having min& max as same as element and set would contain the index of this
element.

2. pop element from the queue, and start adding one element [ increase the set count]
in this set from starting from index in (set[set.length-1]) +1 (so that same element don't get add up
, it's constant time to check min and max. and the condition;

3. Keep doing this until you won't be able to add any further element in the queue.

4. finalCount = setCountSoFar + queue.size()

Complexity:
We are traversing each element of given set at max n times. so O(n^2)
Space complexity; at any given point of time, queue will contain at max n set only
why? since we keep popping the less length set from the queue in each iteration
and adding bigger length set in the queue (+1 size of previous ). At max the length of element would lie
between length=1 to length=n,
So, O(n^2)

O(n^2)/O(n^2)

Simple and clean backtracking approach

package Java;

import java.util.*;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 12/04/19
 * Description:
 */
public class DiceWordProblem {

    public static void main(String args[]) {
        String word = "ybdb";
        char dices[][] = {{'a', 'b', 'c', 'd', 'x', 'y'},
                {'b', 'b', 'c', 'd', 'a', 'b'},
                {'c', 'b', 'd', 'd', 'c', 'd'},
                {'d', 'b', 'c', 'a', 'a', 'b'}};

        System.out.println(isPossible(word, dices));
    }

    private static boolean isPossible(String word, char[][] dices) {

        if (word == null)
            return dices == null;

        if (dices.length == 0)
            return word.isEmpty();
        Set<Integer> availableDices = new HashSet<>();
        Map<Integer, List<Character>> diceToCharacterMap = new HashMap<>();

        int m = dices.length;
        int n = dices[0].length;

        for (int i = 0; i < m; i++) {
            availableDices.add(i);
            for (int j = 0; j < n; j++) {
                List<Character> chars = diceToCharacterMap.getOrDefault(i, new ArrayList<>(6));
                chars.add(dices[i][j]);
                diceToCharacterMap.put(i, chars);


            }
        }

        return isPossible(word, availableDices, diceToCharacterMap, "");
    }

    private static boolean isPossible(String word, Set<Integer> availableDices, Map<Integer, List<Character>> diceToCharacterMap, String temp) {

        if (temp.length() > word.length())
            return false;

        if (temp.equals(word))
            return true;

        for (Integer i : diceToCharacterMap.keySet()) {

            if (availableDices.contains(i)) {

                availableDices.remove(i);

                for (Character c : diceToCharacterMap.get(i)) {
                    if (word.contains(String.valueOf(c))) {
                        temp = temp + c;
                        if (isPossible(word, availableDices, diceToCharacterMap, temp))
                            return true;
                        temp = temp.substring(0, temp.length() - 1);
                    }

                }

                availableDices.add(i);
            }
        }
        return false;
    }
}

To check in k list use Hash to set map

I believe there are many approaches
1. First build the graph ( like 2d array) of n nodes using edge list
2. Then pick a pair from restricted nodes and recursively check does current node pass through any other node which is restricted, if so, simply remove that edge(s).
Complexity = there can be at most n^2 edges = M size O(m) , You need to pick a pair from k list O(k), and check all possible connections from source to destination of picked pair O(m)
O(nkm^2)

2.
2.1 build hash to set of given k list O(k)
2.2 Rater bulding graph, while building it check the restrictions recursively using 2d matrix,
Complexity = you need to traverse whole matrix to check restrictions O(n^2)
For each pair from edge list O(m) , keeping hash to set of nodes from k list O(1)
O(mn^2)

3. Efficient
Use union find algo, assuming path compression is used.
3.1 union edges from m list one by one if they are not connected, before connecting them see O(m)

a) the parent (s) of pair source does not lies in k list O(logn)
B) child of pair of destinations node not lies in k list O(logn)
If either of its true, then discard

Complexity = O(logn + logn) * O(m)
O(mlogn)

Cleaner and simpler approach;
Build graph,
run algorithm similar like Khan algo for topological sort;
Since, each connected orbit has at least 1 degree ( 1 edge between them).
So, if we find all the connected orbits to each other and run algo similar to khan, at the last only those orbit left which are no longer connect to any other;
Here is code

package Java;

import java.util.*;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 12/04/19
 * Description:
 * e.g.
 * <p>
 * OXOXXO
 * XXXXXO
 * XXXXOX
 * erase (0,0) and get
 * XXOXXO
 * XXXXXO
 * XXXXOX
 * erase (2,0) and get
 * XXXXXO
 * XXXXXO
 * XXXXOX
 * erase (5,0) and get
 * XXXXXX
 * XXXXXO
 * XXXXOX
 * no more moves available. Return 2 e.g.
 * <p>
 * OXOXXO
 * XXXXXO
 * XXOXOX
 * erase(4,2), (2,2), (0,0), (2,0), (5,0)
 * <p>
 * Return 1
 * e.g.
 * OXOXXX
 * XOXXXO
 * XXXOOX
 * <p>
 * erase(0,0), (1,1), (3,2)
 * <p>
 * Return 3
 */

public class SetMatrixZeros {

    static class DegreeNode {
        int i, j;
        int degree;

        public DegreeNode(int i, int j, int degree) {
            this.i = i;
            this.j = j;
            this.degree = degree;
        }
    }


    public static void test(char matrix[][]) {
        for (int i = 0; i < matrix.length; i++) {
            System.out.println();
            for (int j = 0; j < matrix[0].length; j++)
                System.out.print(matrix[i][j] + " ");
        }

        System.out.println("\n\noutput");
        int count = 0;
        char result[][] = setMatrixZero(matrix);
        for (int i = 0; i < result.length; i++) {
            System.out.println();
            for (int j = 0; j < result[0].length; j++) {
                if (result[i][j] == 'O')
                    count++;
                System.out.print(result[i][j] + " ");
            }
        }
        System.out.println("\ncount :" + count);

    }

    public static void main(String args[]) {
        char matrix[][] = {{'X', 'X', 'X', 'X', 'X', 'O'},
                {'O', 'X', 'X', 'X', 'X', 'X'},
                {'O', 'X', 'X', 'X', 'X', 'O'},
                {'X', 'X', 'O', 'X', 'O', 'X'},
                {'X', 'O', 'X', 'X', 'X', 'O'}};
        test(matrix);

        char matrix1[][] = {{'O', 'X', 'O', 'X', 'X'},
                {'X', 'O', 'X', 'X', 'X', 'O'},
                {'X', 'X', 'X', 'O', 'O', 'X'}};

        test(matrix1);

        char matrix2[][] = {{'O', 'X', 'O', 'X', 'O'},
                {'X', 'X', 'X', 'X', 'X', 'O'},
                {'X', 'X', 'O', 'X', 'O', 'X'}};

        test(matrix2);

        char matrix3[][] = {{'O', 'X', 'O', 'X', 'X', 'O'},
                {'X', 'X', 'X', 'X', 'X', 'O'},
                {'X', 'X', 'X', 'X', 'O', 'X'}};

        test(matrix3);


    }

    private static char[][] setMatrixZero(char[][] matrix) {
        Map<Integer, Set<Integer>> row = new HashMap<>();
        Map<Integer, Set<Integer>> col = new HashMap<>();

        int m = matrix.length;
        int n = matrix[0].length;
        //Build graph
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 'O') {
                    Set<Integer> redges = row.getOrDefault(i, new HashSet<>());
                    redges.add(j);
                    row.put(i, redges);

                    Set<Integer> cedges = col.getOrDefault(j, new HashSet<>());
                    cedges.add(i);
                    col.put(j, cedges);
                }

            }
        }

        PriorityQueue<DegreeNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o.degree));

        //Count degree
        for (int i = 0; i < m; i++) {
            for (Integer r : row.getOrDefault(i, new HashSet<>())) {
                int degree = row.get(i).size() + col.getOrDefault(r, new HashSet<>()).size() - 2;
                if (degree > 0)
                    priorityQueue.offer(new DegreeNode(i, r, degree));
            }
        }

        int index;
        //Delete till every node has zero degree except last node
        while (true) {

            DegreeNode node = priorityQueue.poll();

            //decrease the degree
            node.degree--;

            //if it has more degree, then push it to process further
            if (node.degree != 0)
                priorityQueue.offer(node);
            else {
                //If all other node degree is 0? in that case only one node has more than 0 degree
                if (priorityQueue.size() <= 1) {
                    break;
                }
            }

            //Find and remove the degree
            Set<Integer> rowsEdges = row.getOrDefault(node.i, new HashSet<>());
            Set<Integer> colEdges = col.getOrDefault(node.j, new HashSet<>());


            rowsEdges.remove(node.i);
            if (rowsEdges.size() == 0)
                row.remove(node.i);


            colEdges.remove(node.j);
            if (colEdges.size() == 0)
                col.remove(node.j);
            
            matrix[node.i][node.j] = 'X';

        }


        return matrix;
    }


}

package Java.Design.TextEditor;

import java.util.List;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 11/04/19
 * Description:
 */
public interface ITextEditor {

    void moveLeft();

    void moveRight();

    void backspace();

    void insert(char data);

    void undo();

    String print();

    CharacterNode getCursor();

}

package Java.Design.TextEditor;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 11/04/19
 * Description:
 * Define the Doubly linked list for text Editor
 */

public class CharacterNode {

    private char value;
    private CharacterNode next;
    private CharacterNode prev;


    public CharacterNode(char value) {
        this.value = value;
    }

    public char getValue() {
        return value;
    }

    public void setValue(char value) {
        this.value = value;
    }

    public CharacterNode getNext() {
        return next;
    }

    public void setNext(CharacterNode next) {
        this.next = next;
    }

    public CharacterNode getPrev() {
        return prev;
    }

    public void setPrev(CharacterNode prev) {
        this.prev = prev;
    }

    @Override
    public String toString() {
        return  value + " ";

    }
}

package Java.Design.TextEditor;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 11/04/19
 * Description:
 */
public class Revision {

    private Action action;
    private CharacterNode data;


    public Revision(Action action, CharacterNode data) {
        this.action = action;
        this.data = data;
    }

    public CharacterNode getData() {

        return data;
    }

    public void setData(CharacterNode data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Revision{" +
                "action=" + action +
                ", data=" + data +
                '}';
    }

    public Action getAction() {
        return action;
    }

    public void setAction(Action action) {
        this.action = action;
    }
}

All above code has corner case issues; here is simplest and fixed

package Java.Design.TextEditor;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * Author: Nitin Gupta(nitin.gupta@walmart.com)
 * Date: 11/04/19
 * Description: 
 */
public class SimpleTextEditor implements ITextEditor {

    private Stack<Revision> undoStack; //holds the last action
    private CharacterNode cursor; //holds the current cursor position
    private CharacterNode start; //to print
    int totalSize = 0;

    public SimpleTextEditor() {
        this.undoStack = new Stack<>();
        this.cursor = new CharacterNode('\0');
        start = null;
    }

    @Override
    public void moveLeft() {
        if (cursor.getPrev() == null) return;
        cursor = cursor.getPrev();
        undoStack.push(new Revision(Action.RIGHT, null));
    }

    @Override
    public void moveRight() {
        if (cursor.getNext() == null) return;
        cursor = cursor.getNext();
        undoStack.push(new Revision(Action.LEFT, null));
    }

    @Override
    public void backspace() {
        if (cursor.getPrev() == null) return; //No data to delete
        totalSize--;
        CharacterNode deleted = delete(cursor.getPrev());
        undoStack.push(new Revision(Action.INSERT, deleted));
        if (totalSize == 0)
            start = null;


    }

    private CharacterNode delete(CharacterNode toDelete) {

        if (toDelete != null) {

            CharacterNode prev = toDelete.getPrev();
            CharacterNode next = toDelete.getNext();

            if (prev != null) {
                prev.setNext(next);
            }

            if (next != null)
                next.setPrev(prev);

            if (toDelete.getPrev() == null && totalSize == 0)
                start = null;

            if (toDelete == start)
                start = next;
        }

        if (cursor.getPrev() == null && totalSize == 0)
            start = null;


        return toDelete;

    }

    @Override
    public void insert(char data) {


        CharacterNode node = new CharacterNode(data);

        CharacterNode prev = cursor.getPrev();

        node.setNext(cursor);
        cursor.setPrev(node);

        if (prev != null) {
            prev.setNext(node);
            node.setPrev(prev);

        } else
            start = node;

        if (totalSize == 0)
            start = node;


        undoStack.push(new Revision(Action.DELETE, node));
        totalSize++;

    }

    @Override
    public void undo() {

        if (undoStack.isEmpty()) return;

        Revision action = undoStack.pop();

        switch (action.getAction()) {
            case LEFT:
                if (cursor != null)
                    cursor = cursor.getNext();
                break;
            case RIGHT:
                if (cursor != null)
                    cursor = cursor.getPrev();
                break;
            case DELETE:
                if (cursor != null) {
                    if (cursor.getPrev() == null)
                        start = null;

                    delete(cursor.getPrev());
                }
                break;
            case INSERT:

                insert(action.getData().getValue());
                break;
        }

    }

    @Override
    public String print() {
        List<CharacterNode> currentText = new LinkedList<>();
        CharacterNode temp = start;
        while (temp != null) {

            if (temp == cursor)
                currentText.add(new CharacterNode('|'));
            if (temp.getValue() != '\0')
                currentText.add(temp);
            temp = temp.getNext();
        }
        return currentText.toString();
    }


    @Override
    public CharacterNode getCursor() {
        return cursor;
    }
}

0