Question

You'reworking on the Google Chrome team when you receivea bug report: Chrome crashes on launch. What would you do?

Step 1: Understand the Scenario

1. How long has user seen this issue?
2. version of browser and OS?
3. Does this happen consistently? How often, and when?

Step 2: Break Down the Problem

Flow of situation:

1. start menu
2. click chrome
3. browser starts
4. browser load settings
5. browser issues HTTP response
6. browser get HTTP response
7. browser parses webpage
8. browser displays content

At some points in this process, something fails. A good tester would iterate thru the elements of this scenario and diagnose the problem.

Step 3: Create Specific, Manageable Tests

Come up with realistic instructions.

Question

Imagine you have a 20 GB file with one string per line.

Explain how you would sort the file.

Solution

Use External Sort. For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

1. Divide the file into chunks of 100MB each. Sort using quicksort.

2. Read the first 10 MB of each sorted chunk into input buffers in RAM and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)

3. [Important] Perform a 9-way merge and store the result in the output buffer. Whenever the output buffer fills, write it to the final sorted file and empty it. Whenever any of the 9 input buffers empties, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available.

Question

You have a stack of n boxes, with widths w., heights h, and depths d. The boxes can only be stacked on top of one another if each box is strictly larger than the box above it in width, height, and depth.

Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box.

Solution

This is appearantly a DP question. I did it in the normal way, and the solution turns out to be very good:

DP solution is        2638ms
Recursive solution is 1322ms
My solution is         370ms

I could not understand the 2 solutions given in the book. Sorry.

The coding is a bit lengthy, and we keeps 2 DP arrays. Not an easy question of course, but the solution is actually standard.

Code

public static ArrayList<Box> createStack(Box[] boxes) {
    ArrayList<Box> ans = new ArrayList<Box>();
    int len = boxes.length;
    int[] heights = new int[len];
    int[] preMap = new int[len];
    int maxIndex = 0;

    // start DP
    for (int i = 0; i < len; i++) {
        heights[i] = boxes[i].height;
        preMap[i] = -1;
        for (int j = 0; j < i; j++) {
            if (boxes[j].canBeAbove(boxes[i])) {
                int newHeight = heights[j] + boxes[i].height;
                if (newHeight > heights[i]) {
                    heights[i] = newHeight;
                    preMap[i] = j;
                }
            }
        }
        // now updated maxIndex
        if (heights[i] > heights[maxIndex]) {
            maxIndex = i;
        }
    }

    // print from maxIndex all the way backwards
    while (maxIndex != -1) {
        ans.add(boxes[maxIndex]);
        // the print order is reversed, so...
        maxIndex = preMap[maxIndex];
    }
    return ans;
}

Question

Given a boolean expression consisting of the symbols 0, 1, ‘&’, ‘|’, and ‘^’, and a desired boolean result value ‘result’.

Now implement a function to count the number of ways of parenthesizing the expression such that it evaluates to ‘result’.

Solution

This is a difficult question.

Each parenthesized expression must have an outermost pair of parentheses.

That is, we can iterate through the expression, treating each operator as the first operator to be parenthesized.

Nice idea suggested in the book! So for each operator, we consider is as first operator (to evaluate), and then we shall if the total possible count.

(Note that while coding, we DO NOT WRITE {if-else if-else…} but instead use {if… if… if…} in order to get the total count. )

DP is more time-efficient.

Like CC150v5 Q9.10, the code given in the book is very hard to read. I have my own code posted below.

Code

public static int countMyAnswer(String exp, boolean result) {
    if (exp.length() == 1) {
        return convertIntToBool(exp.charAt(0)) == result ? 1 : 0;
    }
    // eg. 1^0|0|1
    // result: true
    int totalCount = 0;
    for (int i = 1; i < exp.length(); i += 2) {

        char op = exp.charAt(i);
        String firstHalf = exp.substring(0, i);
        String secondHalf = exp.substring(i + 1);

        int firstHalfTrue = countMyAnswer(firstHalf, true);
        int firstHalfFalse = countMyAnswer(firstHalf, false);
        int secondHalfTrue = countMyAnswer(secondHalf, true);
        int secondHalfFalse = countMyAnswer(secondHalf, false);

        if (evaluate('0', op, '0') == result) {
            totalCount += firstHalfFalse * secondHalfFalse;
        }
        if (evaluate('0', op, '1') == result) {
            totalCount += firstHalfFalse * secondHalfTrue;
        }
        if (evaluate('1', op, '0') == result) {
            totalCount += firstHalfTrue * secondHalfFalse;
        }
        if (evaluate('1', op, '1') == result) {
            totalCount += firstHalfTrue * secondHalfTrue;
        }
    }
    return totalCount;
}

