热乎乎的Google Onsite面经

硬币那个没明白

补充内容 (2015-4-7 22:26):
如果每个袋子里有无穷多个硬币，怎么会有一方拿完呢？

补充内容 (2015-4-7 22:26):
如果每个袋子里有无穷多个硬币，怎么会有一方拿完呢？

lz有没有问面试你的人都是什么组的呢？全是算法题，感觉像general hiring呀。。

第一题3D的heatmap就是一个三维的matrix？ 搜到的heatmap定义没太明白，求lz简单指导一下。多谢

applepie11 发表于 2015-4-7 11:56
硬币那个没明白

补充内容 (2015-4-7 22:26):

这种极限的情况应该不用考虑吧。google一下石子合并问题，这里就是把石子换成了金币。

celtspirit 发表于 2015-4-7 14:24
第一题3D的heatmap就是一个三维的matrix？ 搜到的heatmap定义没太明白，求lz简单指导一下。多谢

就是是2d矩阵。举个例子：
1 5 3 2
9 3 8 2
9 4 8 9
0 3 2 3
这就是一个4x4的heatmap，每个点的值代表了z轴，可以想象成一个个高矮不懂的小山峰。

coolis 发表于 2015-4-8 01:02
就是是2d矩阵。举个例子：
1 5 3 2
9 3 8 2

哦！明白了。多谢楼主指导！

请教楼主个问题, 请问google onsite new grad的话会被问到design题目吗? 还是纯算法题? 多谢

hotIce 发表于 2015-4-8 07:20
请教楼主个问题, 请问google onsite new grad的话会被问到design题目吗? 还是纯算法题? 多谢

我感觉被问到纯design的题目的概率非常小，一般都是design和coding结合的，除非你是面chrome os这样的team。
但是Google自家的bigtable，google file system和map reduce这样的一些system design还是要熟悉的。

coolis 发表于 2015-4-8 08:27
我感觉被问到纯design的题目的概率非常小，一般都是design和coding结合的，除非你是面chrome os这样的tea ...

好的 非常感谢!

问个很弱的问题。LZ的第一道题，我的思路和LZ基本一致，对给的每一个点BFS，然后最终扫描。写了一下code发现个问题：比如，对第一个点BFS的时候，要记录矩阵里的点是否visited，不必重复visit；然后对第二个点BFS，又需要重新记录一下visited，以此类推，每个点都需要记录一下visited，最终把所有的visited都统计起来，看哪个点highest。貌似很麻烦，有没有更简单的方法？（我写的code贴在下面，发现暴麻烦，汗啊，各位高手多多批评指教）
int highestpoint( vector<vector<int>> &vv, vector<vector<int>> &pts ){
        if(vv.empty() || vv[0].empty())
                return -1;
        vector<vector<int>> visited(vv.size()), visitall(vv.size());
        for(int i=0;i<visited.size();i++){
                vector<int> tmp(vv[0].size()); visited[i]=tmp; visitall[i]=tmp;
        }
        print_vv<T>(vv);
        for(int i=0;i<pts.size();i++){
                int pti=pts[i][0], ptj=pts[i][1];
                BFSpoints<T>(vv,visited,pti,ptj);
                for(int ii=0;ii<visited.size();ii++){
                        for(int jj=0;jj<visited[0].size();jj++){
                                visitall[ii][jj]+=visited[ii][jj]; visited[ii][jj]=0;
                        }
                }

        }
        int max=-1;
        for(int i=0;i<visitall.size();i++){
                for(int j=0;j<visitall[0].size();j++){
                        if(visitall[i][j]==pts.size()){
                                if(vv[i][j]>max)
                                        max=vv[i][j];
                        }
                }
        }
        //BFSpoints<T>(vv,visited,1,3);
        print_vv<T>(visitall);
        return max;
};


void BFSpoints(vector<vector<int>> &vv, vector<vector<int>> &visited,
        int pti, int ptj){
                if(pti>=vv.size() || ptj>=vv[0].size())
                        return;
                queue<vector<int>> qTmp;
                vector<int> vtmp; vtmp.push_back(pti); vtmp.push_back(ptj);
                qTmp.push(vtmp);
                while(!qTmp.empty()){
                        vector<int> tmp=qTmp.front(); qTmp.pop();
                        visited[tmp[0]][tmp[1]]=1;
                        // down
                        if( tmp[0]<vv.size() && tmp[0]+1<vv.size()
                        && vv[tmp[0]][tmp[1]]<vv[tmp[0]+1][tmp[1]]
                        && visited[tmp[0]+1][tmp[1]]!=1 ){
                                vector<int> vtmp; vtmp.push_back(tmp[0]+1); vtmp.push_back(tmp[1]);
                                qTmp.push(vtmp);
                        }
                        // up
                        if( tmp[0]<vv.size() && tmp[0]-1>=0
                        && vv[tmp[0]][tmp[1]]<vv[tmp[0]-1][tmp[1]]
                        && visited[tmp[0]-1][tmp[1]]!=1 ){
                                vector<int> vtmp; vtmp.push_back(tmp[0]-1); vtmp.push_back(tmp[1]);
                                qTmp.push(vtmp);
                        }
                        // left
                        if( tmp[1]>=0 && tmp[1]-1>=0
                        && vv[tmp[0]][tmp[1]]<vv[tmp[0]][tmp[1]-1]
                        && visited[tmp[0]][tmp[1]-1]!=1 ){
                                vector<int> vtmp; vtmp.push_back(tmp[0]); vtmp.push_back(tmp[1]-1);
                                qTmp.push(vtmp);
                        }
                        // right
                        if( tmp[1]<vv[0].size() && tmp[1]+1<vv[0].size()
                        && vv[tmp[0]][tmp[1]]<vv[tmp[0]][tmp[1]+1]
                        && visited[tmp[0]][tmp[1]+1]!=1 ){
                                vector<int> vtmp; vtmp.push_back(tmp[0]); vtmp.push_back(tmp[1]+1);
                                qTmp.push(vtmp);
                        }
                }
};