传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 7219|回复: 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.
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

附上面经,面试官是个三哥,2个题,都不难.鏈枃鍘熷垱鑷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:
1234      
8765,  output should be 12345678. from: 1point3acres.com/bbs
这个题我用dfs+backtracking做的.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 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:. from: 1point3acres.com/bbs
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.
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){. Waral 鍗氬鏈夋洿澶氭枃绔,
fill(temp,i,j);
}
}.鏈枃鍘熷垱鑷1point3acres璁哄潧
}

here is fill() function.. From 1point 3acres bbs
int fill(int temp[][], int i, int j){
if(i<0 || j< 0 || i>=M || j>=N)
return 0;

if(temp[i][j] != 0)
return temp[i][j];
-google 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);-google 1point3acres
if(arr[i][j-1] = arr[i][j-1] +1)
left = fill(temp,i,j-1);. 1point3acres.com/bbs
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];. 鍥磋鎴戜滑@1point 3 acres
}. from: 1point3acres.com/bbs
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
thus it will calculate each element of temp array only once.

4. now, find the maximum element in the array. it's value will be the length of LIS.
max_x=0,max_y=0;
for(i=0;i<M;i++){
for(j=0;j<N;j++){
if(temp[i][j] > temp[max_x][max_y]){
max_x = i;. more info on 1point3acres.com
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){
i = i-1;
printf("%d ",temp[i][j]);
continue;
}
if(temp[i+1][j] == temp[i][j] -1){
i = i+1;. From 1point 3acres bbs
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j-1] == temp[i][j] -1){
j = j-1;. from: 1point3acres.com/bbs
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j+1] == temp[i][j] -1){
j = j+1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
printf("%d ",temp[i][j]);
continue;
}. 鍥磋鎴戜滑@1point 3 acres
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
}


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, 第一题的"要求按顺序找"是啥意思啊?

回复 支持 反对

使用道具 举报

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的顺序的?. From 1point 3acres bbs
{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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
要是两个方向还好,4个方向的dp?能写个递推公式吗?


bool f[k][j] is true if after k steps, we can end up at cell (i,j).1point3acres缃

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
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-9-25 10:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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