Google第一轮面经# JobHunting - 待字闺中
s*u
1 楼
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 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 &path, vector< list > &
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 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 > calPaths( int mat[HEIGHT][WIDTH] ){
vector path;
vector< list > 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;
}
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。
不过人比较nice，希望好运吧。
1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）
然后让我实现一个function，看看能不能拼成一个message。
因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。
bool compose( string msg, string newspaper){
unordered_map
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
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
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
vector
vector< list
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;
}
