推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 7142|回复: 42
收起左侧

Google 据信 +面经

[复制链接] |试试Instant~ |关注本帖
ptepte 发表于 2014-11-13 15:09:20 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Fail

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
上周g电话面试,这周就被拒了,直接说


Our hiring team has decided not to move forward with your candidacy for the Applications Engineer, University Graduate role. Please note that your resume will stay on file and we may contact you if we come across another opening for which you may be qualified.. From 1point 3acres bbs


这是模版据信么? 我还能再申请其他职位么? 还是说我半年之内不能再申请了因为被他们keep on file了?   有小伙伴遇到过这种情况的么?

附上面经,面试官是个三哥,2个题,都不难
-google 1point3acres
1,leetcode 上的longest consecutive sequence, 但是要求按顺序找
2,find the longest increasing sequence in an integer matrix in 4 directions (up down left right), return the sequence; for example: input:. 1point 3acres 璁哄潧
1234      
8765,  output should be 12345678
这个题我用dfs+backtracking做的

. from: 1point3acres.com/bbs

补充内容 (2014-11-14 00:40):
1, 就是按照给定数组的顺序, A[]=5,6,10,11,15,1,2,3  output=3, 也就是 1,2,3;

评分

2

查看全部评分

wondermu 发表于 2014-11-14 03:00:28 | 显示全部楼层
此题应该用dp的memoization,

here are the steps:
1. create a new 2d array (let say named temp[][]) of same dimension as original. the element temp[i][j] contains the length of the LIS starting at this point.
. visit 1point3acres.com for more.2. first fill this temp array with 0's.
3. now, start filling this temp array. let say given array's dimension is MxN.

int arr[M][N]; // given array.. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
int temp[M][N];

for (i=0;i<M;i++){
for(j=0;j<N;j++){. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
if(temp[i][j] == 0){
fill(temp,i,j);
}
}
}

here is fill() function.
int fill(int temp[][], int i, int j){
if(i<0 || j< 0 || i>=M || j>=N)
return 0;. visit 1point3acres.com for more.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
if(temp[i][j] != 0). Waral 鍗氬鏈夋洿澶氭枃绔,
return temp[i][j];.1point3acres缃

int left=0,right=0,up=0,down=0;
if(arr[i-1][j] = arr[i][j] +1)
up = fill(temp,i-1,j);
if(arr[i+1][j] = arr[i][j] +1)
down = fill(temp,i+1,j);
if(arr[i][j-1] = arr[i][j-1] +1)
left = fill(temp,i,j-1);
if(arr[i][j+1] = arr[i][j+1] +1)
right = fill(temp,i,j+1);

temp[i][j] = max(up,down,left,right) + 1;
return temp[i][j];
}

thus it will calculate each element of temp array only once.. Waral 鍗氬鏈夋洿澶氭枃绔,

4. now, find the maximum element in the array. it's value will be the length of LIS. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
max_x=0,max_y=0;. visit 1point3acres.com for more.
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] > temp[max_x][max_y]){
max_x = i;
max_y = j;
} 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}
}

5. Above will give the length of LIS. now, to find the LIS, we will check it's neighbours whose LIS value difference is 1.

i=max_x, j= max_y ;
printf("%d ",temp[i][j]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
while(temp[i][j] != 1){
if(temp[i-1][j] == temp[i][j] -1){. visit 1point3acres.com for more.
i = i-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i+1][j] == temp[i][j] -1){
i = i+1;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j-1] == temp[i][j] -1){
j = j-1;
printf("%d ",temp[i][j]);. Waral 鍗氬鏈夋洿澶氭枃绔,
continue;. 1point 3acres 璁哄潧
}
if(temp[i][j+1] == temp[i][j] -1){
j = j+1;
printf("%d ",temp[i][j]);
continue;
}. from: 1point3acres.com/bbs

}


time complexity is: O(M.N)
回复 支持 4 反对 0

使用道具 举报

wksora 发表于 2014-11-13 15:41:53 | 显示全部楼层
真奇怪,楼主感觉为什么会被拒?
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2014-11-13 16:42:19 | 显示全部楼层
pat pat楼主,第二题思路可以再详细一些么?如果是每个点都dfs的话消耗有点大啊,求指导。
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2014-11-13 16:45:03 | 显示全部楼层
没事了,我太傻比。。。
回复 支持 反对

使用道具 举报

Dexter_syr 发表于 2014-11-13 21:01:53 | 显示全部楼层
应该是据了,不过半年以后还可以投。Lz move on吧,半年再去投一次。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
还有, 请教lz, 第一题的"要求按顺序找"是啥意思啊?
. 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

yabay91 发表于 2014-11-13 21:36:36 | 显示全部楼层
lz这个是多长时间的面试啊。。。我收到了一个goole的说是15~20分钟的电面。。不知道他要问啥
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-13 21:55:59 | 显示全部楼层
第二题可以dp下
回复 支持 反对

使用道具 举报

sjtuzyt 发表于 2014-11-13 22:51:18 | 显示全部楼层
楼主第一题的意思是consecutive sequence必须是increasing的顺序的?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴{100,1,2,6,3,4,5} 那么最长是5?
回复 支持 反对

使用道具 举报

sailorconan 发表于 2014-11-13 23:27:39 | 显示全部楼层

要是两个方向还好,4个方向的dp?能写个递推公式吗?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-13 23:31:36 | 显示全部楼层
bool f[k][i][j] is true if after k steps, we can end up at cell (i,j)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
k is at most n^2
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-13 23:31:52 | 显示全部楼层
sailorconan 发表于 2014-11-13 23:27
.鏈枃鍘熷垱鑷1point3acres璁哄潧要是两个方向还好,4个方向的dp?能写个递推公式吗?


bool f[k][j] is true if after k steps, we can end up at cell (i,j). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

k is at most n^2
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-11-14 01:24:45 | 显示全部楼层
lz第二题印度小哥没让你做优化么,你写完了就完了?
回复 支持 反对

使用道具 举报

byrlhb 发表于 2014-11-14 01:24:53 | 显示全部楼层
lz第二题印度小哥没让你做优化么,你写完了就完了?
回复 支持 反对

使用道具 举报

 楼主| ptepte 发表于 2014-11-14 01:27:54 | 显示全部楼层
byrlhb 发表于 2014-11-14 01:24
lz第二题印度小哥没让你做优化么,你写完了就完了?

写完就没时间了,,,
第二题应该怎么做?
回复 支持 反对

使用道具 举报

 楼主| ptepte 发表于 2014-11-14 01:28:52 | 显示全部楼层
qiaokan 发表于 2014-11-13 23:31-google 1point3acres
bool f[k][j] is true if after k steps, we can end up at cell (i,j)

k is at most n^2

递推公式是?
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-11-14 02:45:57 | 显示全部楼层
我怎么觉得第二题和第一题是一样的。。无非加了两个方向。。
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-11-14 03:00:27 | 显示全部楼层
第二题用bfs 计算最长路径。。。 这样想比dp简单好多,就是不是那么efficient。。
回复 支持 反对

使用道具 举报

adiggo 发表于 2014-11-14 03:08:43 | 显示全部楼层
wondermu 发表于 2014-11-14 03:00
此题应该用dp的memoization,

here are the steps:

搜了一下, 这个的确算最佳解法 了。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-8-18 13:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表