53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

思路: DP的思路,用一个curSum跟maxSum来追踪.
复杂度 time O(n) space O(1)

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) 
            return Integer.MIN_VALUE;
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            curSum = curSum > 0 ? curSum + nums[i]: nums[i];
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }
}

150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
[“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9
[“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

思路: 用stack来实现, 数字就是入栈,运算符就pop出前两个值,进行计算再入栈。

public class Solution {
    public int evalRPN(String[] tokens) {
        if (tokens == null || tokens.length == 0) return 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < tokens.length; i++) {
            String token = tokens[i];
            if (!isOperator(token)) {
                stack.push(Integer.valueOf(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                int res = calculate(num1, num2, token);
                stack.push(res);
            }
        }
        return stack.peek();
    }

    public boolean isOperator(String op) {
        if (op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/")) return true;
        return false;
    }

    public int calculate(int num1, int num2, String op) {
        if (op.equals("+")) {
            return num1 + num2;
        } else if (op.equals("-")) {
            return num1 - num2;
        } else if (op.equals("*")) {
            return num1 * num2;
        } else if (op.equals("/")) {
            return num1 / num2;
        } else {
            return 0;
        }
    }
}

341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6]
思路: 用一个List来盛放flatten之后的元素,同时用一个index来取当前flatten list的元素。

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List&lt;NestedInteger&gt; getList();
 * }
 */
public class NestedIterator implements Iterator&lt;Integer&gt; {
    List&lt;Integer&gt; flatList;
    int index;

    public NestedIterator(List&lt;NestedInteger&gt; nestedList) {
        flatList = new ArrayList&lt;Integer&gt;();
        index = 0;
        dumpToList(nestedList, flatList);
    }

    public void dumpToList(List&lt;NestedInteger&gt; nestedList, List&lt;Integer&gt; flatList) {
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger()) {
                flatList.add(ni.getInteger());
            } else {
                dumpToList(ni.getList(), flatList);
            }
        }
    }


    @Override
    public Integer next() {
        if (hasNext()) {
            Integer result = flatList.get(index);
            index++;
            return result;
        } 
        return null;
    }

    @Override
    public boolean hasNext() {
        return index &lt; flatList.size();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */

进制转换题目总结

//十进制转26进制: 
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB 
public class Solution {
    public String convertToTitle(int n) {
        StringBuilder sb = new StringBuilder();
        while(n > 0) {
            n--;
            char ch = (char)(n % 26 + 'A');
            sb.append(ch);
            n = n / 26;
        }
        sb.reverse();
        return sb.toString();
    }
}
//26进制转10进制: 
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
public class Solution {
    public int titleToNumber(String s) {
        int res = 0;
        int power = 0;
        int n = s.length() - 1;
        for (int i = n; i >=0; i--) {
            int digit = s.charAt(i) - 'A' + 1;
            res += digit * Math.pow(26, power);
            power++;
        }
        return res;
    }
}
//十六进制转十进制:

//十进制转十六进制: 
public class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        while( num != 0) {
            sb.append(hex[num & 15]);
            num = num >>> 4;
        } 
        sb.reverse();
        return sb.toString();
    }
}

//Roman to Integer
public class Solution {
    public int romanToInt(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        char[] array = s.toCharArray();
        char base = array[array.length - 1]; // get the last char
        int res = map.get(base);
        for (int i = array.length - 2; i >= 0; i--) {
            if (map.get(base) <= map.get(array[i])) {
                res += map.get(array[i]);
            } else {
                res -= map.get(array[i]);
            }
            base = array[i];
        }
        return res;
    }
}

// Integer to Roman TODO

Database Sharding

http://www.25hoursaday.com/weblog/2009/01/16/BuildingScalableDatabasesProsAndConsOfVariousDatabaseShardingSchemes.aspx
Definition: the process of splitting up a database across multiple machines to improve the scalability of an application.

Why ?
Reach to a limit to original database.
Scale vertically too expensive. Limitation: RAM, CPU power, disk I/O, storage capacity. bandwidth.

