Google第一轮面经

发信人: smilenceyu (smilence), 信区: JobHunting
标  题: Google第一轮面经
发信站: BBS 未名空间站 (Tue Oct  8 17:38:31 2013, 美东)

Phone interview，美国人，说话很清楚。不过太健谈了，导致他每次描述问题，说一
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。

不过人比较nice，希望好运吧。

1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）

然后让我实现一个function，看看能不能拼成一个message。

因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。

bool compose( string msg, string newspaper){
    unordered_map<char,int> ccnt;
    for(auto it = newspaper.begin(); it != newspaper.end(); it++)
        ccnt[ *it ]++;
    for(auto it = msg.begin(); it != msg.end(); it++){
if( ccnt.count(*it) == 0 || ccnt[ *it ] == 0)
return false;
else
    ccnt[ *it ]--;
     return true;
}   


2.他说他也是听说来的这道题，又是讨论描述了N久才搞明白，还跟我扯你知道为啥美
国分成这48个州么。。。比如给一个矩阵

1 2 2 3 (5)
3 2 3 (4) (4)
2 4 (5) 3 1              Atlantic
(6) (7) 1 4 5
(5) 1 1 2 4

每个数字代表该地区的海拔，然后西边是太平洋，东边是大西洋，让我返回所有path，
每个path能连通大西洋和太平洋，水只能从高处往低处走。

我到最后才发现他这个例子好像有点不对（他说他也不是很清楚，别人给他的。。汗）
，我觉得真正的意思应该是水流是单向的，否则岂不是随便怎么走都能连通？？

我就用backtracking的方法，有点类似boggle game那题，从西海岸的点出发，往8个方
向走，如果没超出边界或者没用过，就走下去，直到到达东海岸，把这个路径存下来。

电面结束我才发现我有个bug，就是说，到达东海岸的时候不应该return，因为还可以
沿东海岸往下走。一开始没写这个return，后来手贱加上去，悔啊。。。

如果题目意思我没理解错的话，我感觉我做法是对的。面试官说他理解了，但是他没做
过，不知道对不对，回去跟人讨论讨论。。。。。


class point{
public:
    int row;
    int col;
}

bool isValid( int row, int col, bool used[HEIGHT][WIDTH] ){
    if( row > HEIGHT || col > WIDTH || row < 0 || col < 0 )
        return false;
    if( used[row][col] )
        return false;
    return true;
}

   
void flow( int row, int col, vector<point> &path, vector< list<point> > &
paths, int mat[ HEIGHT] [ WIDTH ], bool used[HEIGHT][WIDTH]     ){
    int value = mat[row][col];
    used[row][col] = true;
    point p;
    p.row = row;
    p.col = col;
    path.push_back( p );
    if( col == WIDTH - 1 ){
        list<point> tmp(path.begin(), path.end());
        paths.push_back(tmp);
        //return;这里不应该return
    }
    if( isValid( row - 1, col , used ) &&  mat[row - 1][col] <= value )
flow( row -1,col,path,paths,mat,used );
if( isValid( row - 1, col - 1 , used ) &&  mat[row - 1][col -1 ] <= value )
    flow( row -1,col - 1,path,paths,mat,used );
if( isValid( row , col - 1 , used ) &&  mat[row ][col -1 ] <= value )
        flow( row,col - 1,path,paths,mat,used );
if( isValid( row + 1, col - 1 , used ) &&  mat[row + 1 ][col -1 ] <= value )
        flow( row + 1,col - 1,path,paths,mat,used );
if( isValid( row + 1, col  , used ) &&  mat[row + 1 ][col  ] <= value )
        flow( row + 1,col ,path,paths,mat,used );
if( isValid( row + 1, col + 1  , used ) &&  mat[row + 1 ][col + 1  ] <=
value )
        flow( row + 1,col + 1,path,paths,mat,used );
if( isValid( row + 1, col - 1  , used ) &&  mat[row + 1 ][col - 1  ] <=
value )
        flow( row + 1,col - 1,path,paths,mat,used );
if( isValid( row , col + 1  , used ) &&  mat[row  ][col + 1  ] <= value )
        flow( row ,col + 1,path,paths,mat,used );
    path.pop_back();
    used[row][col] = false;
}

vector< list<point> > calPaths( int mat[HEIGHT][WIDTH] ){
    vector<point> path;
vector< list<point> > paths;
bool used[HEIGHT][WIDTH] ;
for( int i = 0; i < HEIGHT; i++){
    for( int j = 0; j < WIDTH; j++){
        used[i][j] = false;
    }
    }
for( int i = 0; i < HIEGHT;i++){
    flow( i, 0, path, paths, mat, used );
}
return paths;
}




--

※ 修改:·smilenceyu 於 Oct  8 17:50:35 2013 修改本文·[FROM: 71.]
※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 71.]

http://www.mitbbs.com/article_t/JobHunting/32549767.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东十一长假图书满100立减20元 ， 更多京东优惠券