private static boolean convertIntToBool(char num) {
    if (num == '1') {
        return true;
    } else {
        return false;
    }
}

private static boolean evaluate(char num1, char op, char num2) {
    boolean b1 = convertIntToBool(num1);
    boolean b2 = convertIntToBool(num2);
    if (op == '&') {
        return b1 & b2;
    } else if (op == '|') {
        return b1 | b2;
    } else if (op == '^') {
        return b1 ^ b2;
    }
    System.out.println("Did not found operator " + op);
    return false;
}

Question

Implement the “paint fill” function that one might see on many image editing programs.

That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.

Solution

This is a BFS/DFS question, very similar to [LeetCode 130] Surrounded Regions.

However, this question is not same as surrounding region, because no temporary storage of state is needed, and we DO NOT NEED TO keep track of the visited positions!

Why is this?

1. This question, we simple change the color from A to B.
2. Surrounding Region is change A to B, and B to A.

That’s why, the nature of 2 questions are different.

Code 1 is my first solution, and Code 2 is doing a BFS and set color directly to expected value. This type of questions is highly frequent and sometimes may cause confusions.

Code

my code 1, with ‘temp’ state

public static void PaintFill1(Color[][] screen, int posX, int posY,
        Color ncolor) {
    // the queue keeps the list of positions that I'm going to visit
    Queue<Position> q = new LinkedList<Position>();
    int len = screen.length;
    Color original = screen[posX][posY];
    // visited origin node first
    q.offer(new Position(posX, posY));
    while (!q.isEmpty()) {
        // visit positions in q one by one (mark color as 'Temp')
        Position p = q.poll();
        if (p.x < 0 || p.x >= len || p.y < 0 || p.y >= len) {
            // invalid pos coordinate
            continue;
        } else if (screen[p.x][p.y] == Color.Temp
                || screen[p.x][p.y] != original) {
            continue;
        }
        screen[p.x][p.y] = Color.Temp;
        q.offer(new Position(p.x - 1, p.y));
        q.offer(new Position(p.x + 1, p.y));
        q.offer(new Position(p.x, p.y - 1));
        q.offer(new Position(p.x, p.y + 1));
    }
    // finish visiting all positions that's original color
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len; j++) {
            if (screen[i][j] == Color.Temp) {
                screen[i][j] = ncolor;
            }
        }
    }
}

my code 2, without ‘temp’ state

public static void PaintFill2(Color[][] screen, int posX, int posY,
        Color ncolor) {
    // the queue keeps the list of positions that I'm going to visit
    Queue<Position> q = new LinkedList<Position>();
    int len = screen.length;
    Color original = screen[posX][posY];
    // visited origin node first
    q.offer(new Position(posX, posY));
    while (!q.isEmpty()) {
        // visit positions in q one by one (mark color as 'Temp')
        Position p = q.poll();
        if (p.x < 0 || p.x >= len || p.y < 0 || p.y >= len) {
            // invalid pos coordinate
            continue;
        } else if (screen[p.x][p.y] != original) {
            continue;
        }
        screen[p.x][p.y] = ncolor;
        q.offer(new Position(p.x - 1, p.y));
        q.offer(new Position(p.x + 1, p.y));
        q.offer(new Position(p.x, p.y - 1));
        q.offer(new Position(p.x, p.y + 1));
    }
}

Question 1

A magic index in an array A[l.. .n-l] is defined to be an index such that A[i] = i.

Given a sorted array of distinct integers, write a method to find a magic index, if one exists, in array A.

Question 2

FOLLOW UP: What if the values are not distinct?

Solution

This is a difficult binary search question!

Question 1 is slightly easier: we simplyl use binary search, and we are able to discard half of the array each time.