Common Sharding Schemes:
主要思路: break up an application databse into multiple small dbs. Main schemas:

  1. Vertical Partitioning:
    思路: segment application databse to moves tables related to specific features to their own server. 也就是根据table的specific features来进行分割。
    举例: User table => 分割为 1. User profile table 2. friend lists table 3. user generated content table, e.g. photos, blogs. 3个table各放置在一台server上面
    Trade Off:
    Pro: approach is straightforward and low impact
    Cons: 随着site用户增长, 有些table可能需要继续拆分(further sharding a feature specific database across multiple servers), e.g. handing metadata queries for 10 billion photos by 140 million users .

  2. Range Based Partitioning
    需求场景: the entire dataset for a single feature or table still needs to be further subdivided across mutiple machines.
    思路: 1. split data based on values range that occur within each entity. e.g. sales transaction 可以根据created date 来分割; assigning users 可以根据zip code来划分
    Trade Offs:
    Pro:
    Cons: value range 选择不好,会导致unbalanced servers. sales transaction的例子可能会导致某些server的访问量巨大, user划分的例子是根据user evenly distribution划分的, 有些地区可能users跨zip的情况经常发生导致fail to account

  3. Key or Hash Based Partitioning
    需求场景: Web2.0 sites,每个user都在db中有个对应的数字 hash id, 来决定哪台server来服务这个user. e.g.10台database servers, 用户ID是个数字,每次新来一个用户,新用户分配的Id是之前用户的ID+1. 这种情况下Hash function可以选择UserID % 10 取余数, 用余数的值来决定哪台database server 来服务于这个用户.
    还有一种是对“Hash(key) mod N”的改进:假设我们要将数据分不到20台机器上,传统做法是hash(key) mod 20,而改进后,N取值要远大于20,比如是20000000,然后我们采用额外一张表记录每个节点存储的key的模值,比如:
    node1:0~1000000
    node2:1000001~2000000
    Trade Offs:
    Cons: 仅用于固定的servers数, 如果server增加也就意味着Hash Function也会变。

  4. Directory Based Partitioning
    需求场景: 根据 partitioning schema来创建个lookup service.这种松耦合结构可以有效的从原来的DB 层解耦,不用每次访问都提供db的access code。
    Trade Offs:
    Pros: 例如用GetDatabaseFor()方法来存储/返回一个从entity key-> 需求的database server的映射表. 这个映射表不会因为你partitioning scehma的改变而影响到你的app。
    例如针对之前10台db servers跟Hash function的问题,假如我们想新增5台servers, 并不想增加downtime。 我们可以保留当前的Hash function, 将这5台新增servers作为一个pool, 执行一个新的script 把根据新的hash Function数据从原来的10台servers拷贝到这5台新的servers上面(Tricky 用的用户持续update他们的信息)。 拷贝完成后, 原有的旧Hash function可以在以前的10台servers上面继续用。

    Problems Common to all Sharding schemas

    Joins and Denormalization

    Joining data from multiple shareds

    Rebalancing

198. House Robber I/II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

思路:
复杂度: Time O(n), Space O(n)

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] money = new int[nums.length + 1];
        money[0] = 0; // 第0次抢了0
        money[1] = nums[0]; // 第一次抢的nums[0]
        for (int i = 2; i &lt; nums.length + 1; i++) {
            money[i] = Math.max(money[i - 1], money[i - 2] + nums[i - 1]);
        }
        return money[nums.length];
    }
}

房子成环。
思路: 抢第一个就不能抢最后一个,不抢第一个抢不抢最后一个随意
两种情况:
1.抢第一间(第二间必须不抢,第三间随意),不抢最后一间(倒数第二间随意)
2.不抢第一间(第二间随意),最后一间抢不抢随意(倒数第二间也随意)

public class Solution {
    // 1 2 4 6 4
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        int n = nums.length;
        int[] robFirst = new int[n+1];
        int[] notRobFirst = new int[n+1];
        // init 
        robFirst[1] = nums[0];
        robFirst[2] = robFirst[1];
        notRobFirst[1] = 0;
        notRobFirst[2] = nums[1];

        for (int i = 3; i &lt;= n - 1; i++) { // 第三次抢到n-1次
            robFirst[i] = Math.max(nums[i - 1] + robFirst[i - 2], robFirst[i - 1]);
        }
        for (int i = 3; i &lt;= n; i++) { // 第三次抢到第n次
            notRobFirst[i] = Math.max(nums[i - 1] + notRobFirst[i - 2], notRobFirst[i-1]);
        }

        return Math.max(robFirst[n - 1], notRobFirst[n]);

    }
}

Top K 最大值(最小值)问题

Top K问题指的是从大量数据中获取前K个最大值或者最小值。 我们可以用miniHeap解决TopK最大值问题,或者MaxHeap解决TopK最小值问题, 时间复杂度O(nlogK)。

最小堆解决TopK最大值的解决方法就是:先去源数据中的K个元素放到一个长度为K的数组中去,再把数组转换成最小堆。再依次取源数据中的K个之后的数据和堆的根节点(数组的第一个元素)比较,根据最小堆的性质,根节点一定是堆中最小的元素,如果小于它,则直接pass,大于的话,就替换掉跟元素,并对根元素进行Heapify,直到源数据遍历结束。堆中元素就是TopK的最大元素。

Java 中实现Priority Queue.

 maxPQ = new PriorityQueue<Integer>();
 miniPQ = new PriorityQueue<Integer>(new Comparator<Integer>(){
        public int compare(Integer i1, Integer i2) {
            return i2 - i1;
        }
 });

Reference:
http://blog.csdn.net/xiao__gui/article/details/8687982
http://baozitraining.org/blog/mitbbs-google-k-largest-elements/