2015年11月25日星期三

Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
  • You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
  • After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int buy[] = new int[n];
        int sell[] = new int[n];
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            buy[i] = Math.max(buy[i - 1], (i == 1 ? 0 : sell[i - 2]) - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[n - 1];
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int buy = -prices[0];
        int sell = 0;
        int prevSell = 0;
       
        for (int i = 1; i < prices.length; i++) {
            int tmpBuy = buy;
            buy = Math.max(buy, prevSell - prices[i]);
            prevSell = sell;
            sell = Math.max(sell, tmpBuy + prices[i]);
        }
        return sell;
    }
}

Additive Number

Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Follow up:
How would you handle overflow for very large input integers?
Credits:
Special thanks to @jeantimex for adding this problem and creating all test cases


public class Solution {
    public boolean isAdditiveNumber(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }
        return helper(num, 0, null, null);
    }
   
    private boolean helper(String num, int position, String pre2, String pre1) {
        if (pre2 != null && pre1 != null) {
            String sum = addTwoNumber(pre2, pre1);
            if (num.substring(position).startsWith(sum)) {
                if (num.length() == position + sum.length()) {
                    return true;
                } else if (num.length() > position + sum.length()) {
                    return helper(num, position + sum.length(), pre1, sum);
                }
            }
            return false;
        } else if (position < num.length()) {
            for (int i = position; i < num.length(); i++) {
                if (i != position && num.charAt(position) == '0') continue;
                if (pre2 == null) {
                    if (helper(num, i + 1, num.substring(position, i + 1), pre1)) return true;
                } else if (pre1 == null) {
                    if (helper(num, i + 1, pre2, num.substring(position, i + 1))) return true;
                }
            }
        }
        return false;
    }
   
    public String addTwoNumber(String str1, String str2) {
        StringBuilder sb = new StringBuilder();
        int p1 = str1.length() - 1;
        int p2 = str2.length() - 1;
        int carry = 0;
        while (p1 >= 0 || p2 >= 0 || carry != 0) {
            int val = carry;
            val += p1 >= 0 ? (str1.charAt(p1) - '0') : 0;
            val += p2 >= 0 ? (str2.charAt(p2) - '0') : 0;
            carry = val / 10;
            val %= 10;
            sb.append(val);
            p1--;
            p2--;
        }
        return sb.reverse().toString();
    }
}

2015年11月23日星期一

Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Given m = 3, n = 3positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).
0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.
1 0 0
0 0 0   Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.
1 1 0
0 0 0   Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.
1 1 0
0 0 1   Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.
1 1 0
0 0 1   Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]
Challenge:
Can you do it in time complexity O(k log mn), where k is the length of the positions?

public class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[] roots = new int[m*n];
        Arrays.fill(roots, -1);
   
        int[] xOffset ={0, 0, 1, -1};
        int[] yOffset = {1, -1, 0, 0};
        List<Integer> result = new ArrayList<Integer>();
        for(int[] position : positions){
            int pointID = position[0]*n + position[1];
            roots[pointID] = pointID;
            int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
            for(int i = 0; i < 4; i++){
                int newX = xOffset[i] + position[0];
                int newY = yOffset[i] + position[1];
                if(newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1){
                    int root1 = find(newX * n + newY, roots);
                    if(root1 != pointID) count--;
                    roots[root1] = pointID;
                }
            }
            result.add(count);
        }
        return result;
    }
   
    public int find(int target, int[] roots){
        if(roots[target] == target) return target;
        return find(roots[target], roots);
    }
}

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

public class NumMatrix {
    int dp[][];
   
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1] - dp[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
}


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix = new NumMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.
public class NumArray {
   
    int[] sums;

    public NumArray(int[] nums) {
        this.sums = new int[nums.length + 1];
        sums[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            sums[i + 1] = nums[i] + sums[i];    
        }
    }

    public int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);

Smallest Rectangle Enclosing Black Pixels

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
For example, given the following image:
[
  "0010",
  "0110",
  "0100"
]
and x = 0y = 2,
Return 6.

