CareerCup

The application and service FACEY.TOP represents briefly how Instagram works.


But this is not a question for the interview. Or, probably, if the person has the imagination at least how to start and what is expected as a final implementation.

We could represent the persons as the array of Qubits:
00: Celebrity - knows nobody in the room
01: No celebrity - knows only celebrity
10: No celebrity - knows everybody but no celebrity
11: No celebrity - knows the celebrity and everybody else

If we sort the array - then we know where to look for the celebrity.

Hint: use this method as a way of summing big numbers:

public String bigSum(String s1, String s2) {
    int lengthS1 = s1.length();
    int lengthS2 = s2.length();

    int diff = Math.abs(lengthS1 - lengthS2);

    String prefix = repeatString("0", diff);


    if (lengthS1 < lengthS2) {
        s1 = prefix + s1;
    } else if (lengthS2 < lengthS1) {
        s2 = prefix + s2;
    }

    StringBuilder out = new StringBuilder();
    int buf = 0;
    for (int i = s1.length() - 1; i >= 0; i--) {
        int n1 = Integer.parseInt(String.valueOf(s1.charAt(i)));
        int n2 = Integer.parseInt(String.valueOf(s2.charAt(i)));

        int sum = buf + n1 + n2;
        buf = 0;
        if (sum >= 10) {
            sum = sum % 10;
            buf++;
        } else {
            buf = 0;
        }

        if (buf > 0 && i == 0) {
            out.insert(0, "1").insert(1, sum);
        } else {
            out.insert(0, sum);
        }
    }


    return out.toString();
}

Explain your answer in the code, please.

My explanation is:

1. Assume that we know that we need to start on the first line from left to right because we know that the last broken computer on the paired line (if to calculate from 1, not from 0) and it is closer to the right side.
2. It means that will be faster if we start the verification of the last line from the right side.
3. We have 5 rows of the 5 items in a row. The last broken computer is a first item in the 4th row. It means that 3*5 + 1 = 16.

The question is about possible combinations, not the permutations.
It means, that if we have a number 5 - then possible combinations are:
1+1+1+1+1
2+1+1+1
2+2+1
3+1+1
4+1

Clarify the question, please.
Because, if the question is: is it possible to pair them (Put all the white sockets in the bucket#1 and all the black sockets in the bucket#2)? Then:
- if the number of socks is not paired {number} % 2 != 0 - then the answer is immediately False.
- if the number is paired - we need to go through the list of the socks (could be both directional iteration) and put the socks on 2 different buckets. Once the number of socks (black or white) becomes bigger than half of all the socks - the answer is False.
- if the balancing of both lists works - then we will end the iteration with the balanced number of socks in both buckets.

If we need to differentiate by "left" and "right" for each color - then the flow is different.

This is an simple algorithm of how to convert Hex to Decimal and how to build RGB color, for example #4d4d4d = rgb(77, 77, 77).

public String convertColorHexToDecimal(String hex) {
        StringBuilder result = new StringBuilder();

        int counterDivider = 0;
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < hex.length(); i++) {
            counterDivider ++;
            buf.append(hex.charAt(i));
            if (counterDivider == 2) {
                result.append(convertHexToDecimal(buf.toString())).append(" ");
                buf.delete(0, buf.length());
                counterDivider = 0;
            }
        }
        return result.toString();
    }

    public int convertHexToDecimal(String hex) {
        int result = 0;
        for (int i = 0; i < hex.length(); i++) {
            result += Character.getNumericValue(hex.charAt(hex.length() - 1 - i)) * Math.pow(16, i);
        }
        return result;
    }

Complexity O(2*n/2) = O(n)

public String[] reverseArrayWithModification(String[] arr) {
        String[] out = new String[arr.length - 1];
        int middle = arr.length / 2;

        if (arr[middle].equals("&")) {
            for (int i = 0; i < middle; i ++) {
                out[i] = arr[arr.length - 1 - i];
            }
            for (int i = middle + 1; i <= 2 * middle; i ++) {
                out[i - 1] = arr[i - middle - 1];
            }
        } else {
            throw new IllegalArgumentException("Input array has no char '&'");
        }
        return out;
    }

Please, clarify the question.
Because, if we talk about Adjacency matrix for undirected graph - it's is a symmetric matrix, so, the answer will be always True.

ArrayList<int[]> coordinatesBrokenComputers = new ArrayList<>();
        coordinatesBrokenComputers.add(new int[]{1,1});
        coordinatesBrokenComputers.add(new int[]{1,4});
        coordinatesBrokenComputers.add(new int[]{2,2});
        coordinatesBrokenComputers.add(new int[]{3,4});

        int[][] room = new int[][]{
                {1,1,1,1,1},
                {1,0,1,1,0},
                {1,1,0,1,1},
                {1,1,1,1,0},
                {1,1,1,1,1}
        };

