Word Search

 dfs
class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        if(board.size()==0) return false;
        if(word.length()==0) return true;
       
        int row=board.size(),col=board[0].size();
         vector<vector<bool>>used(row,vector<bool>(col,false));
        
         for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
               if(search(board,word,0,i,j,used))
                return true;
        return false;       
       
       
    }
    bool search(vector<vector<char> > &board, string word, int index,int i,int j, vector<vector<bool>>&used){
        if(index==word.length()) return true;
        if(i<0||j<0||i>=board.size()||j>=board[0].size()||used[i][j]||word[index]!=board[i][j])
            return false;
        used[i][j]=true;   
        bool res=search(board,word,index+1,i-1,j,used)
               ||search(board,word,index+1,i+1,j,used)
               ||search(board,word,index+1,i,j-1,used)
               ||search(board,word,index+1,i,j+1,used);
       
        used[i][j]=false;
        return res;
        //the above two line can be replaced by:
        //if(res) return true;
        //used[i][j]=false;
        //return false;
    }
};


//another flavor
public boolean exist(char[][] board, String word) {
    if(board == null) return false;
    if(word == null || word.length() == 0) return true;
    boolean [][] visited = new boolean[board.length][board[0].length];
    for(int i = 0; i < board.length; i++)
        for(int j = 0; j < board[0].length; j++)
            if(DFS(board, i, j, word, 0, visited)) return true;
    return false;
}
public boolean DFS(char[][] b, int i, int j, String word, int index, boolean[][] v){
    if(v[i][j] || b[i][j] != word.charAt(index)) return false;
    if(index == word.length() - 1) return true;
    v[i][j] = true;
    if(i != 0 && DFS(b, i - 1, j, word, index + 1, v)) return true;                  
    if(i != b.length - 1 && DFS(b, i + 1, j, word, index + 1, v)) return true;
    if(j != 0 && DFS(b, i, j - 1, word, index + 1, v)) return true;
    if(j != b[0].length - 1 && DFS(b, i, j + 1, word, index + 1, v)) return true;
    v[i][j] = false;
    return false;
}

facebook面经 interval problem

 determine the minimum number of meeting rooms needed to hold all the
meetings.
Input array(pair(1, 4), pair(2,3), pair(3,4), pair(4,5))
 Output: 2


Ans:

treat each start and end time as a point, sort the points,
now process each point in order,
if hit a start time, cnt ++
if hit an end time, cnt --

the max of cnt in the process is the number of meeting rooms needed.

there is one catch
这个解法有个注意事项，如果interval 1的start time 和interval 2 的end time相等
，应该把 interval 2的 end time排在前面

不然像（２，　３），(3, 4)这样的可能返回2，实际应该返回1.


The following is a wrong dp solution:
 按pair.first sort,
f[i]为从第0个到第i个时间段需要的最小房间数
那么if(pair[i].first>=pair[i-1].second) f[i]=f[i-1]
else f[i]=f[i-1]+1

counterexample:（1，3）（2，6），（4，5）
 the result of the algo is 3, but the correct answer is 2

Google 电面两道算法题

 2014.11. from 1point3

1.找出missing number 范围
number范围[0,99]

input: [0, 1, 2,50 , 52, 75]

output: "3-49,51,53-74,76-99"

2. 找出一个数由最少几个平方的和的组成
例子：
input： 14    output:  9 ,4 , 1  虽然也能由1 +1 +....+1组成 但长度是14 不是最优解

input:   50     ouput :  25, 25

Ans:
1. idea from the solution the leetcode problem: Longest Consecutive Sequence
use the map property that the key is sorted

 int merge(map<int, int> &amap, int left, int right) {
    int upper = right + amap[right] - 1;
    int lower = left - amap[left] + 1;
    int len = upper - lower + 1;
    amap[upper]= len;
    amap[lower]= len;
    return len;
}

//the range is [start, end]
int missingRanges(vector<int> & a,int start,int end) {
    map<int, int> amap;
    for (int i=0;i<a.size();i++) {
        if (amap.count(a[i])) continue;
        amap[a[i]]=1;
        if (amap.count(a[i]-1)) {
            merge(amap, a[i]-1, a[i]);
        }
        if (amap.count(a[i]+ 1) ){
            merge(amap, a[i], a[i]+1);
        }
    }

    for(auto it=amap.begin();it!=amap.end();it++){
        if(start==it->first){
            start=it->first+it->second;
        }
        else if(start<it->first){
            cout<<start<<"-"<<it->first-1<<", ";
            start=it->first+it->second;
        }
    }
    if(start<=end)
        cout<<start<<"-"<<end<<"\n";
    return 0;
}