public class Solution {
    public int minArea(char[][] image, int x, int y) {
        int left = getLeftRightMost(image, y, true);
        int right = getLeftRightMost(image, y, false);
        int up = getUpBottomMost(image, x, true);
        int bottom = getUpBottomMost(image, x, false);
        return (right - left + 1) * (-up + bottom + 1);
    }
   
    private int getUpBottomMost(char[][] image, int x, boolean up) {
        int height = image.length;
        int width = image[0].length;
        int start = up ? 0 : x;
        int end = up ? x : height - 1;
        int res = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            boolean black = false;
            for (int i = 0; i < width; i++) {
                if (image[mid][i] == '1') {
                    black = true;
                    break;
                }
            }
            if (!black) {
                if (up) start = mid + 1;
                else {
                    end = mid - 1;
                }
            } else {
                res = mid;
                if (up) end = mid - 1;
                else {
                    start = mid + 1;      
                }
            }
        }
        return res;
    }
   
    private int getLeftRightMost(char[][] image, int y, boolean left) {
        int height = image.length;
        int width = image[0].length;
        int start = left ? 0 : y;
        int end = left ? y : width - 1;
        int res = 0;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            boolean black = false;
            for (int i = 0; i < height; i++) {
                if (image[i][mid] == '1') {
                    black = true;
                    break;
                }
            }
            if (!black) {
                if (left) start = mid + 1;
                else end = mid - 1;
            } else {
                res = mid;
                if (left) end = mid - 1;
                else {
                    start = mid + 1;      
                }
            }
        }
        return res;
    }
}

2015年11月22日星期日

Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Note: The input string may contain letters other than the parentheses ( and ).
Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]
Credits:
Special thanks to @hpplayer for adding this problem and creating all test cases.

public class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res = new LinkedList<>();
        if (s == null) {
            return res;
        }
        //Remove proceeding ")".
        int i = 0;
        while (i < s.length() && s.charAt(i) != '(') i++;
        s = s.substring(0, i).replace(")", "") + ((i == s.length())?"" : s.substring(i));

        //Remove trailing "("
        int j = s.length() - 1;
        while (j >= 0 && s.charAt(j) != ')') j--;
        s = s.substring(0, j+1) + ((j == s.length()-1)? "" : s.substring(j+1).replace("(", ""));

        HashSet<String> visited = new HashSet<>();
        visited.add(s);
        LinkedList<String> queue = new LinkedList<>();
        queue.add(s);
        boolean isValid = false;
        while (!queue.isEmpty() && !isValid) {
            int count = queue.size();
            while (count-- > 0) {
                String str = queue.poll();
                if (isValid(str)) {
                    res.add(str);
                    isValid = true;
                } else {
                    for (int position = 0; position < str.length(); position++) {
                        if (str.charAt(position) != '(' && str.charAt(position) != ')') continue;
                        String nextStr = str.substring(0, position) + str.substring(position + 1);
                        if (visited.add(nextStr)) {
                            queue.add(nextStr);
                        }
                    }
                }
            }
        }
        return res;
    }
 
    private boolean isValid(String str) {
        int left = 0;
        for (char c : str.toCharArray()) {
            if (c == '(') {
                left++;
            } else if (c == ')') {
                left--;
                if (left < 0) return false;
            }
        }
        return left == 0;
    }
}

=================

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;

        for(int x : nums) {
            int i = binarySearch(dp, 0, len - 1, x);
            if(i < 0) i = -(i + 1);
            dp[i] = x;
            if(i == len) len++;
        }

        return len;
    }
   
    private int binarySearch(int[] dp, int start, int end, int element) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (dp[mid] == element) {
                return mid;
            } else if (dp[mid] > element) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -(start + 1);
    }
}

2015年11月15日星期日

zigzag print

1. zigzag print一个matrix,input: [ [1, 2, 3], [4, 5, 6] ] 
output: [ [1], [2, 4], [3, 5], [6] ]

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

public void zigzagPrint(List<List<Integer>> input) {
int index = 0;
boolean print = true;
while (print) {
print = false;
int tmpIndex = index;
for (List<Integer> list : input) {
if (tmpIndex < list.size()) {
print = true;
System.out.print(list.get(tmpIndex));
}
if (tmpIndex == 0) break;
tmpIndex--;
}
if (print)
System.out.println();
index++;
}
}

