San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 7646|回复: 42
收起左侧

Google 据信 +面经

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

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

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

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

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.. 1point3acres

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

附上面经,面试官是个三哥,2个题,都不难

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. 牛人云集,一亩三分地
这个题我用dfs+backtracking做的
. 1point3acres


补充内容 (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.
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++){-google 1point3acres
if(temp[i][j] == 0){
fill(temp,i,j);. from: 1point3acres
}
}
}

here is fill() function.
int fill(int temp[][], int i, int j){
来源一亩.三分地论坛. if(i<0 || j< 0 || i>=M || j>=N)
.1point3acres网return 0;

if(temp[i][j] != 0)
return temp[i][j];

int left=0,right=0,up=0,down=0;. 牛人云集,一亩三分地
if(arr[i-1][j] = arr[i][j] +1)-google 1point3acres
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).1point3acres网
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.. 1point3acres

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
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]);. visit 1point3acres for more.
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;. more info on 1point3acres
printf("%d ",temp[i][j]);
continue;
}
if(temp[i][j-1] == temp[i][j] -1){
j = j-1;
printf("%d ",temp[i][j]);. 1point3acres
continue;. 1point 3acres 论坛
}
if(temp[i][j+1] == temp[i][j] -1){
j = j+1;
printf("%d ",temp[i][j]);
continue;
}

}

.本文原创自1point3acres论坛
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吧,半年再去投一次。
. from: 1point3acres
还有, 请教lz, 第一题的"要求按顺序找"是啥意思啊?

回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

sjtuzyt 发表于 2014-11-13 22:51:18 | 显示全部楼层
楼主第一题的意思是consecutive sequence必须是increasing的顺序的?.本文原创自1point3acres论坛
{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)
. Waral 博客有更多文章,
k is at most n^2
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-11-13 23:31:52 | 显示全部楼层
sailorconan 发表于 2014-11-13 23:27.留学论坛-一亩-三分地
要是两个方向还好,4个方向的dp?能写个递推公式吗?

. visit 1point3acres for more.
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)
. visit 1point3acres for more.
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:

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-26 20:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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