CareerCup

Just a small suggestion that when you do this

mid = (left + right) //2

, then it might throw an overflow exception. the correct way is to

mid = left  + (right - left)/2;

Please find the recursive solution and possibly handling all cases where the number in mid is not a single digit.

public class GenerateI18NCombination {

    private Set<String> set = new HashSet<String>();

    private void recurse(String arr, String strSoFar) {
        if (arr.length() > 0) {
            set.add(strSoFar);
            String replace = replaceNumber(strSoFar, arr.length(), arr.charAt(0), true);
            if (!set.contains(replace)) {
                String s = arr.substring(1);
                recurse(s, replace);
            }
            replace = replaceNumber(strSoFar, arr.length(), arr.charAt(arr.length() - 1), false);
            if (!set.contains(replace)) {
                String s = arr.substring(0, arr.length()-1);
                recurse(s, replace);
            }
        } else {
            set.add(strSoFar);
        }
    }

    private String replaceNumber(String str, int length, char ch, boolean isInFront) {
        String[] arr = str.split("\\d");
        if (length - 1 == 0) {
            return arr[0] + ch + arr[1];
        } else {
            if (isInFront) {
                return arr[0] + ch + (length - 1) + arr[1];
            } else {
                return arr[0] + (length - 1) + ch + arr[1];
            }
        }
    }

    public static void main(String[] args) {
        GenerateI18NCombination obj = new GenerateI18NCombination();
        obj.recurse("AREERCU", "C7P");
        List<String> sortedList = new ArrayList<String>(obj.set);
        Collections.sort(sortedList);
        System.out.println(sortedList);
    }

}

Hi By using the containsValue method, you are basically making your implementation run O(N^2) because it take O(N) time to search if that value is there or not. What you can do is save the normal itenary that is given and also a reverse of that itenary i.e. in another hash map store "destination" as key and "source" as value. Now all you have to do is find if the key exists in this second hash map while iterating over the original itenary. I hope I made sense.

Hi @um01 can you explain with an example that will be great.

Hi, the wording of your algorithm (the last part of calculating the sum) is not clear. If possible please run an example for the same. Thanks.

Do the two numbers that we add have to be of same length? for example :- Is 1241125 an additive number? (for me it is since 124 +1 =125). But I want to clear it

Do the two numbers that we add have to be of same length? for example :- Is 1241125 an additive number? (for me it is since 124 +1 =125). But I want to clear it

Hello Tony, could you please provide an example, the one you have provided is not very clear. what do you mean by 124 is acceptable if we actually have "126 46.." as key code?

Hi, your code seems to work only for numbers that differ by 1 in length. However I think it should't be like that. As per my understanding of code we need to print the two halves that sum up as less than or equal to the other number. Here is my implementation.

public static void splits(String number1, String number2) {
        int num = Integer.parseInt(number2);
        String half1, half2;
        for (int index = 1; index < number1.length(); index++) {
            half1 = number1.substring(0, index);
            half2 = number1.substring(index);
            if ((Integer.parseInt(half1) + Integer.parseInt(half2)) <= num) {
                // could be easily changed here to track the halves that sum 
		// closest to 2nd Number
                System.out.println(half1 + "--" + half2);
            }
        }

    }

Hello can you explain your code a little bit more as it doesnt make sense what you mean by diameter. BY diameter do you mean its a circle around a rectangle? and then calculating all points? if so how did you calculate the diameter as just square root of area?

Hi when you say a Dijkstra's algorithm, how would you do that since it is possible only in a directed graph and this is not.... because if we are able to go from arr[i][j] to arr[i-1][j] then reverse is also true... Please correct me if I am wrong. Moreover when you say you would use HEAP DS then do you intend to change the structure of Heap DS as a node can have 2 children but in this question a node can have 4 immediate children (n, s, e, w);

Hello amirtar,
This is the code that i wrote. It has a slight modification of saving the best path once i reach a guard and the path i took to reach that guard. This way i save myself from doing a BFS on all nodes.