public static void main(String args[]) {
Solution solution = new Solution();
List<List<Integer>> input = new ArrayList<>();
input.add(Arrays.asList(1, 2, 3));
input.add(Arrays.asList(4, 5, 6));
solution.zigzagPrint(input);
}

}

Max Value using +, * and ()

第二轮是一个abc或者中国人,口语屌炸。问了我第二个intern proj。 开始想出Bigint,我说已经在电面做过了。 然后他就另外出了一个找最大值的题。给一个数组[1,1,2,1],然后用+ * ()三个操作求出这个数组的最大值,这个题返回6。 很简单,DP解决。我开始写了个用res[i][j] 表示的solution,然后写完代码,测了几个用例,都过了。然后他问如果数组里面有负数和0咋办呢。 我说维护两个表max[i][j] 和 min[i][j]。然后他很满意。我说其实还有复杂度更低的方法,可以用一位数组做。他说不用了,这个方法已经够好了,不要求写那么复杂。 然后面完还有10分钟,他问我有什么问题没有,我一听慌了,连时间都没有用完是不是不好,我就问他这个是不是没面好的征兆。他说不是不是,因为我已经很快给出solution,而且代码也没有问题,还给出了follow up的思路,就够了,说有时候时间没用完也是面的好的表现。 我听完心里放松了一些,然后和他唠了唠team之间的工作什么的,只是为了把时间耗完

public class Solution {
public int getMax(int[] nums) {
int n = nums.length;
int maxResult[][] = new int[n][n];
for (int len = 1; len <= n; len++) {
for (int start = 0; start < n; start++) {
int end = start + len - 1;
if (end >= n) {
continue;
}
if (start == end) {
maxResult[start][end] = nums[start];
continue;
}
for (int mid = start; mid < end; mid++) {
maxResult[start][end] = Math.max(maxResult[start][end],
Math.max(maxResult[start][mid] + maxResult[mid + 1][end],
maxResult[start][mid] * maxResult[mid + 1][end]));

}
}
}
return maxResult[0][n - 1];
}

public static void main(String args[]) {
Solution solution = new Solution();
System.out.println(solution.getMax(new int[] { 1, 1, 2, 1 }));
}
}

getWeight recurseive structure

1 given [1, [2,3], [[4]]], return sum. 计算sum的方法是每向下一个level权重+1, 例子的sum = 1 * 1 + (2 + 3) * 2 + 4 * 3。follow up:每向下一个level 权重 - 1, sum = 3 * 1 +(2 + 3)* 2 + 4 * 1 

import java.util.ArrayList;
import java.util.List;

public class Solution {

public static class Node {

}

public static class ValNode extends Node {
int val;
public ValNode(int v) {
this.val = v;
}
}

public static class ListNode extends Node {
List<Node> nodes;
public ListNode() {
nodes = new ArrayList<Node>();
}

public void addNode(Node node) {
this.nodes.add(node);
}
}

public static int getWeightIncrease(Node node, int weight) {
int res = 0;
if (node instanceof ValNode) {
res += weight * ((ValNode) node).val;
} else {
ListNode list = (ListNode) node;
for (Node child : list.nodes) {
res += getWeightIncrease(child, weight + 1);
}
}
return res;
}

public static void main(String args[]) {
ListNode all = new ListNode();
Node node1 = new ValNode(1);
ListNode node2 = new ListNode();
node2.addNode(new ValNode(2));
node2.addNode(new ValNode(3));

ListNode node3 = new ListNode();
ListNode sub = new ListNode();
node3.addNode(sub);
sub.addNode(new ValNode(4));

all.addNode(node1);
all.addNode(node2);
all.addNode(node3);

System.out.println(getWeightIncrease(all, 0));
}
}

print path from leftup to rightdown

M*N的地图上0表示可以走,1表示不能走,求从左上角到右下角的最短路径
很显然的BFS,也很快把基本的写出来了,然而我BFS每一步存了路径,大哥说这样内存消耗太大,怎么improve,然后在提示下想到每个node存一个路径上从哪来的信息,最后反过来打印。
然而悲剧就此来了,因为存的坐标信息是(x,y),python的tuple是immutable的,存[x,y]的list初始化成M*N又有问题。然后想着建个class用coordinates表示x,y,然后一直有bug,到结束了都没有run出来,面完多看了眼就发现初始化coordinate的class应该初始化M*N个而不是直接复制(那样都是引用,导致最后改一个都改了)。因为这种问题跪了真是不甘心