2. dp, first one
int minNumber1(int num){
    vector<int> dp(num+1);
    dp[0]=0;
    for(int i=1;i<=(int)(sqrt((double)num));i++)
        dp[i*i]=1;
    for(int i=2;i<=num;i++){
        if(dp[i]!=0) continue;
        int amin=INT_MAX;
        for(int k=1;k<=i/2;k++){
            amin=min(amin,dp[k]+dp[i-k]);
            if(amin==2)
                break;
        }
        dp[i]=amin;
    }
    return dp[num];
}

//another flavor, faster.
int minNumber2(int n){
    vector<int> f(n+1);
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n ; i++){
        int amin = INT_MAX;
        for(int k=1;k*k<=i;k++){
            int cur = 1 + f[i-k*k];
            amin = min(amin, cur);
        }
        f[i] = amin;
    }
    return f[n];
}

Quick sort

quicksort(A,p,r){
    if (p<r){
        q=partition(A,p,r);
        quicksort(A,p,q-1);
        quicksort(A,q+1,r);
    }
}

 partition(A,p,r){
    i=p-1;
    for(int j=p;j<r;j++){
        if (A[j]<=A[r]){
            swap(A[++i],A[j])
        }
    }
    swap(A[i+1],A[r]);
    return i+1;
}

string question: example using kmp

A家的电面题:

有一种String,是把一个更短的String重复n次而构成的，那个更短的String长度至少为
2，输入一个String写代码返回T或者F
例子：
"abcabcabc"  Ture   因为它把abc重复3次构成
"bcdbcdbcde" False  最后一个是bcde
"abcdabcd"   True   因为它是abcd重复2次构成
"xyz"       False  因为它不是某一个String重复
"aaaaaaaaaa"  False  重复的短String长度应至少为2（这里不能看做aa重复5次)

要求算法复杂度为O(n)

public boolean isMultiple(String s){

}


Ans:

用KMP吧。检查preprocess部分生产的array pai 就可以了。如果是valid case.
preprocessing array 必然满足下面的几个条件：
1. pai[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-pai[n-1])就是repeating pattern;
3. pai[n-1]/(length of the repeating pattern) >= 1;
4. pai[n-1] % (length of the repeating pattern) == 0.

bool isMultiple(const string &text){
    int n=text.length();
    vector<int> pai(n);
    computeVec(text,pai);
    int len=n-pai[n-1];
    return len>1&&pai[n-1]/len>=1&&pai[n-1]%len==0;
}

void computeVec(const string &Pat, vector<int>&pai){//from KMP
    pai[0]=0;
    int k=0;
    int m=Pat.length();
    for(int i=1;i<m;i++){
        while(k>0&&Pat[k]!=Pat[i])
            k=pai[k-1];
        if(Pat[k]==Pat[i])
            k++;
        pai[i]=k;
    }
}

未名空间十大: G家面经总结，顺便求个bless，和一起找工作的同学们共勉

未名空间十大: G家面经总结，顺便求个bless，和一起找工作的同学们共勉: 发信人: freepooh (freepooh), 信区: JobHunting 标  题: G家面经总结，顺便求个bless，和一起找工作的同学们共勉 发信站: BBS 未名空间站 (Fri Apr  4 11:13:06 2014, 美东) 也找工作了一段时间了，从...

kmp string match

from CLRS(Introduction to Algorithm)

For a pattern P, pai[q] is the length of the longest prefix of P that is a proper suffix of Pq. (Pq is P[1...q], note that here the index start from 1, which is different from the code below)

vector<int> computepai(string Pat){
    int n=Pat.length();
    vector<int> pai(n,0);
    pai[0]=0;

    for(int i=1;i<n;i++){
        int k=pai[i-1];//number of characters matched
        while(k>0&&Pat[k]!=Pat[i])
            k=pai[k-1];
        k+=Pat[k]==Pat[i];

        pai[i]=k;
    }
    return pai;
}

下面这个computepai是算法导论上的版本，和上面的几乎一样（不同的只是k的位置），但是上面的似乎更容易理解和记忆些。
vector<int> computepai(string Pat){
    int n=Pat.length();
    vector<int> pai(n,0);
    pai[0]=0;
    int k=0;//number of characters matched
    for(int i=1;i<n;i++){
        while(k>0&&Pat[k]!=Pat[i])
            k=pai[k-1];
        if(Pat[k]==Pat[i])
            k++;
        pai[i]=k;
    }
    return pai;
}

void matchstr(string text,string Pat){
    int n=text.length();
    int m=Pat.length();
    vector<int> pai= computepai(Pat);
    int k=0;//number of characters matched
    for(int i=0;i<n;i++){//scan the text from left to right
        while(k>0&&Pat[k]!=text[i])
            k=pai[k-1];   //next character of P doesn't match text[i]
        if(Pat[k]==text[i])
            k++;       //next character matches
        if(k==m){  // is all of P matched
            cout<<"find in pos : "<<i-m+1<<"  "<<text.substr(i-m+1,m)<<endl;
            k=pai[k-1];
        }
    }
}