Question

link

Given an array of integers A, give an algorithm to find the longest Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, such that

A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the largest possible.

The sequence S1, S2, …, Sk is called an arithmetic progression if S(j+1) – S(j) is a constant.

Solution

This is a rather difficult Arithmetic Progression question.

The solution is 2-D DP.

The idea is to create a 2D table dp[n][n]. An entry dp[i][j] in this table stores LLAP with input[i] and input[j] as first two elements of AP(j > i).

The last column of the table is always 2. Rest of the table is filled from bottom right to top left.

To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an AP, then the value of dp[i][j] is set as dp[j][k] + 1.

Note that the value of dp[j][k] must have been filled before as the loop traverses from right to left columns.

The 2 difficult points of this question:

1. how to come up with the transation formula. (i.e. dp[i][j] = dp[j][k] + 1, when (i, j, k) forms a AP).
2. how to fill up all dp[i][j] in each loop of j. (Once inside the if-else, once outside the main while-loop)

Code

written by me

public int longest(int[] A) {
    int len = A.length;
    int[][] dp = new int[len][len];
    for (int i = 0; i < len; i++) {
        // the pair ending at last position is always a progression
        dp[i][len - 1] = 2;
    }
    int longest = 1;
    for (int j = len - 2; j >= 0; j--) {
        // for each j, find i and k that makes 1 progression
        int i = j - 1;
        int k = j + 1;
        while (i >= 0 && k < len) {
            int total = A[i] + A[k];
            if (total > 2 * A[j]) {
                // this is important!
                dp[i][j] = 2;
                i--;
            } else if (total < 2 * A[j]) {
                k++;
            } else {
                // found a valid progression triplet A(i, j, k)
                dp[i][j] = dp[j][k] + 1;
                longest = Math.max(longest, dp[i][j]);
                i--;
                k++;
            }
        }
        // this is important!
        while (i >= 0) {
            dp[i][j] = 2;
            i--;
            // If the loop was stopped due to k becoming more than
            // n-1, set the remaining dp[i][j] as 2
        }
    }
    return longest;
}

Question

Describe an algorithm to find the largest 1 million numbers in 1 billion numbers.

Assume that the computer memory can hold all one billion numbers.

Solution

There’re enough discussion on Top K problems so far in this blog. The suggest solutions is:

1. Sort

2. Min Heap, O(n logm) time.

3. Quickselect algorithm. O(n) time.

Question

Given an NxN matrix of positive and negative integers, write code to find the sub-matrix with the largest possible sum.

Solution

I wrote about this question before: [Question] Max Sum In A 2D Array (sub-matrix), and the solution gave a better time complexity (O(n³)) than in the book (O(n⁴)).

1. locate a row - O(n)
2. locate another row - O(n)
3. compute sub value of that column - O(n), and then find largest subarray in array - also O(n)
4. The above 3 steps each take O(n) time, total time is O(n³).

Please refer to the other post for more detail.

Question

Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.

Solution

This is very similar to another post I wrote: [Question] Shuffle An Array (Fisher–Yates).

The basic idea is to choose element one by one using RNG. After choosing an int, swap it to top and then mark this element as ‘dead’. Next time, the RNG will not touch on the ‘dead’ elements.

Very similar to Fisher–Yates Shuffle, and the code below is written by me.

Code

public static int[] pickMRandomly(int[] original, int m) {
    int[] ans = new int[m];
    for (int i = 0; i < m; i++) {
        int rand = Question.listRand.get(i);
        // note: rand is RN in the range [i, max]
        ans[i] = original[rand];
        original[rand] = original[i];
        // now (i)th position in original is dead
        // no one cares what value is at original[i]
    }
    return ans;
}

Question

Given a string s and an array of smaller strings T, design a method to search s for each small string in T.

Solution

This is a very classic question of string search, favored by Google and Facebook.

The solution is suffix tree (to be distinguished from trie, or prefix tree, which searched word by its prefix). Suffix tree is good for search a proportion of a long string. For example, using “bibs” to build a suffix tree like this:

The building of suffix tree and searching is not a very lengthy code. It’s posted below and it’s not written by me.

Code

Main method:

public static void main(String[] args) {
    String testString = "mississippi";
    String[] stringList = { "is", "sip", "hi", "sis" };
    SuffixTree tree = new SuffixTree(testString);
    for (String s : stringList) {
        ArrayList<Integer> list = tree.getIndexes(s);
        if (list != null) {
            System.out.println(s + ": " + list.toString());
        } else {
            System.out.println(s + ": does not exist.");
        }
    }
}

SuffixTree.java

public class SuffixTree {
    SuffixTreeNode root = new SuffixTreeNode();

    public SuffixTree(String s) {
        // create a suffix tree with input string s
        for (int i = 0; i < s.length(); i++) {
            String suffix = s.substring(i);
            root.insertString(suffix, i);
        }
    }

