Question

Given a two dimensional graph with points on it, find a line which passes the most number of points.

Solution

For this question, we used to use HashMap(Double, Integer) to do. However, the answer suggested in the book define its own Line Class, and uses HashMap(Line, Intger).

This is a much better solution, however, I failed to write it, don’t know why.

The key is to override the 2 methods:

@override
public int hashCode() {}

@override
public boolean equals(Object o) {}

Code

not written by me

Line.java

public class Line {

    private static double epsilon = .0001;

    public double slope;
    public double intercept;
    private boolean infinite_slope = false;

    public Line(GraphPoint p, GraphPoint q) {
        if (Math.abs(p.x - q.x) > epsilon) { // if x痴 are different
            slope = (p.y - q.y) / (p.x - q.x); // compute slope
            intercept = p.y - slope * p.x; // y intercept from y=mx+b
        } else {
            infinite_slope = true;
            intercept = p.x; // x-intercept, since slope is infinite
        }
    }

    public boolean isEqual(double a, double b) {
        return (Math.abs(a - b) < epsilon);
    }

    public void Print() {
        System.out.println("slope = " + slope + "\nintercept = " + intercept);
    }

    @Override
    public int hashCode() {
        int sl = (int) (slope * 1000);
        int in = (int) (intercept * 1000);
        return sl | in;
    }

    @Override
    public boolean equals(Object o) {
        Line l = (Line) o;
        if (isEqual(l.slope, slope) && isEqual(l.intercept, intercept)
                && (infinite_slope == l.infinite_slope)) {
            return true;
        }
        return false;
    }
}

Main method:

public static Line findBestLine(GraphPoint[] points) {

    Line bestLine = null;
    HashMap<Line, Integer> line_count = new HashMap<Line, Integer>();

    for (int i = 0; i < points.length; i++) {
        for (int j = i + 1; j < points.length; j++) {
            Line line = new Line(points[i], points[j]);
            if (!line_count.containsKey(line)) {
                line_count.put(line, 0);
            }
            line_count.put(line, line_count.get(line) + 1);
            if (bestLine == null
                    || line_count.get(line) > line_count.get(bestLine)) {
                bestLine = line;
                System.out.println("bestLine upodated! count = "
                        + line_count.get(line));
            }
        }
    }
    return bestLine;
}

Question

You have a very large array of ‘Person’ objects. Sort the people in increasing order of age.

Solution

First we look at the nature of this question:

1. large input array
2. sort based on age (which is between 1 and 100, this is important)

This exactly matches the charasteristics of Bucket Sort. Time complexity in average case is O(n + k) where k is the number of buckets.

Question

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.

Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4

Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

Solution

The solution is binary search, but when reads empty, advance to the next non-empty string.

But wait, there can be a very big problem that causes looping forever. Eg.

“a”, “”, “”, “”, “c” (5 items), look for “b”

Now ‘left’ points to 1st string(“a”) and ‘right’ points to 4th(“”). If we read read ‘mid’ value and advance to the next non-empty string, it’ll be “c”.

since “c” is large than “b”, ‘right’ is set to the 4th index. It’s a endless loop!

There’re various ways to solve this. The book suggests locate ‘right’ pointer at non-empty string by moving left, and then locate ‘mid’ pointer at non-empty by moving right. This avoids endless loop.

My approach is to use 2 instances of ‘mid’:

1. calculatedMid
2. comparisonMid

Both ways are fine.

Code

public static int search(String[] input, String target) {
    if (target == null || target.length() == 0) {
        return -1;
    }
    int len = input.length;
    int left = 0, right = len - 1;
    while (left < right) {
        int calculatedMid = left + (right - left) / 2;
        int comparisonMid = calculatedMid;
        while (comparisonMid < len && input[comparisonMid].length() == 0) {
            comparisonMid++;
        }
        if (input[comparisonMid].equals(target)) {
            return comparisonMid;
        } else if (input[comparisonMid].compareTo(target) < 0) {
            left = comparisonMid + 1;
        } else {
            right = calculatedMid - 1;
        }
    }
    if (left < len && input[left].equals(target)) {
        return left;
    } else {
        return -1;
    }
}

