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;
}