    public ArrayList<Integer> getIndexes(String s) {
        return root.getIndexes(s);
    }
}

SuffixTreeNode.java

public class SuffixTreeNode {

    char value;
    HashMap<Character, SuffixTreeNode> children;
    ArrayList<Integer> indexes = new ArrayList<Integer>();

    public SuffixTreeNode() {
        children = new HashMap<Character, SuffixTreeNode>();
    }

    public void insertString(String s, int index) {
        indexes.add(index);
        if (s != null && s.length() > 0) {
            value = s.charAt(0);
            SuffixTreeNode child = null;
            if (children.containsKey(value)) {
                child = children.get(value);
            } else {
                child = new SuffixTreeNode();
                children.put(value, child);
            }
            String remainder = s.substring(1);
            child.insertString(remainder, index);
        }
    }

    public ArrayList<Integer> getIndexes(String s) {
        if (s == null || s.length() == 0) {
            return indexes;
        } else {
            char first = s.charAt(0);
            if (children.containsKey(first)) {
                String remainder = s.substring(1);
                return children.get(first).getIndexes(remainder);
            }
        }
        return null;
    }
}

Question

Imagine you have a square matrix, where each cell is filled with either black or white.

Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

Solution

There is no better way to solve this except Brute Force. First find a point (as the top-left corner), and then test square size from large to small.

The code below is from the book.

Code

public static Subsquare findMaxSquareInMatrix(int[][] matrix) {
    assert (matrix.length > 0);
    for (int row = 0; row < matrix.length; row++) {
        assert (matrix[row].length == matrix.length);
    }

    int N = matrix.length;
    int currentMaxSize = 0;
    Subsquare sq = null;
    int col = 0;

    // Iterate through each column from left to right
    while (N - col > currentMaxSize) { // See step 4 above
        for (int row = 0; row < matrix.length; row++) {
            // starting from the biggest
            int size = N - Math.max(row, col);
            while (size > currentMaxSize) {
                if (checkSquareBorders(matrix, row, col, size)) {
                    currentMaxSize = size;
                    sq = new Subsquare(row, col, size);
                    break; // go to next (full) column
                }
                size--;
            }
        }
        col++;
    }
    return sq;
}

private static boolean checkSquareBorders(int[][] matrix, int row, int col,
        int size) {
    // Check top and bottom border.
    for (int j = 0; j < size; j++) {
        if (matrix[row][col + j] == 1) {
            return false;
        }
        if (matrix[row + size - 1][col + j] == 1) {
            return false;
        }
    }

    // Check left and right border.
    for (int i = 1; i < size - 1; i++) {
        if (matrix[row + i][col] == 1) {
            return false;
        }
        if (matrix[row + i][col + size - 1] == 1) {
            return false;
        }
    }
    return true;
}

Question

Write a method to count the number of 2s between 0 and n.

Solution

This is a difficult question, especially hard to come up with the correct formula. Eg.

f(279) = {(79 + 1) + 2 * f(99)} + f(79)

f(513) = {100 + 5 * f(99)} + f(13)

Take 513 as example, the first digit is 5. We know that all the 200+ is within the range, so there’re 100 twos in the first digit. Then, for the rest of the digits, we get f(99) for number between 0 and 99, and another f(99) for number between 100 and 199… and this happens 5 times until 499. That’s why we have 5 multiple by f(99).

In the end, we do the calculation recursively for reminder number 13.

Code

public static int myAnswer(int n) {
    if (n == 0)
        return 0;
    int power = 1;
    while (power * 10 <= n) {
        power *= 10;
    }

    int first = n / power;
    int reminder = n % power;
    int firstDigit2count = 0;
    if (first > 2) {
        firstDigit2count = power;
    } else if (first == 2) {
        firstDigit2count = reminder + 1;
    }
    int totalCountBeforeReminder = firstDigit2count
            + (first * myAnswer(power - 1));
    return totalCountBeforeReminder + myAnswer(reminder);
}

Question

Write a method which finds the maximum of two numbers. You should not use if-else or any other comparison operator.

EXAMPLE

Input: 5, 10

Output: 10

This is also on CC150v5 Q17.4.

Solution

We can’t use >, < or if-else statement, but we can use mathematical operator like subtract and bit operators.

Calculate (a-b) and do (a + K(a-b)) can help us (where K is either 0 or -1).

Updated on Sep 29th: according to CC150v5 Q17.4, there can be errros when (a-b) is overflows. So this is the modified version of solution:

1. do a sign check of a and b
2. if a and b are same sign, do it just like before
3. if a and b are different sign, the ‘K’ value only depends on a.

I posted the modified solution below as well.

Code

first solution from v4, written by me:

public static int getMax(int a, int b) {
    int c = a - b;
    int signBit = c >> 31 & 1;
    // if (a-b) is negative, sign = 1
    // otherwise, sign = 0
    return a - signBit * c;
}