import java.util.LinkedList;

public class Solution {

public String findPath(int[][] board) {
int m = board.length;
int n = board[0].length;
LinkedList<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] { 0, 0 });
boolean find = false;
while (!queue.isEmpty()) {
int count = queue.size();
while (count-- > 0) {
int[] point = queue.poll();
int x = point[0];
int y = point[1];
if (x == m - 1 && y == n - 1) {
find = true;
break;
}
if (x > 0 && board[x - 1][y] == 0) {
board[x - 1][y] = 2;// up
queue.add(new int[] { x - 1, y });
}
if (x < m - 1 && board[x + 1][y] == 0) {
board[x + 1][y] = 3;// down
queue.add(new int[] { x + 1, y });
}
if (y > 0 && board[x][y - 1] == 0) {
board[x][y - 1] = 4;// left
queue.add(new int[] { x, y - 1 });
}
if (y < n - 1 && board[x][y + 1] == 0) {
board[x][y + 1] = 5;
queue.add(new int[] { x, y + 1 });
}
}
if (find) break;
}
if (!find) return "No Path";
String res = "";
int x = m - 1;
int y = n - 1;
while (x != 0 || y != 0) {
int dir = board[x][y];
if (dir == 2) {
res = "up ->" + res;
x++;
} else if (dir == 3) {
res = "down ->" + res;
x--;
} else if (dir == 4) {
res = "left ->" + res;
y++;
} else if (dir == 5) {
res = "right ->" + res;
y--;
}
}
return res;
}

public static void main(String args[]) {
Solution s = new Solution();
int[][] board = {{0, 1, 1, 1, 0}, {0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 1, 0}};
System.out.println(s.findPath(board));
}
}

Detect Cycle in a Directed Graph

Detect Cycle in a Directed Graph

Given a directed graph, check whether the graph contains a cycle or not. Your function should return true if the given graph contains at least one cycle, else return false. For example, the following graph contains three cycles 0->2->0, 0->1->2->0 and 3->3, so your function must return true.
Solution
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. In the following graph, there are 3 back edges, marked with cross sign. We can observe that these 3 back edges indicate 3 cycles present in the graph.

import java.util.ArrayList;
import java.util.List;

public class Solution {
int n;
public List<List<Integer>> adjList = new ArrayList<>();

public Solution(int n) {
this.n = n;
for (int i = 0; i < n; i++) {
adjList.add(new ArrayList<>());
}
}

public void addEdge(int from, int to) {
adjList.get(from).add(to);
}

public boolean hasCycle() {
boolean[] visited = new boolean[n];
boolean[] inStack = new boolean[n];
for (int i = 0; i < n; i++) {
if (!visited[i]) {
if (dfsCycle(i, visited, inStack)) {
return true;
}
}
}
return false;
}

private boolean dfsCycle(int start, boolean[] visited, boolean[] inStack) {
visited[start] = true;
inStack[start] = true;
for (int next : adjList.get(start)) {

if (!visited[start] && dfsCycle(next, visited, inStack)) {
return true;
} else if (inStack[next]) {
return true;
}
}
inStack[start] = false;
return false;
}

public static void main(String args[]) {
Solution g = new Solution(4);
g.addEdge(0, 1);
   g.addEdge(0, 2);
   g.addEdge(1, 2);
   g.addEdge(2, 0);
   g.addEdge(2, 3);
   g.addEdge(3, 3);
   System.out.println(g.hasCycle());
}
}

lowest common in multi-branch tree

给一个Employee类,有一个String name和一个List<Employee> directReport来表示一个公司的组织结构,然后给定一个公司的ceo和两个员工的名字,找到这两个员工的第一个common manager,给的两个员工一定存在。N-try tree的first common ancestor。楼主就用最naive的方法先找到从根到target节点的path然后在两个path中找第一个common ancestor。在电脑上写代码和测试样例,改掉测试样例的一个小bug之后通过。要求优化,说了用postorder traversal的方法来找,这样只需要遍历树一遍,说了一下整体的过程没有coding。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Solution {

public static class Employee {
List<Employee> employees;

String name;
int num;

public Employee(String name) {
this.name = name;
this.employees = new ArrayList<>();
}
}

private void outputTree(List<String> input) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}
updateNum(head);
print(head, "");
}