assertEquals(16, coordinatesFounder.getLessAmountOfStepsToFindBrokenComputers(room, coordinatesBrokenComputers));

Implementation:

public int getLessAmountOfStepsToFindBrokenComputers(int[][] room, ArrayList<int[]> coordinatesBrokenComputers) {
        int steps = 0;
        int sizeOfBrokenComputers = coordinatesBrokenComputers.size();
        for (int i = 0; i < room.length; i++) {
            if (i % 2 == 0) {
                for (int j = 0; j < room[i].length; j++) {
                    steps++;
                    if (room[i][j] == 0) {
                        sizeOfBrokenComputers--;
                        if (sizeOfBrokenComputers == 0) {
                            return steps;
                        }
                    }
                }
            } else {
                for (int j = room[i].length - 1; j >= 0; j--) {
                    steps++;
                    if (room[i][j] == 0) {
                        sizeOfBrokenComputers--;
                        if (sizeOfBrokenComputers == 0) {
                            return steps;
                        }
                    }
                }
            }
        }

        return steps;
    }

Very short solution. It checks that 0 could be an island also if it's alone:

public boolean isAnIsland(int[][] matrix, int[] pointXY) {
        assert pointXY.length == 2;

        int x = pointXY[0];
        int y = pointXY[1];
        int value = matrix[x][y];

        boolean top = x <= 0 || (matrix[x - 1][y] != value);
        boolean bottom = x >= matrix.length - 1 || (matrix[x + 1][y] != value);
        boolean left = y <= 0 || (matrix[x][y - 1] != value);
        boolean right = y >= matrix[x].length - 1 || (matrix[x][y + 1] != value);

        return top && bottom && left && right;
    }


    public int foundNumberOfIslands(int[][] matrix) {
        int count = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (isAnIsland(matrix, new int[]{i, j})) {
                    count++;
                    System.out.println("Coordinates: " + i + ", " + j);
                }
            }
        }

        return count;
    }

Here is the multiplication. The method "bigSum" is described above.
The function works only with an equal Strings by length.

unit test:
bigMultipl("123456781234567812345678123456781231234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678456781234567812345678123456781234567812345678",

"123456781234567812345678123456781231234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678123456781234567812345678456781234567812345678123456781234567812345678"));

result =
15241566832799835131840019356816873129412161060136908261522059216750369293320360971620290100369704845365086870331252870116370369202120372405370527895373317370413557870939420377432620454710371351027673886100984519252301774947583571499390156842912823863303992974797473165550166654279282375988982091851404238129875577457087736154196977375165932083620904155824874754407079505654114672374342882186495595263426186618964206036665458836888572988923249505065691208988873673208352565279684

public String bigMultipl(String s1, String s2) {
        LinkedList<String> list = new LinkedList<>();
        int lengthS1 = s1.length();
        int lengthS2 = s2.length();

        int diff = Math.abs(lengthS1 - lengthS2);

        StringBuilder prefix = new StringBuilder();
        for (int i = 0; i < diff; i++) {
            prefix.append("0");
        }


        if (lengthS1 < lengthS2) {
            s1 = prefix + s1;
        } else if (lengthS2 < lengthS1) {
            s2 = prefix + s2;
        }
        for (int i = s1.length() - 1; i >= 0; i --) {
            int buf = 0;
            String tempSum = "";
            for (int j = s2.length() - 1; j >= 0; j --) {
                int n1 = Integer.parseInt(String.valueOf(s1.charAt(i)));
                int n2 = Integer.parseInt(String.valueOf(s2.charAt(j)));

                int sum = buf + n1 * n2;
                buf = 0;
                if (sum >= 10) {
                    buf += sum / 10;
                    sum = sum % 10;
                } else {
                    buf = 0;
                }
                tempSum = String.valueOf(sum) + tempSum;

            }
            if (buf > 0) {
                list.add(buf + tempSum);
            } else {
                list.add(tempSum);
            }
        }

        String sum = "";
        for (int i = 0; i < list.size(); i ++) {
            sum = bigSum(sum, list.get(i) + repeatString("0", i));
        }

        if (sum.startsWith("0")) {
            sum = "1" + sum;
        }

        return sum;
    }

Steps:
1. Find the biggest 10^n number before "number"
2. Put into array 10^0 ... 10^n. We have smth like [1, 10, 100, 1000]
3. Print all the combinations

Exclude the steps if any of the pre-conditions are known already.

Continue to the answer above.

Tested with the UT:
assertEquals("0", codeBase.bigSum("909876545678909876878765546789765490987654567890987687876554678976546789909876545678909876878765546789765467890876545678908765457890087654567890876545789067899098765456789098768787655467897654678908765456789087654578900876545678908765457890", "909876545678909876878765546789765490987654567890987687876554678976546789909876545678909876878765546789765467890876545678908765457890087654567890876545789067899098765456789098768787655445678908765457890"));