modified solution, no overflow issues.

public static int getMax(int a, int b) {
    int sign;
    // if a,b have different sign, then go with first number
    if (sign(a) == sign(b)) {
        sign = sign(a - b);
    } else {
        sign = sign(a);
    }
    // sign is 0 if a >= b
    // sign is -1 is a < b
    return a + (a - b) * sign;
}

private static int sign(int c) {
    return c >> 31;
}

Question

Given an integer between 0 and 999,999, print an English phrase that describes the integer (eg, “One Thousand, Two Hundred Thirty Four”).

This is also on CC150v5 Q17.7.

Solution

The solution in book isn’t good, so I wrote the code myself. Read it below.

Code

private static String[] arr1 = { "Zero ", "One ", "Two ", "Three ",
        "Four ", "Five ", "Six ", "Seven ", "Eight ", "Nine " };

private static String[] arr11 = { "Ten ", "Eleven ", "Twelve ",
        "Thirteen ", "Fourteen ", "Fifteen ", "Sixteen ", "Seventeen ",
        "Eighteen ", "Nineteen " };

private static String[] arr10 = { "", "Ten ", "Twenty ", "Thirty ",
        "Forty ", "Fifty ", "Sixty ", "Seventy ", "Eighty ", "Ninety " };

public static String numtostring(int num) {
    int part1 = num / 1000;
    int part2 = num % 1000;
    if (part1 == 0) {
        return numBelowTrousand(part2);
    } else {
        return numBelowTrousand(part1) + "Thousand, "
                + numBelowTrousand(part2);
    }
}

public static String numBelowTrousand(int num) {
    StringBuilder sb = new StringBuilder();
    // assume num is below 1000

    // first, convert hundred digit
    int hundred = num / 100;
    if (hundred != 0) {
        sb.append(arr1[hundred] + "Hundred ");
    }

    // second, convert the rest of digits
    num %= 100;
    if (num != 0) {
        int ten = num / 10;
        int one = num % 10;
        if (ten == 1) {
            sb.append(arr11[num - 10]);
        } else {
            if (ten != 0) {
                // ten is in the range of [2,9]
                sb.append(arr10[ten]);
            }
            if (one != 0) {
                sb.append(arr1[one]);
            }
        }
    }
    return sb.toString();
}

Question

link

How would you determine if someone has won a game of tic-tac-toe on a board of any size?

(This is also on CC150v4 19.2 and CC150v4 17.2)

Solution

First, confirm that when the number of pieces in a line equals to the dimension of the board, one person wins. Eg. for 10 * 10 board, 10 pieces need to be in 1 line.

We can determine if someone has won during a game in real time, as in checking after every move.

Create an array of size 2n+2 at the beginning of the game and fill it with zeros. Each spot in the array will be a sum of X’s or O’s horizontally (the first n places in the array), vertically (the second n places in the array) and diagonally (the last 2 places). Then with every move, you add 1 to the 2 places (or 3 if on a diagnol) of the array if X, and subtract 1 if its an O. After adding you check and see if the value of the array is equal to n or -n, if it is, n mean X has won and -n means O has won.

This is uses O(2n+2) space, but it’s the best solution I can find online. I wrote code posted below.

Code

written by me

enum Piece {
    Empty, Red, Blue
};

public static Piece hasWon3(Piece[][] board) {

    int N = board.length;

    // O(2n+2) space to store count info
    int[] rowCnt = new int[N];
    int[] colCnt = new int[N];
    int[] digCnt = new int[2];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {

            int pieceValue = 0;
            if (board[i][j] == Piece.Blue) {
                pieceValue = 1;
            } else if (board[i][j] == Piece.Red) {
                pieceValue = -1;
            }

            // if empty, pieceValue is 0
            // if blue, add 1 in count
            // if red, subtract 1 in count
            rowCnt[i] += pieceValue;
            if (checkFinish(rowCnt[i], N) != null) {
                return checkFinish(rowCnt[i], N);
            }

            // after adding the count, check if the game finishes
            colCnt[j] += pieceValue;
            if (checkFinish(colCnt[j], N) != null) {
                return checkFinish(colCnt[j], N);
            }

            if (i == j) {
                digCnt[0] += pieceValue;
                if (checkFinish(digCnt[0], N) != null) {
                    return checkFinish(digCnt[0], N);
                }
            } else if (i + j == N) {
                digCnt[1] += pieceValue;
                if (checkFinish(digCnt[1], N) != null) {
                    return checkFinish(digCnt[1], N);
                }
            }
        }
    }
    // game not finished, continue
    return Piece.Empty;
}

private static Piece checkFinish(int count, int N) {
    if (count == N)
        return Piece.Blue;
    else if (count == -1 * N)
        return Piece.Red;
    else
        return null;
}