一亩三分地论坛

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

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

Google 面试题求解

[复制链接] |试试Instant~ |关注本帖
yanyanleeeee 发表于 2015-10-20 16:47:14 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 本科 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
Google 面完onsit挺久了。现在才来写。 因为接到通知,要继续面。简单的题我真心不记得了
记得的分享一下
1. 给一个N*N grid, 上面有一些格子里面标了1. 问总共多少方块了有1. 所以方块包括只含1的那个, 还有任何含1的那个 所以2*2, 3*3。 当时,被问懵了,而且是那一轮的第二小题,所以没时间了。后来面试官一直说
don't forget you have a computer blah blah, 越给我hint我越panic不知道怎么做。
2. 给你一堆灯泡。可以flip 一个范围开着变关, 关变开, 然后问这么干了k次以后, 随便问你一个灯泡是开着开始关着,怎么做。我还是很弱地没写完。 但是有很多idea。主要想就是interval, merge interval 之类. more info on 1point3acres.com
求大家指点这两个题该怎么做最好。 而且,想问大家每次runtime问了都怎么回答的啊。 我每次都想当然,很容易答错。 求大家多多指教!





评分

1

查看全部评分

本帖被以下淘专辑推荐:

 楼主| yanyanleeeee 发表于 2015-10-24 11:47:46 | 显示全部楼层
就像edly 所说。
所以主要的思考方法是, 我们看每一个点, 数一下以这个点为最右下的方块的个数. visit 1point3acres.com for more.
然后看每个点, 如果是1,  以这个点为最右下角的正方形应该有 min(x+1, y+1)个。  (x, y) 为index. Waral 鍗氬鏈夋洿澶氭枃绔,
比如
0 0
0 1
(1,1)那个点 就有 两个方块, 它自己和包括它的那个2*2。 因为自己肯定是1, 所以每个方块里保证有1 了,
如果是0, 那么就要看应该少数几块, 我们需要维护一个matrix 那个matrix里面记录 和这个点最近的1 的距离。
int withzero =  Math.min(radius[i-1][j], Math.min(radius[i-1][j-1], radius[j][1])) + 1;. From 1point 3acres bbs
比如
0 0 0
0 1 0
0 0 0
那么我们发现(2,2)最短距离 为它左上的 0(每次我们读1, 往matrix里面放0, 表示1和1 的距离为0)
然后我们+1 因为自己是0
然后count 就是min(x+1, y+1) - withzero

一边数的时候一边加一加每个点的count 就得到答案了!
回复 支持 2 反对 0

使用道具 举报

 楼主| yanyanleeeee 发表于 2015-10-21 00:35:27 | 显示全部楼层
我是楼主, 题目没说清楚。 我来一幅图吧。  https://drive.google.com/file/d/0B_1YGf8GUUU0Njd3Q2M4V0lJMGc/view?usp=sharing

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

edly 发表于 2015-10-20 17:14:33 | 显示全部楼层
1.
先维护r[x][y]表示(x,y)右边第一个1的y坐标,d[x][y]表示(x,y)下面第一个1的坐标,递推r[x][y]<-r[x][y + 1], d[x][y]<-d[x + 1][y]. visit 1point3acres.com for more.
然后可以算f[x][y]->(左上角为(x,y)的方块,最大不包含1的边长是多少),有了f 最后答案就很好算了,f[x][y]可由f[x + 1][y + 1],r[x][y],d[x][y] O(1)算
O(n^2)
. 1point3acres.com/bbs
2.
假设询问有q个,灯泡有n个
对于一次flip(l,r),在l和r+1两点取反,即flag[l] = flag[l] xor 1, flag[r + 1] = flag[r + 1] xor 1,灯泡i 最后的状态就是把j<=i的flag[j]xor起来. From 1point 3acres bbs
如果全部flip完后才询问,可以直接按上述方法做完后算好每个灯的状态直接保存下来,询问直接输出. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
O(n+k+q)
如果一边flip一边有询问,那么可用Binary Index Tree将flip和query都做成O(logn),或者直接用Segment Tree或BST等数据结构维护区间修改
O(n+(k+q)logn)

把做法吃透了runtime自然而然就知道了

评分

2

查看全部评分

回复 支持 1 反对 0

使用道具 举报

edly 发表于 2015-10-21 20:17:37 | 显示全部楼层
javaprogrammer 发表于 2015-10-21 16:24
大牛能不能详细说下第一题的解法,还是没看懂

可以用一个三元组表示一个正方形(x,y,k),表示左上角坐标为(x,y),边长为k的正方形
对于每个(x,y)显然存在一个z,当k<=z时,(x,y,k)不包含1,当k>z时,(x,y,k)包含1
当知道每个(x,y)的z后,答案就很显然了. visit 1point3acres.com for more.

我们定义f[x][y]=z of (x,y),f[x][y]的取值可由f[x+1][y+1],(x,y)向下第一个1的位置,(x,y)向右第一个1的位置O(1)确定
回复 支持 1 反对 0

使用道具 举报