private void print(Employee emp, String prefix) {
System.out.println(prefix + "" + emp.name + " " + emp.num);
StringBuilder sb = new StringBuilder();
for (char c : prefix.toCharArray()) {
if (c == '\\') {
sb.append(' ');
} else if (c != '_' && c != '-') {
sb.append(c);
}
}
for (int i = 0; i < emp.employees.size(); i++) {
Employee emp2 = emp.employees.get(i);
if (i != emp.employees.size() - 1) {
print(emp2, sb.toString() + "|-");
} else {
print(emp2, sb.toString() + "\\_");
}
}
}

private int updateNum(Employee emp) {
int res = emp.num;
for (Employee emp2 : emp.employees) {
res += updateNum(emp2);
}
emp.num = res;
return res;
}

public String getCommon(List<String> input, String name1, String name2) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}

Employee common = getCommon(head, map.get(name1), map.get(name2));
return common.name;
}

private Employee getCommon(Employee root, Employee emp1, Employee emp2) {
if (root == emp1 || root == null || root == emp2) {
return root;
}
Employee find1 = null;
Employee find2 = null;
for (Employee child : root.employees) {
Employee find = getCommon(child, emp1, emp2);
if (find != null) {
if (find1 == null) {
find1 = find;
} else if (find2 == null) {
find2 = find;
}
}
}
if (find1 != null && find2 != null) {
return root;
} else {
return find1;
}
}

public static void main(String args[]) {
Solution s = new Solution();
List<String> list = Arrays.asList("Bob,Alice,3", "Carol,Bob,2",
"Richard,Carol,5", "Kim,Richard,5", "Tom,Carol,5",
"David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1", "Alice,,5",
"Chen,Eve,5", "Cen,Eve,2", "Eli,Cen,1", "Baba,Cen,2",
"Rui,Chen,2");
// List<String> list = Arrays.asList("Bob,Alice,3", "Alice,,5",
// "Cal,Alice,3");
// List<String> list = Arrays.asList("Alice,,5", "Bob,Alice,3",
// "Carol,Bob,2", "David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1");
s.outputTree(list);
System.out.println(s.getCommon(list, "Alice", "Tom"));
}
}

bigFloatAdd

稍微聊了下问了big float加法,中间有个compile error找了半天,找到以后有个小bug,改了下,大叔自己让我弄几个test case,测了下都过了,他自己测了下也没问题,然后就完了。又聊了一会,他说他希望new grad来了三个礼拜之内能ship feature。
解法:就是把一个float分成两部分,point之前的跟point之后的,然后用类似big int加法的做法做,先处理point之后的部分,然后处理之前的那部分,注意进位就行。

import java.util.Random;

public class Solution {

public String bigFloatAdd(String f1, String f2) {
String[] part1 = split(f1);
String[] part2 = split(f2);

StringBuilder floatSum = new StringBuilder();
int carry = addFloat(part1[1], part2[1], floatSum);
String integerSum = addInteger(part1[0], part2[0], carry);
return integerSum + "." + floatSum.reverse().toString();
}

private String[] split(String f1) {
int p1 = f1.indexOf(".");
String int1 = "";
String float1 = "";
if (p1 != -1) {
int1 = f1.substring(0, p1);
float1 = f1.substring(p1 + 1);
} else {
int1 = f1;
float1 = "";
}
return new String[]{int1, float1};
}

private int addFloat(String s1, String s2, StringBuilder sb) {
int len = Math.max(s1.length(), s2.length()) - 1;
int carry = 0;
while (len >= 0) {
int val = carry;
val += len < s1.length() ? s1.charAt(len) - '0' : 0;
val += len < s2.length() ? s2.charAt(len) - '0' : 0;
len--;
carry = val / 10;
sb.append(val % 10);
}
return carry;
}

private String addInteger(String s1, String s2, int carry) {
if (s1.isEmpty()) {
return s2;
}
if (s2.isEmpty()) {
return s1;
}
int i1 = s1.length() - 1;
int i2 = s2.length() - 1;
StringBuilder sb = new StringBuilder();
while (i1 >= 0 || i2 >= 0 || carry != 0) {
int val = carry;
val += i1 >= 0 ? s1.charAt(i1) - '0' : 0;
val += i2 >= 0 ? s2.charAt(i2) - '0' : 0;
carry = val / 10;
sb.append(val % 10);
i1--;
i2--;
}
return sb.reverse().toString();
}


public static void main(String args[]) {
Solution s = new Solution();
double d1 = 2.93;
double d2 = 107.08;
double sum = d1 + d2;
String strSum = s.bigFloatAdd(Double.toString(d1), Double.toString(d2));
System.out.println(d1 + "+" + d2 + "=" + sum + " == " + strSum);
}
}

