google题

发信人: xiaoyouyi (yy), 信区: JobHunting
标  题: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 04:06:43 2014, 美东)

假设你是harry potter，在grid的左上角，你现在要走到右下角，grid中有
正数也有负数，遇到正数表示你的strength增加那么多，遇到负数表示strength减少那
么多，在任何时刻如果你的strength小于等于0，那么你就挂了。在一开始你有一定的
初始的strength，现在问这个初始的strength最少是多少，才能保证你能够找到一条路
走到右下角。每一步只能向右或者向下。

发信人: blaze (狂且), 信区: JobHunting
标  题: Re: G家题讨论： harry potter 走矩阵
发信站: BBS 未名空间站 (Sun Jan 19 14:12:05 2014, 美东)

Just dp:
f是dp函数的值，表示从当前的点走到目标最少需要多少能量。

w是当前点上的权重，可以是正的或者负的。

f(m, n) = 0

f(i, j) = min(
  max(f(i+1, j) - w(i+1,j), 0),
  max(f(i, j+1) - w(i, j+1), 0)
)


每个点计算当前点到目标的最 小能量要求。当前点只能走到下面或右面的点。如果走下面的点，那么最小要求是下面 点的最小要求减去下面那个点的值。如果发现小于0则是0。右面的点同理。然后两种情 况取最小作为当前点的最小能量要求即可。



发信人: CodeSwim (CodeSwim), 信区: JobHunting
标  题: GG面经
发信站: BBS 未名空间站 (Tue Jan 20 12:55:43 2015, 美东)

前两天面了GG, 刚收到feedback说通过. 下面是面经:
白人小伙, 一上来什么都没说,直接开题.

第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有
match的字符串.
给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表
达式的做法; 面试官说用trie来实现吧. 先构建trie, 然后把搜索函数写出来. 没什么
好说的 从头开始写. 完成后写了个简单的test case, 和他一起过了一遍;

第二题, deep copy linked list. 给了两种方案, 一是hashmap based Time O(n) +
Space O(n); 一是直接对List拆分deep拷贝 然后再恢复原list Time O(n) + Space O(
1)。
面试官让分析了下两种方法的优劣. 然后说实现下第二种吧. 我刚把思路说完正打算写
代码, 然后考官打断说时间不太够了,实现第一种吧. 于是一口气写完. 给了个test
case过了一遍. 最后考官问代码里有没有问题, 我又从头仔细和他过了一遍,没发现.
问他给点提示, 他说他也没发现... 于是让问问题. 结束. 

Maximum Subarray

     int maxSubArray(int A[], int n) {
        vector<int > dp(n,0);
        dp[0]=A[0];
        int amax=A[0];
        for(int i=1;i<n;i++){
            dp[i]=A[i]+(dp[i-1]>0?dp[i-1]:0);
            amax=max(dp[i],amax);
        }
        return amax;
    }
 //less space
    int maxSubArray(int A[], int n) {
        int mx,pre;
        mx=pre=A[0];
        for(int i=1;i<n;i++){
            if(pre>0)
                {pre+=A[i];}
            else
                pre=A[i];
            if(pre>mx) mx=pre;   
        }
        return mx;       
    }

Word Break

    wordB[i] means whether the substring [0, i] is true.

bool wordBreak(string s, unordered_set<string> &dict) {
        vector<bool> wordB(s.length() + 1, false);
        wordB[0] = true;
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
                    wordB[i] = true;
                    break;
                }
            }
        }
        return wordB[s.length()];
    }

Edit Distance -interesting

Use dp[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]):
if c == d, then : dp[i][j] = dp[i-1][j-1]
Otherwise we can use three operations to convert word1 to word2:
(a) if we replaced c with d: dp[i][j] = dp[i-1][j-1] + 1;
(b) if we added d after c: dp[i][j] = dp[i][j-1] + 1;
(c) if we deleted c: dp[i][j] = dp[i-1][j] + 1;


class Solution {
public:
    int minDistance(string word1, string word2) {
        return minDistance_2(word1, word2);
    }
    int minDistance_1(string word1, string word2) {
        int M = word1.size(), N = word2.size();
        int dp[N+1][M+1];
        for (int j = 0; j <= M; j++)
            dp[0][j] = j;
        for (int i = 0; i <= N; i++)
            dp[i][0] = i;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= M; j++)
                if (word2[i-1] == word1[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j])) + 1;
        return dp[N][M];
    }
    int minDistance_2(string word1, string word2) {
        int M = word1.size(), N = word2.size();
        int dp[N+1];
        for (int j = 0; j <= N; ++j)
            dp[j] = j;
        for (int i = 1; i <= M; ++i)
        {
            int upperLeftBackup = dp[0];
            dp[0] = i;
            for (int j = 1; j <= N; ++j)
            {
                int upperLeft = upperLeftBackup;
                upperLeftBackup = dp[j];
                if (word1[i-1] == word2[j-1])
                    dp[j] = upperLeft;
                else
                    dp[j] = min(min(dp[j-1], dp[j]), upperLeft) + 1;
            }
        }
        return dp[N];
    }
};