Wizmann 发表于 2015-10-20 17:45:09 | 显示全部楼层
第一题类似于Largest sum of a Matrix
第二题只存端点即可。每次查询是log(Q)的。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

will_ym 发表于 2015-10-20 21:32:40 | 显示全部楼层
edly 发表于 2015-10-20 17:14
1.
先维护r[x][y]表示(x,y)右边第一个1的y坐标,d[x][y]表示(x,y)下面第一个1的坐标,递推r[x][y]

大神 我以前一直用n cube 做得 学习了 不过r应该是邮编第一个0的坐标吧 这样r[x][y]就代表了最长1的个数 d同理
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-10-20 22:44:53 | 显示全部楼层
真心看不懂第一题什么意思  ‘总共方块了有1....’ 是什么意思? 这题是说求有多少个由1组成的正方形?
回复 支持 反对

使用道具 举报

 楼主| yanyanleeeee 发表于 2015-10-21 00:37:09 | 显示全部楼层
edly 发表于 2015-10-20 17:14
1.
先维护r[x][y]表示(x,y)右边第一个1的y坐标,d[x][y]表示(x,y)下面第一个1的坐标,递推r[x][y]

谢谢你的回答。 但我第一题没怎么看懂 。 这里有个图, 所以我们最后是怎么数的呢。. from: 1point3acres.com/bbs
图片

补充内容 (2015-10-21 00:37):. more info on 1point3acres.com
https://drive.google.com/file/d/0B_1YGf8GUUU0Njd3Q2M4V0lJMGc/view?usp=sharing
回复 支持 反对

使用道具 举报

 楼主| yanyanleeeee 发表于 2015-10-21 00:37:36 | 显示全部楼层
yanyanleeeee 发表于 2015-10-21 00:37
谢谢你的回答。 但我第一题没怎么看懂 。 这里有个图, 所以我们最后是怎么数的呢。
图片

https://drive.google.com/file/d/0B_1YGf8GUUU0Njd3Q2M4V0lJMGc/view?usp=sharing
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-10-21 16:24:54 | 显示全部楼层
edly 发表于 2015-10-20 17:14
1.. from: 1point3acres.com/bbs
先维护r[x][y]表示(x,y)右边第一个1的y坐标,d[x][y]表示(x,y)下面第一个1的坐标,递推r[x][y]

大牛能不能详细说下第一题的解法,还是没看懂
回复 支持 反对

使用道具 举报

mingmingya 发表于 2015-10-21 19:51:55 来自手机 | 显示全部楼层
还是不懂啥意思
回复 支持 反对

使用道具 举报

goo 发表于 2015-10-21 21:10:41 | 显示全部楼层
edly 发表于 2015-10-21 20:17. 1point 3acres 璁哄潧
可以用一个三元组表示一个正方形(x,y,k),表示左上角坐标为(x,y),边长为k的正方形
对于每个(x,y)显然存 ...

可不可以先求只包含0的正方形数x  用总的正方形-x  编码简单 O(n)就可以了
回复 支持 反对

使用道具 举报

javaprogrammer 发表于 2015-10-22 13:14:41 | 显示全部楼层
edly 发表于 2015-10-21 20:17
可以用一个三元组表示一个正方形(x,y,k),表示左上角坐标为(x,y),边长为k的正方形
对于每个(x,y)显然存 ...

像这样的matrix
0000
0010
0100
0000

维护的2-d array r 和 d 是下面这样吗?我不明白为什么要找到每个点右面和下面第一个1的位置,那如果那个点本身就是1,怎么办呢?
r[x][y]
0000
2220
1100
0000. more info on 1point3acres.com
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
d[x][y]
0210
0210
0200
0000

这样好像没什么意义啊. 1point 3acres 璁哄潧

回复 支持 反对

使用道具 举报

 楼主| yanyanleeeee 发表于 2015-10-24 08:50:47 | 显示全部楼层
我也还是没看懂
回复 支持 反对

使用道具 举报

 楼主| yanyanleeeee 发表于 2015-10-24 09:10:59 | 显示全部楼层
我懂了, 我会待会 把我写的solution 传上来
回复 支持 反对

使用道具 举报

calalia 发表于 2015-10-24 12:01:53 | 显示全部楼层
第一个题让我想起 画直方图(largest rectangle in histogram)的那个 不知道我感觉对不对 用stack ~那个题要largest,这个是要输出所有的 所以就要存起来。不知道有木有理解对题意。我认为是 所有1组成的方块~复杂度O(n) ~ http://www.cnblogs.com/lichen782 ... e_in_Histogram.html
回复 支持 反对

使用道具 举报

arjiang 发表于 2015-10-25 02:46:11 | 显示全部楼层
yanyanleeeee 发表于 2015-10-24 11:47
就像edly 所说。
所以主要的思考方法是, 我们看每一个点, 数一下以这个点为最右下的方块的个数
然后看 ...

厉害,这个方法不错。
回复 支持 反对

使用道具 举报

Qiangdong16 发表于 2016-2-3 14:27:40 | 显示全部楼层
楼主的第一题,2X2的我怎么数出来是7个?总数是14个?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 13:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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