1. if (array[mid] > mid), then we discard the right half.
2. if (array[mid] < mid), then we discard the left half.

Question 2 is difficult. We cannot discard half of the input any more. Instead, we discard a range between (mid) and (array[mid]). Then check left and right part seperately.

So, I wrote the following code:

int mid = left + (right - left) / 2;
if (array[mid] == mid) {
    return mid;
} else {
    int smaller = Math.min(array[mid], mid);
    int larger = Math.max(array[mid], mid);
    int leftResult = helper(array, left, smaller);
    if (leftResult != -1) {
        return leftResult;
    } else {
        return helper(array, larger, right);
    }
}

This becomes an endless loop. We did not discard point ‘mid’ in the code above. The correct code is posted below.

Code

code for non-duplicate input

public static int myAnswerNonDup(int[] array) {
    int len = array.length;
    return helper(array, 0, len - 1);
}

public static int helper(int[] array, int left, int right) {
    if (right < left) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (array[mid] == mid) {
        return mid;
    } else if (array[mid] < mid) {
        // discard all element to the left of array[mid]
        return helper(array, mid + 1, right);
    } else {
        return helper(array, left, mid - 1);
    }
}

code for have-duplicate input

public static int myAnswerWithDup(int[] array) {
    int len = array.length;
    return helper(array, 0, len - 1);
}

public static int helper(int[] array, int left, int right) {
    if (right < left) {
        return -1;
    }
    int mid = left + (right - left) / 2;
    if (array[mid] == mid) {
        return mid;
    } else {
        int smaller = 0;
        int larger = 0;
        if (array[mid] < mid) {
            smaller = array[mid];
            larger = mid + 1;
        } else if (array[mid] > mid) {
            smaller = mid - 1;
            larger = array[mid];
        }
        int leftResult = helper(array, left, smaller);
        if (leftResult != -1) {
            return leftResult;
        } else {
            return helper(array, larger, right);
        }
    }
}

Question

Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).

Solution

Mask odd and even bits seperately.

Code

public static int swapOddEvenBits(int x) {
    return (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
}

Question

link

给你一个password 假定6位

有个function, 每call一次就给你一个triplet 是password 里的随即三位(order不变)。比如google, 可能返回: ggl, goe, oog, ool…

问如何最有效破译这个密码?

Solution

This is just a rough idea suggested by Level 6 of this post.

六位密码随机给三位，应该有C(6, 3) = 20个bucket。

如果密码是abcdef，那么以a开头的bucket应该是 C(5, 2) = 10个。以b开头的buckt应该是C(4, 2) = 6个，以c开头的是3个，以d开头的是1个…. from this, we know the probability of the occurrance of each letter.

In this case, we generate many triplets, and calculate based on their frequencies. However, the guy also wrote about this condition:

如果abcd中间有相同(there are same letters in the 6-char password)，那么就会出现以a开头的是11个（abca)，13个(abad)，14个(abaa)，16个(aacd)，17个(aaca),19个(aaad)或者20个(aaaa).

思路是比较清楚，不过算法还要想想。

Code

not written

Question

Write a function to determine the number of bits (change) required to convert integer A to integer B.

Solution

Using XOR operation, we can find out number of bits that are different.

The next important thing is to know how to count the number of ‘1’s in a integer. It’s like this:

c = c & (c - l) clears the least significant bit of ‘1’.

Keep doing this until all ‘1’s are cleared.

Code

code 1

public static int calcBitsSwapMe1(int a, int b) {
    int num = a ^ b;
    int count = 0;
    while (num != 0) {
        count += num & 1;
        num = num >>> 1;
    }
    return count;
}

code 2

public static int calcBitsSwapMe2(int a, int b) {
    int num = a ^ b;
    int count = 0;
    while (num != 0) {
        num = num & (num - 1);
        count++;
    }
    return count;
}

Question

You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams.

Given a scale, how to find the heavy bottle only scaling ONCE?

Solution

Take 1 pill from Bottle 1, 2 pills from Bottle 2, and so on. We’ll expect (1 + 2 + … + 20) = 210 gram of pills.

The answer would be {(weight - 210 grams) / 0.1}.