Regular Expression Matching

the res[i][j] means preceding substring of length i of s and length j of p. For any two substrings, res[i][j] is true if and only if one of the following cases is satisfied:
case A: the j th character of p is not '*'

• case 1: res[i-1][j-1] is true, and ith character of s is equal to j th character of p. Or j th character of p is '.'

case B: the j th character of p is '*'

• case 2:res[i-1][j] is true, the preceding character of '*' matches incoming character of s, and the pattern like (a*) will match one or more a.

• case 3: res[i][j-2] is true, and the pattern like (a*) will match an empty string

base case is the res[0][0], res[i][0], res[0][j].

note that in the above algorithm description, the index i, j starts from 1.

    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') return *s == '\0';  //empty
        int lens=strlen(s);
        int lenp=strlen(p);
        bool res[lens+1][lenp+1];

        for(int i=0;i<lens+1;i++)
            for(int j=0;j<lenp+1;j++)
                res[i][j]=false;
       
        res[0][0]=true;//base case
        for(int j=0;j<lenp;j++){//base case of res[0][j+1]
               if(p[j]=='*'){
                 if(j>0&&res[0][j-1]) res[0][j+1]=true;
               }
        }
        for(int j=0;j<lenp;j++)// the position of these two lines can be changed.
        for(int i=0;i<lens;i++)
         {
             if(p[j]=='*'){
                if(j<1) cout<<"error input for p"<<endl;
                 if(res[i+1][j-1]||(res[i][j+1]&&(p[j-1]=='.' || p[j-1]==s[i])))
                    res[i+1][j+1]=true;         
             }
             else{
                    if(p[j]=='.'||p[j]==s[i])
                         res[i+1][j+1]=res[i][j];
            }      
         }
        return res[lens][lenp];
    }

//same idea , use only O(m) space
use OPT and PRE array to save the current optimal and previous optimal to avoid 2 dimensional space.

    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') return *s == '\0';  //empty
        int m = strlen(p), n = strlen(s);
        bool * OPT = new bool[m+1];
        bool * PRE = new bool[m+1];
        PRE[0] = true;//base case
        for (int j = 1; j <= m; ++j)//base case
            PRE[j] = (j >= 2 && p[j-1] == '*') && PRE[j-2];
          
        OPT[0] = false;//base case, because for i=1...n, res[i][0]=false;
        for (int i = 1; i <= n; ++i){
            for (int j = 1; j <= m; ++j){
             
                OPT[j] = ((p[j-1] == s[i-1] || p[j-1] == '.') && PRE[j-1]) ||
                            ((p[j-1] == '*' && (p[j-2] == s[i-1] || p[j-2] == '.')) && PRE[j]) ||
                            (j-2 >= 0 && p[j-1] == '*' && OPT[j-2]);
            }
            for (int j = 0; j <= m; ++j)
                PRE[j] = OPT[j];
        }
        return PRE[m];
    }


// a recursive version

    bool matchFirst(const char *s, const char *p){
        return (*p == *s || (*p == '.' && *s != '\0'));
    }

    bool isMatch(const char *s, const char *p) {
        if (*p == '\0') return *s == '\0';  //empty
   
        if (*(p + 1) != '*') {//without *
            return matchFirst(s,p)&&isMatch(s + 1, p + 1);
        } else { //next: with a *
            if(isMatch(s, p + 2)) return true;    //try the length of 0
            while ( matchFirst(s,p) )       //try all possible lengths
                if (isMatch(++s, p + 2))return true;
        }

        return false;
    } 

Palindrome Partitioning II -interesting

 //there is a related problem: longest palindrome substring