package arrays;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class GuardEmptySpace {

    /*char[][] museum = {
            {'.', '#', '.', 'G', '.'},
            {'.', '.', '#', '.', '.'},
            {'G', '.', '.', '.', '.'},
            {'.', '.', '#', '.', '.'}
    };*/

    char[][] museum = {
            {'.', '.', '.', 'G'},
            {'.', '.', '.', '.'},
            {'G', '#', '#', '.'},
            {'.', 'G', '#', '.'}
    };
    int[][] space = new int[museum.length][museum[0].length];

    Queue<String> q;
    Set<String> set;

    public static void main(String[] args) {
        GuardEmptySpace ges = new GuardEmptySpace();
        ges.findSpace();
    }

    private void findSpace() {
        for (int i = 0; i < museum.length; i++) {
            for (int j = 0; j < museum[0].length; j++) {
                if (museum[i][j] == 'G') {
                    //set n, s, e, w to be accessible in just one unit of space if they are not having #
                    setSpace(i, j);
                    space[i][j] = Integer.MIN_VALUE;
                } else if (museum[i][j] == '#') {
                    space[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        for (int i = 0; i < museum.length; i++) {
            for (int j = 0; j < museum[0].length; j++) {
                q = new LinkedList<String>();
                set = new HashSet<String>();
                if (space[i][j] == 0) {
                    set.add(i + "," + j);
                    q.add(i + "," + j);
                    setPath(performBFS());
                }
            }
        }

        for (int i = 0; i < museum.length; i++) {
            for (int j = 0; j < museum[0].length; j++) {
                if (space[i][j] == Integer.MIN_VALUE) {
                    System.out.print("G");
                } else if (space[i][j] == Integer.MAX_VALUE) {
                    System.out.print("#");
                } else {
                    System.out.print(space[i][j]);
                }
            }
            System.out.println();
        }
    }

    private void setPath(String s) {
        String[] split = s.split(";");
        int k = 1;
        for (int i = split.length - 2; i >= 0; i--, k++) {
            String[] split2 = split[i].split(",");
            space[Integer.parseInt(split2[0])][Integer.parseInt(split2[1])] = k;
        }
    }

    private String performBFS() {
        int i, j;
        while (!q.isEmpty()) {
            StringBuilder sb = new StringBuilder(q.poll());
            String str = getIndexString(sb.toString());
            String[] split = str.split(",");
            i = Integer.parseInt(split[0]);
            j = Integer.parseInt(split[1]);
            if (museum[i][j] == 'G') {
                return sb.toString();
            } else {
                changeQueue(sb.toString(), i - 1, j);
                changeQueue(sb.toString(), i + 1, j);
                changeQueue(sb.toString(), i, j - 1);
                changeQueue(sb.toString(), i, j + 1);
            }
        }
        return "";
    }

    private void changeQueue(String str, int i, int j) {
        StringBuilder sb = new StringBuilder(str);
        if (isGoodCell(i, j)) {
            q.add(sb.append(";").append(i).append(",").append(j).toString());
            set.add(i + "," + j);
        }
    }

    private String getIndexString(String str) {
        String[] split = str.split(";");
        int size = split.length;
        return split[size - 1];
    }

    private boolean isGoodCell(int i, int j) {
        if ((i < museum.length && i >= 0) && (j < museum[0].length && j >= 0)) {
            if ((!set.contains(i + "," + j)) && (space[i][j] != Integer.MAX_VALUE)) {
                return true;
            }
        }
        return false;
    }

    private void setSpace(int i, int j) {
        // set north
        if ((i - 1 >= 0) && (space[i - 1][j] != '#')) {
            space[i - 1][j] = 1;
        }
        // set south
        if ((i + 1 < museum.length) && (space[i + 1][j] != '#')) {
            space[i + 1][j] = 1;
        }
        //set east
        if ((j - 1 >= 0) && (space[i][j - 1] != '#')) {
            space[i][j - 1] = 1;
        }
        if ((j + 1 < museum[0].length) && (space[i][j + 1] != '#')) {
            space[i][j + 1] = 1;
        }
    }
}

i think we can save ourself from doing BFS on N nodes. Here is what i propose:-
(1) first traverse the whole array and while traversing whenever you find a G, we turn all the accessible points from that G with distance of 1 only as 1, i.e. the immediate n, s, e, w points to this G as 1. and keep putting these cells in a queue.
(2) while the queue is not empty, we pop one element (one cell) and turn it's n, s, e, w to be min(it's neighbors + 1); and put this new cell in queue.
NOTE: since not all the neighbors are having the value we just take those that have and we shall check this value again. Also the cells that have value as 1 cannot be better than that so we don't enqueue them again.

Please reply if you find any ambiguity in the algorithm.

You need to create a min heap of k size which will take O(n) and then after heap creation just pop all elements one by one and add the total number of stones needed to overflow each pot.

Well the person who down flagged it please be courteous enough to drop the reason for the same. Also this solution works as I have tried and tested it using JAVA

My solution is O(n), assuming, we need to give a pair of numbers whose sum matches the value asked for.
(1) create a hash map of <key=(the numbers given in list), value= the frequency of the number>
(2) start with first number in the list and subtract this number from the sum (if the number is positive), if its negative then add.
(3) search in hash map for the difference from step 2 if present then print the pair else proceed with step 2.

Note: few assumptions
(1) sum requested is positive, but the above algo can be modified to make it work for
negative sums.
(2) we want to print pair of numbers only.

this is not a recursive solution....

What do you mean by ^ operator?

I am down voting the same because the use of regex expression is the best way to do so as that is much more quicker and clean.

the approach is correct but it will be O(n^2) not O(n*logn)

I would do it in the following way....

Step 1: Iterate through all the elements in the list
Step 2: Insert each element in a set if its not there, else remove from the set.
Step 3: once end of list occurs, Iterate through the set and print if any element, else "print no unique element"

/*
     * Returns true if the input string is a number and false otherwise
     */
    /*
     * Examples:
     * isNumber(12) -> true
     * isNumber("one") -> false
     * isNumber(23.2) -> true
     * isNumber(0) -> true
     * isNumber(-23) -> true
     */

public static boolean isNumber(String toTest)
    {
        boolean flag = false;
        
        // implementation here
        String pattern = "(-?\\d+)|(-?\\d+\\.\\d+)";
        flag = toTest.matches(pattern);
        return flag;

}