Question

Write a method to compute all permutations of a string.

Do it recursively.

Solution

1. Get first char.

2. Permute the reminder of the string.

3. Insert that char into all possible positions.

The code is more concise that doing it iteratively, and no visited array needed!

Code

public static ArrayList<String> getPerms(String s) {
    ArrayList<String> ans = new ArrayList<String>();
    if (s.length() == 1) {
        ans.add(s);
        return ans;
    }
    char single = s.charAt(0);
    ArrayList<String> partialPerms = getPerms(s.substring(1));
    for (String part : partialPerms) {
        for (int i = 0; i <= part.length(); i++) {
            ans.add(part.substring(0, i) + single + part.substring(i));
        }
    }
    return ans;
}

Question

An array A[1…n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation.

The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

Solution

This is a difficult bit operation question.

The main thing to understand is, for a particular bit:

if the bit value of the removed number is 0, then count(0) <= count(1)

if the bit value of the removed number is 1, then count(0) > count(1)

By using this principle, we can easily find the missing value for each bit.

However, we must know when to stop checking. For example:

input: 000, 001, 011

We know that the last bit is 0, second last is 1. We shall stop here and return the result “010”. If we did not stop, the result value would be “110”, which is wrong. How this is handled is by passing only half of the input list each time, and we also add one condition at the beginning:

if (list.size() == 0)
    return 0;

By doing this, we always limit the input list to a smaller range, until we finish finding all bits.

Code

hard to write

public static int findMissing(List<BitInteger> list) {
    return helper(list, BitInteger.INTEGER_SIZE - 1);
}

private static int helper(List<BitInteger> list, int col) {
    if (list.size() == 0)
        return 0;
    List<BitInteger> zeroList = new ArrayList<BitInteger>();
    List<BitInteger> oneList = new ArrayList<BitInteger>();
    for (BitInteger bit : list) {
        if (bit.fetch(col) == 0) {
            zeroList.add(bit);
        } else {
            oneList.add(bit);
        }
    }
    if (zeroList.size() <= oneList.size()) {
        // this means the missing value contains a 0
        return helper(zeroList, col - 1) << 1;
    } else {
        // the missing value contains 1
        return helper(oneList, col - 1) << 1 | 1;
    }
}

Question

There is an 8x8 chess board in which two diagonally opposite squares have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares.

Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible).

Solution

The chess board initially has 32 black and 32 white squares. By removing opposite corners, we’re left with 30 of one color and 32 of the other color.

31 dominos must cover 31 of one color and 31 of the other color.

So, impossible.

Question

Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation.

If the number can not be represented accurately in binary, print “ERROR”

Solution

Convert the integer part is easy.

The difficulty is how to convert a floating point (the decimal part) to binary form. The idea suggested in the book is to keep x2, and subtract 1 when necessary. Eg.

0.625 x 2 = 1.25, append 1

0.25 x 2 = 0.5, append 0

0.5 x 2 = 1, append 1

the binary form of 0.625 would be 0.101.

We must declarify the max number of digits in the decimal part. In the book, the answer assumes a maximum digits of 32 bits (i.e. when binary length grows more than 32 bits, return “Error”).

Code

written by me

public static String printBinary(String n) {
    String[] num = n.split("\\.");
    int integer = Integer.parseInt(num[0]);
    double decimal = Double.parseDouble("0." + num[1]);

    // now convert decimal part, if can't convert, return ERROR
    StringBuilder sb = new StringBuilder();
    while (decimal != 0) {
        if (sb.length() > 32) {
            return "ERROR";
        }
        double newDoub = 2 * decimal;
        sb.append(newDoub >= 1 ? "1" : "0");
        decimal = newDoub % 1;
    }

    // now convert integer part
    String intStr = "";
    while (integer != 0) {
        intStr = ((integer & 1) == 1 ? "1" : "0") + intStr;
        integer = integer >> 1;
    }

    // return the 2 parts connected with a dot
    return intStr + "." + sb.toString();
}