Note that in the following solution, to accommodate the dp computation of palin, we define dp[i] to be the mincut for the substring from i to the end.
     int minCut(string str) {
        int leng = str.size();

        int dp[leng+1];
        bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i-1;
      for(int i = 0; i < leng; i++)
          for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(str[i] == str[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0];
    }

 //one dimension dp, by anniekim
   int minCut(string s) {
        int N = s.size();
        bool isP[N];
        int dp[N];
        dp[0] = 0;
        for (int i = 1; i < N; ++i)
        {
            isP[i] = true;
            dp[i] = dp[i-1] + 1;
            for (int j = 0; j < i; ++j)
            {
                isP[j] = (s[i] == s[j]) ? isP[j+1] : false; // isP[j] == true -> [j...i] is a palindrome
                                                            // isP[j+1] == true -> [j+1...i-1] is a palindrome
                if (isP[j])
                    dp[i] = (j == 0) ? 0 : min(dp[i], dp[j-1] + 1); // dp[i] -> minCount for [0...i]
            }
        }
        return dp[N-1];
    }

Longest Palindromic Substring

first method: dp

    string longestPalindrome(string s) {
        if(s.length()==0)
            return "";
        bool palin[1000][1000] = {false};
        int maxLen = 0;
        int maxstart=0;
        for(int i=s.length()-1;i>=0;i--)
        {
            for(int j=i;j<s.length();j++)
            {
                if(s[i]==s[j] && (j-i<=2 || palin[i+1][j-1]))
                {
                    palin[i][j] = true;
                    if(maxLen<j-i+1)
                    {
                        maxLen=j-i+1;
                        maxstart=i;
                    }
                }
            }
        }
        return s.substr(maxstart,maxLen); 
    }

second method: Time O(n), Space O(n) (Manacher's Algorithm)
 the code is generally adopted from leetcode, but i have changed a little to satisfy my understanding.  There is another flavor written by anniekim.

string preProcess(const string &s) {
  int n = s.length();

  string ret;
  for (int i = 0; i < n; i++)
    ret += "#" + s.substr(i, 1);

  ret += "#";
  return ret;
}

string longestPalindrome(string s) {
  string T = preProcess(s);
  int n = T.length();
  int *P = new int[n];
  int C = 0, R = 0;
  for (int i = 0; i < n; i++) {
    int i_mirror = 2*C-i; // equals to i' = C - (i-C)
   
    P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
   
    // Attempt to expand palindrome centered at i
    while (T[i + 1 + P[i]] == T[i - 1 - P[i]])//actually need to check if the index is in the range.
      P[i]++;

    // If palindrome centered at i expand past R,
    // adjust center based on expanded palindrome.
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }

  // Find the maximum element in P.
  int maxLen = 0;
  int centerIndex = 0;
  for (int i = 0; i < n; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  delete[] P;
 
  return s.substr((centerIndex  - maxLen)/2, maxLen);
}

Maximum Product Subarray

dp, three flavors of code are provided:

    //f[k] means maximum product that can be achieved ending with k
    //g[k] means minimum product that can be achieved ending with k

f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
g(k) = min( f(k-1) * A[k], A[k], g(k-1) * A[k] )

     int maxProduct3(int  A[],int n) {
        if (n<1)  return 0;
   
        vector<int> f(n,0),g(n,0);
        f[0] = A[0];
        g[0] = A[0];
        int res = A[0];
        for (int i = 1; i < n; i++) {
            f[i] = max(max(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
            g[i] = min(min(f[i - 1] * A[i], g[i - 1] * A[i]), A[i]);
            res = max(res, f[i]);
        }
        return res;
    }

//convert the above one to use less space
    int maxProduct(int A[], int n) {
         if (n<1)  return 0;

        int f= A[0];
        int g= A[0];
        int res = A[0];
        for (int i = 1; i < n; i++) {
            int tmp=f;
            f = max(max(f * A[i], g* A[i]), A[i]);
            g = min(min(tmp * A[i], g* A[i]), A[i]);
            res = max(res, f);
        }
        return res;      
    }

//other flavors
    int maxProduct11(int A[], int n) {
        if (n < 1) return 0;
        int r = A[0];
        int max_p = A[0];
        // max_p is the maximum product that could be achieved
        // from the subarrays ending at the current position.
        int min_p = A[0];
        // The minimum product that could be achieved from
        // the subarrays ending at the current position.
        for(int i=1; i<n; i++){
            // The maximum or minimum product of the subarrays
            // ending at the current position could be achieved from the next three values.
            int a = max_p*A[i];
            // the max product of subarray ending at the previous position multiply the current value
            int b = min_p*A[i];
            // the minimum product of subarray ending at the previous position multiply the current value
            int c = A[i];
            // the current value
            max_p = max(max(a,  b),  c);
            min_p = min(min(a,  b),  c);
            if (max_p > r) r = max_p;
        }
        return r; 
    }
    //same idea way 2
    int maxProduct(int A[], int n) {
    if(n==1) return A[0];
    int pMax=0, nMax=0, m = 0;
    for(int i=0; i<n; i++){
        if(A[i]<0) swap(pMax, nMax);
        pMax = max(pMax*A[i], A[i]);
        nMax = min(nMax*A[i], A[i]);
        m = max(m, pMax);
    }
    return m;
    }