一亩三分地论坛

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

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

FB电面

[复制链接] |试试Instant~ |关注本帖
dojiangv 发表于 2016-5-1 03:08:13 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 博士 全职@Facebook - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
一个char[][] board,里面有‘b’'B''w''W'四种,bB都表示black,wW都表示white,找最大的正方形面积,这个正方形四个边都是black,正方形中间随便黑白无所谓。Example:一个5x5的board如下,符合条件最大正方形是个3x3的,return面积9。
wwbww
wbbbb
bbWbw
Bbbbb
wwwww

评分

3

查看全部评分

ericLaw 发表于 2016-5-2 09:13:08 | 显示全部楼层
还是用dp做,就是max square的一个变形
回复 支持 2 反对 0

使用道具 举报

 楼主| dojiangv 发表于 2016-5-1 12:08:06 | 显示全部楼层
edcent 发表于 2016-5-1 04:18. From 1point 3acres bbs
楼主怎么做的呢?

记忆化搜索,记录每一个点的往左黑线长度和往上黑线长度。
回复 支持 2 反对 0

使用道具 举报

edcent 发表于 2016-5-1 04:18:49 | 显示全部楼层
楼主怎么做的呢?
回复 支持 反对

使用道具 举报

malc 发表于 2016-5-1 04:36:18 | 显示全部楼层
DFS,以某点为起点顺时针沿边线搜索?
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-5-1 13:02:34 | 显示全部楼层
这解法的复杂度是多少?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-5-2 11:21:42 | 显示全部楼层
ericLaw 发表于 2016-5-2 09:13
还是用dp做,就是max square的一个变形

请问dp具体做法怎么做?
回复 支持 反对

使用道具 举报

 楼主| dojiangv 发表于 2016-5-2 14:53:19 | 显示全部楼层
mingzhou1987 发表于 2016-5-1 13:02
这解法的复杂度是多少?

O(n)吧,worst case O(n2)
回复 支持 反对

使用道具 举报

smallpig1988 发表于 2016-5-3 02:09:27 | 显示全部楼层
应该就是这道题吧?
http://www.geeksforgeeks.org/given-matrix-o-x-find-largest-subsquare-surrounded-x/
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-5 13:57:40 | 显示全部楼层
dojiangv 发表于 2016-5-2 14:53
O(n)吧,worst case O(n2)

请教楼主 为什么我想是
O(n^3)?(如果变长是n)

建立helper matrix需要O(n^2)-google 1point3acres

然后遍历每个cell需要O(n^2),对每个cell寻找他的向上或向左的黑边里,哪个可以组成正方形
因为有可能:

wbb
bwb
bbb

这样右下角的点的正方形就不是3

我是不是哪里没优化
回复 支持 反对

使用道具 举报

三吉 发表于 2016-5-6 00:12:49 | 显示全部楼层
tcomein2009 发表于 2016-5-5 13:57
请教楼主 为什么我想是
O(n^3)?(如果变长是n)

同问,我也觉得是O(n^3)...而且naive的做法好像也不是很费时

. from: 1point3acres.com/bbs 1. naive: 对于每个square,check边框是不是w。
                        time: O(n^2 * 4n) = O(n^3)
                        space: O(1)
2. dp: 用两个矩阵记录每个点左边和上边的边框长度
                        time: O(3 * n^2 * n) = O(n^3)
                        space: O(2 * n^2) = O(n^2)
. visit 1point3acres.com for more.
两种方法好像没差多少的,而且第二个还用了不少space。。不知道分析得对不对=。=
回复 支持 反对

使用道具 举报

 楼主| dojiangv 发表于 2016-5-6 00:21:54 | 显示全部楼层
tcomein2009 发表于 2016-5-5 13:57
请教楼主 为什么我想是
O(n^3)?(如果变长是n)

我这里的n指整个board的元素,如果按你的算法,就是n2
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-6 07:52:57 | 显示全部楼层
三吉 发表于 2016-5-6 00:12
同问,我也觉得是O(n^3)...而且naive的做法好像也不是很费时

1. naive: 对于每个square,check边框是 ...

你这个分析dp的worst case是O(n^3),但是考虑到还有很多剪枝情况,比如可能的值比当前发现的最大值小,或者一下子就找到了比当前值大的值,不用把左和上都遍历一遍,所以平均下来的时间应该是优于O(n^3) n是matrix的边长。不过其实他没有说matrix是一个正方形,我觉得平均时间应该是O(mm)+O(mm)*O(m+n) 其中m和n是matrix的
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-6 07:55:08 | 显示全部楼层
ericLaw 发表于 2016-5-6 07:52. more info on 1point3acres.com
你这个分析dp的worst case是O(n^3),但是考虑到还有很多剪枝情况,比如可能的值比当前发现的最大值小,或 ...

手机打字不好打,应该是O(mn) + O(mn)*O(m+n)
回复 支持 反对

使用道具 举报

 楼主| dojiangv 发表于 2016-5-6 08:50:28 | 显示全部楼层
ericLaw 发表于 2016-5-6 07:55-google 1point3acres
手机打字不好打,应该是O(mn) + O(mn)*O(m+n)

你这比O(n^3)都大了
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-6 09:00:45 | 显示全部楼层
dojiangv 发表于 2016-5-6 08:50
你这比O(n^3)都大了

后面那个O(m+n)应该是O(min(m,n))
回复 支持 反对

使用道具 举报

 楼主| dojiangv 发表于 2016-5-6 14:21:17 | 显示全部楼层
ericLaw 发表于 2016-5-6 07:55
手机打字不好打,应该是O(mn) + O(mn)*O(m+n)

能解释一下两个O(mn)分别是什么吗?我觉得O(mn)*O(min(m+n))就差不多了,这题设定input是个square,所以worse case O(n^3)。
回复 支持 反对

使用道具 举报

 楼主| dojiangv 发表于 2016-5-6 14:23:16 | 显示全部楼层
dojiangv 发表于 2016-5-6 14:21. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
能解释一下两个O(mn)分别是什么吗?我觉得O(mn)*O(min(m+n))就差不多了,这题设定input是个square,所以w ...

打错了,O(mn)*O(min(m,n))
回复 支持 反对

使用道具 举报

ericLaw 发表于 2016-5-6 17:16:51 | 显示全部楼层
dojiangv 发表于 2016-5-6 14:23. 鍥磋鎴戜滑@1point 3 acres
打错了,O(mn)*O(min(m,n))

你是对的。第一个只是想说明一下初始化dp矩阵要消耗的时间。其实严格来说应该去掉。我后来仔细想了一下最坏情况和平均情况big O应该是一样的。如果是给一个正方形就应该是O(n^3)。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-5-7 10:43:03 | 显示全部楼层
ericLaw 发表于 2016-5-2 09:13
还是用dp做,就是max square的一个变形

同意。。 其实就是max square。。 无非判断1,0 变成 b,w
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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