Question

Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented.

The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Solution

This is a very good question that tests stack operations.

Code

written by me

public static Stack<Integer> sort(Stack<Integer> s) {
    Stack<Integer> result = new Stack<Integer>();
    while (!s.isEmpty()) {
        Integer nextNum = s.pop();
        while (!result.isEmpty() && result.peek() < nextNum) {
            s.push(result.pop());
        }
        result.push(nextNum);
    }
    return result;
}

Question

You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.

Solution

Keep a list of items as buffer, and check the following condition:

“does this node complete a path with the sum?”

There’re n nodes in total, and the max size of buffer is lg(n), so the time complexity is O(nlgn).

Code

written by me

public static void find(TreeNode head, int target) {
    findSum(head, target, new ArrayList<Integer>());
}

private static void findSum(TreeNode node, int target, List<Integer> buffer) {
    if (node == null)
        return;

    buffer.add(node.data);
    int sum = 0;
    for (int i = buffer.size() - 1; i >= 0; i--) {
        sum += buffer.get(i);
        if (sum == target) {
            // from (i)th element until the last element is a valid path
            printPath(buffer, i);
        }
    }

    List<Integer> clone1 = new ArrayList<Integer>(buffer);
    findSum(node.left, target, clone1);

    List<Integer> clone2 = new ArrayList<Integer>(buffer);
    findSum(node.right, target, clone2);
}

private static void printPath(List<Integer> buffer, int start) {
    System.out.print("Path: ");
    for (int i = start; i < buffer.size(); i++) {
        System.out.print(buffer.get(i) + " ");
    }
    System.out.println();
}

Question

In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of di!erent sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one). You have the following constraints:

1. Only one disk can be moved at a time.
2. A disk is slid o! the top of one rod onto the next rod.
3. A disk can only be placed on top of a larger disk.

Write a program to move the disks from the “rst rod to the last using Stacks.

Solution

This is a classic recursive question. The solution code is supposed to be very concise.

Code

written by me, slightly different from the answer in the book, but good.

Main class:

public class HanoiMyAnswer {

    private static Rod r0, r1, r2;
    private static final int NUM_DISKS = 5;

    public static void main(String[] args) {
        // Hanoi Tower always have 3 rods
        r0 = new Rod(0);
        r1 = new Rod(1);
        r2 = new Rod(2);

        // Put some disks on the 1st rod, leaving 2nd and 3rd rod empty
        r0.setDisks(NUM_DISKS);

        // start main algorithm
        System.out.println("My answer: ");
        moveDisks(NUM_DISKS, r0, r2, r1);
    }

    private static void moveDisks(int number, Rod from, Rod to, Rod buffer) {
        if (number == 1) {
            int topValue = from.disks.pop();
            to.disks.push(topValue);
            displayMessage(topValue, from.name, to.name);
        } else {
            moveDisks(number - 1, from, buffer, to);
            int bottomValue = from.disks.pop();
            to.disks.push(bottomValue);
            displayMessage(bottomValue, from.name, to.name);
            moveDisks(number - 1, buffer, to, from);
        }
    }

    private static void displayMessage(int disk, int from, int to) {
        System.out.println("Disk[" + disk + "]: Rod" + from + "-->" + to);
    }
}

Rod.java

class Rod {

    int name;
    Stack<Integer> disks = new Stack<Integer>();

    public Rod(int rodIndex) {
        this.name = rodIndex;
    }

    public void setDisks(int n) {
        // this method will insert n disks on this Rod
        // the bottom disk is indexed as (n-1) and top one is 0
        disks.clear();
        for (int i = n - 1; i >= 0; i--) {
            disks.push(i);
        }
    }
}