一亩三分地论坛

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

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

Google电面

[复制链接] |试试Instant~ |关注本帖
analog123 发表于 2015-5-5 07:01:01 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other在职跳槽

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

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

x
题目: Given a rectangular grid of colored pixels and a particular pixel in the grid, find the perimeter of the same-colored blob containing that pixel.

                               
登录/注册后可看大图
               

                               
登录/注册后可看大图



                               
登录/注册后可看大图
               
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                               
登录/注册后可看大图
.1point3acres缃
口音不重的三姐面的,第一眼看到google doc里贴出来这几张图片以为是复杂的几何题差点吓尿。。不过听完解释就是简单的DFS。。要注意的点是第四个图例是个空图,所以假设存在Color.EMPTY,就要在DFS之前先判断下。做之前因为细节都很模糊,问了不少问题,最后45分钟就做了这一道题。。感觉很虚。。
. 1point3acres.com/bbs



补充内容 (2015-5-7 10:18):
补充一下,因为是求包含所给像素的图形的周长,所以就是DFS到每个相同颜色的邻接像素,然后检查这个像素周围四个像素的颜色,如果颜色不同或者越界了,周长+1,否则就继续DFS到那个像素。最后得到周长

评分

1

查看全部评分

hami33 发表于 2015-5-5 12:36:33 | 显示全部楼层
感谢楼主分享! 祝好运!

能再解释一下这道题到底什么意思吗? 输入是给的什么?
回复 支持 反对

使用道具 举报

hami33 发表于 2015-5-5 15:09:00 | 显示全部楼层
我写出来了,多谢楼主分享!
回复 支持 反对

使用道具 举报

magicalcan 发表于 2015-5-6 15:46:06 | 显示全部楼层
这题周长是指多少格子吗,比如第三个的周长怎么定义
回复 支持 反对

使用道具 举报

hami33 发表于 2015-5-7 09:00:55 | 显示全部楼层
magicalcan 发表于 2015-5-6 15:46
这题周长是指多少格子吗,比如第三个的周长怎么定义

只求连续的格子,所以就是那几个连续的周长就好
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-1 08:00:37 | 显示全部楼层
包含的形状一定要rectangle? 不规则形状怎么算周长?
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-6-1 23:36:24 | 显示全部楼层
看不到图。。。怎么办
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-6-2 00:01:04 | 显示全部楼层
是和 leetcode 里面的 Maximal Rectangle  很像么
回复 支持 反对

使用道具 举报

dmsehuang 发表于 2015-6-2 03:00:11 | 显示全部楼层
的确看不到图啊。这个周长的定义很模糊啊。
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-10 03:11:26 | 显示全部楼层
周长的定义很模糊 could you explain more?
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-6-29 07:55:46 | 显示全部楼层
hami33 发表于 2015-5-7 09:00
只求连续的格子,所以就是那几个连续的周长就好

麻烦你能不能解释一下题目的意思呢,不是很明白。。。。
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-6-29 07:56:16 | 显示全部楼层
麻烦楼主能不能再说一下题目的大概意思。。不是很明白,怎么找到相同像素的周长?
回复 支持 反对

使用道具 举报

 楼主| analog123 发表于 2015-6-29 09:36:59 | 显示全部楼层
UmassJin 发表于 2015-6-28 18:56
麻烦楼主能不能再说一下题目的大概意思。。不是很明白,怎么找到相同像素的周长?

说是像素其实就是一个一个边长为1的正方形小格子,每个格子有一个颜色,所以就是从给定格子出发做DFS,直到抵达一个在边缘的格子(也就是说这个格子周围四个方向有一个方向颜色不同或者越界),有几个边满足条件就加几
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-6-29 12:56:14 | 显示全部楼层
analog123 发表于 2015-6-29 09:36. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
说是像素其实就是一个一个边长为1的正方形小格子,每个格子有一个颜色,所以就是从给定格子出发做DFS,直 ...

谢谢楼主,明白啦!
回复 支持 反对

使用道具 举报

jsqihui 发表于 2015-7-9 10:21:36 | 显示全部楼层
明白了,最后直到有一个格子的边不为同样的颜色,或者多个格子的边不为同样的颜色,有几个边就加几,因为这就是周长的一部分了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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