一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 4111|回复: 42
收起左侧

Google 据信 +面经

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

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

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

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

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

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

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

1,leetcode 上的longest consecutive sequence, 但是要求按顺序找-google 1point3acres
2,find the longest increasing sequence in an integer matrix in 4 directions (up down left right), return the sequence; for example: input:
1234      
.1point3acres缃8765,  output should be 12345678
这个题我用dfs+backtracking做的



补充内容 (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.. 鍥磋鎴戜滑@1point 3 acres
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++){. 1point 3acres 璁哄潧
for(j=0;j<N;j++){
if(temp[i][j] == 0){
fill(temp,i,j);. 1point 3acres 璁哄潧
}-google 1point3acres
}
}

here is fill() function.
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];

int left=0,right=0,up=0,down=0;
if(arr[i-1][j] = arr[i][j] +1)
up = fill(temp,i-1,j);. Waral 鍗氬鏈夋洿澶氭枃绔,
if(arr[i+1][j] = arr[i][j] +1)
down = fill(temp,i+1,j);.鏈枃鍘熷垱鑷1point3acres璁哄潧
if(arr[i][j-1] = arr[i][j-1] +1). 1point3acres.com/bbs
left = fill(temp,i,j-1);. from: 1point3acres.com/bbs
if(arr[i][j+1] = arr[i][j+1] +1)
right = fill(temp,i,j+1);
. 1point3acres.com/bbs
temp[i][j] = max(up,down,left,right) + 1;
return temp[i][j];
}

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++){. 1point 3acres 璁哄潧
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]);. Waral 鍗氬鏈夋洿澶氭枃绔,
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;
printf("%d ",temp[i][j]);.鐣欏璁哄潧-涓浜-涓夊垎鍦
continue;
}
if(temp[i][j-1] == temp[i][j] -1){
j = j-1;
printf("%d ",temp[i][j]);
continue;-google 1point3acres
}
if(temp[i][j+1] == temp[i][j] -1){
j = j+1;
printf("%d ",temp[i][j]);
-google 1point3acrescontinue;
}

}


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的顺序的?
{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)
.鐣欏璁哄潧-涓浜-涓夊垎鍦
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第二题印度小哥没让你做优化么,你写完了就完了?

. 1point3acres.com/bbs写完就没时间了,,,
第二题应该怎么做?
回复 支持 反对

使用道具 举报

 楼主| ptepte 发表于 2014-11-14 01:28:52 | 显示全部楼层
qiaokan 发表于 2014-11-13 23:31. 鍥磋鎴戜滑@1point 3 acres
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:

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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