chuanying

// you can also use includes, for example:
// #include <algorithm>
#include <list>
int solution(const vector<int> &D, const vector<int> &P, int T) {
    // write your code here...
    list< pair<int, int> > tank; //油箱里面都装了些什么油,由便宜到贵排序的
    int curr = 0;
    long long cost = 0;
    for (int i = 0; i < D.size(); ++i) {
        while (!tank.empty() && P[i] < tank.back().first) { //油箱里面有比这个加油站还贵的油, 全部扔掉

chuanying

方勤 分享的题:

1. Implement pop_heap http://en.cppreference.com/w/cpp/algorithm/pop_heap
2. Zero one Knapsack https://github.com/soulmachine/acm-cheat-sheet/tree/master/C%2B%2B 的 10.5.1

贺峰 分享的题:

1. FlatIterator iterator的iterator
2. bool hasNext()

chuanying

System Design Problems:

1. Amazon S3

   1. Support one file more than 1TB, how to design the system to meet the requirement?

2. TinyURL:

   1. We should provide a tinyurl service(two main interface: post long url to get the tinyurl, post tinyurl to get the tinyurl). The tinyurl should be as shorter as possible.
      1. More than 10 billion url in total
      2. More than 100 thousands long url to tinyurl requests per second

3. More than 1 million tinyurl to long url requests per second

chuanying

//f(i,j) = f(i+1, j) + (S[i] == T[j]) * f(i+1,j+1)
//means numDistinct(S.substr(i), T.substr(j))
int numDistinct(string S, string T) {
    vector<vector<int> > dp(S.length() + 1, vector<int>(T.length() + 1, 0));
    dp[S.length()][T.length()] = 1;
    for (int i = S.length() - 1; i >= 0; --i) {
        dp[i][T.length()] = 1; //!! empty is every string's subseq
        for (int j = T.length() - 1; j >= 0; --j) {
            dp[i][j] = dp[i+1][j];
            if (S[i] == T[j]) {

chuanying

//https://code.google.com/codejam/contest/2270488/dashboard#s=p1
int main()
{
    int test_case_num = 0;
    cin >> test_case_num;
    for (int test_case=1; test_case <= test_case_num; test_case++) {
        int N, M;
        cin >> N >> M;
        vector<vector<int> > lawn(N, vector<int>(M, 100));
        for (int i = 0; i < N; i++) {

chuanying

//给定两个日期, 求他们相差的天数
bool leapyear(int y) {
    return (y%4 == 0) && (0 != y%100 || y%400 == 0);
}

int days(int y, int m, int d) {
    //static int mt[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    static int mt[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};
    int x = y-1;
    int ans = x*365 + x/4 - x/100 + x/400;

chuanying

int numTrees(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = dp[1] = 1;
    for(int i=2;i<=n;i++) {
        //there will be one value at the root, with whatever remains 
        // on the left and right each forming their own subtrees. 
        // Iterate through all the values that could be the root... 
        for(int j=0;j<i;j++) {
            dp[i] += dp[j] * dp[i-j-1];
        } 

chuanying

vector<int> inorderTraversal_moris(TreeNode *root) {
    vector<int> ans;
    TreeNode* curr = root;
    while(curr) {
        if(curr->left) {
            TreeNode* p = curr->left;
            //find the right-most child, remember to check cycle
            while(p->right && p->right != curr) {
                p = p->right;
            }