pretty print organization

Employee,Manager,ItemsSold
Alice,,5
Bob,Alice,3. 1point 3acres 璁哄潧
Carol,Bob,2
Richard,Carol,5
Kim,Richard,5
Tom,Carol,5. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
David,Bob,3
Eve,Alice,2-google 1point3acres
Ferris,Eve,1
就是员工跟他的manager还有销售的item,之后输出下面的结构,数字表示该员工跟他下属的sold item总额. 1point 3acres 璁哄潧
Alice 31
|-Bob 23
| |-Carol 17
| | |-Richard 10
| | | \_Kim 5
| | \_Tom 5
| \_David 3
\_Eve 3
  \_Ferris 1
解法:这题略坑,算法就是先建图然后跑dfs,主要是output很恶心,output也是用dfs做的,当时写到最后还是差一些,这个output给大家一点参考吧,如果你的代码能输出上面那个例子,应该已经过了。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Solution {

public static class Employee {
List<Employee> employees;

String name;
int num;

public Employee(String name) {
this.name = name;
this.employees = new ArrayList<>();
}
}

private void outputTree(List<String> input) {
HashMap<String, Employee> map = new HashMap<>();
Employee head = null;
for (String entry : input) {
String tokens[] = entry.split("\\,");
Employee employee = map.get(tokens[0]);
if (employee == null) {
employee = new Employee(tokens[0]);
map.put(tokens[0], employee);
}
employee.num = Integer.parseInt(tokens[2]);
if (tokens[1].isEmpty()) {
head = employee;
continue;
}
Employee manager = map.get(tokens[1]);
if (manager == null) {
manager = new Employee(tokens[1]);
map.put(tokens[1], manager);
}
manager.employees.add(employee);
}
updateNum(head);
print(head, "");
}

private void print(Employee emp, String prefix) {
System.out.println(prefix + "" + emp.name + " " + emp.num);
StringBuilder sb = new StringBuilder();
for (char c : prefix.toCharArray()) {
if (c == '\\') {
sb.append(' ');
} else if (c != '_' && c != '-') {
sb.append(c);
}
}
for (int i = 0; i < emp.employees.size(); i++) {
Employee emp2 = emp.employees.get(i);
if (i != emp.employees.size() - 1) {
print(emp2, sb.toString() + "|-");
} else {
print(emp2, sb.toString() + "\\_");
}
}
}

private int updateNum(Employee emp) {
int res = emp.num;
for (Employee emp2 : emp.employees) {
res += updateNum(emp2);
}
emp.num = res;
return res;
}

public static void main(String args[]) {
Solution s = new Solution();
// List<String> list = Arrays.asList("Bob,Alice,3", "Carol,Bob,2",
// "Richard,Carol,5", "Kim,Richard,5", "Tom,Carol,5",
// "David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1", "Alice,,5",
// "Chen,Eve,5", "Cen,Eve,2", "Eli,Cen,1", "Baba,Cen,2", "Rui,Chen,2");
List<String> list = Arrays.asList("Bob,Alice,3", "Alice,,5","Cal,Alice,3");
// List<String> list = Arrays.asList("Alice,,5", "Bob,Alice,3",
// "Carol,Bob,2", "David,Bob,3", "Eve,Alice,2", "Ferris,Eve,1");
s.outputTree(list);
}
}