《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2353|回复: 5
收起左侧

问一道面试题

[复制链接] |试试Instant~ |关注本帖
redolent 发表于 2014-10-14 03:53:25 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 实习@Facebook - 校园招聘会 - 技术电面 |Other

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

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

x
电面,只做了一道题,就是给了一张图,上面有一些形状大小不规则的黑色区域,剩下的地方为白色,要求输出一共有多少个黑色区域。
我知道应该是用flood fill 算法,可是不确定数目在什么时候update. 希望有人可以指点一下,有兴趣的可以写个伪代码。
Bless us all~
头像被屏蔽
hungryhuang 发表于 2014-10-17 05:17:03 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 1

使用道具 举报

tyr034 发表于 2014-10-14 04:23:50 | 显示全部楼层
有什么类似的题嘛?不太懂题目的意思
回复 支持 反对

使用道具 举报

kuyen 发表于 2014-10-14 07:12:26 | 显示全部楼层
tyr034 发表于 2014-10-14 04:23
有什么类似的题嘛?不太懂题目的意思

leetcode "Surrounded Regions" 可能类似
回复 支持 反对

使用道具 举报

迷彩的瓜皮帽 发表于 2014-10-14 08:40:43 | 显示全部楼层
这张图是以什么形式给的?matrix?还是需要自己分析
回复 支持 反对

使用道具 举报

eecsece 发表于 2014-10-14 09:10:32 | 显示全部楼层
这道题类似POJ的lake counting: http://poj.org/problem?id=2386. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
具体到楼主这道题:双层循环遍历图中每个点(假设图是m*n的矩阵),遇到黑点就开始DFS,过程中把遍历过得所有的黑点都改成白色的点,每次DFS就更新一次count。抛砖引玉写个伪代码:
时间复杂度是O(mn)
for(int i=0;i<m;i++){
     for(int j=0;j<n;j++){
            if(mat[j]是黑色){
                    DFS(i,j,mat);
                    count++;
            }
     }
}
DFS(int i, int j, matrix mat){
      mat改为白色;. Waral 鍗氬鏈夋洿澶氭枃绔,
      搜索所有方向,有黑色继续DFS(newi,newj,mat)
}
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-19 09:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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