一亩三分地

 找回密码 注册账号

扫描二维码登录本站


Salarytics=Salary Analytics
查询工资数据
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
把贵司信息放这里
查看: 3838|回复: 16
收起左侧

狗家onsite一道特别的题

[复制链接] |试试Instant~ |美国面经, 码农类general, 面试经验, google
我的人缘0

分享帖子到朋友圈
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (15)
 
 
0% (0)    👎

2016(10-12月) 码农类General 硕士 全职@Google - 内推 - Onsite  | Other | 在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
题目:M乘以N的二维由1乘1的小方形构成的矩形,可以分解成最少多少个SQAURE。。。

现场给出了一个递归解法,就是无限由长边分解短边,但是自己发现有点bug准备改,可是面试官说没问题这
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
复杂。。。


分享给版上的朋友们。。。

评分

参与人数 1大米 +3 收起 理由
mmliu + 3 感谢分享!

查看全部评分


上一篇:Salesforce infra 实习店面12/12
下一篇:Yelp 技术电面12/12

本帖被以下淘专辑推荐:

  • · Google|主题: 459, 订阅: 131
  • · G|主题: 16, 订阅: 3
我的人缘0
stellari 2016-12-14 04:49:51 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   99% (499)
 
 
0% (5)    👎
henryoier 发表于 2016-12-13 07:07
我的想法是: 不失一般性,首先假定m > n否则我们将m,n对调,那么枚举边长从1 到 n的正方形去覆盖一个矩形 ...

这种方法的假设是“L的最佳分割法中的某条边界一定能够把L恰好切成两个矩形”。但是这个假设应该并非总是成立的。比如177x176

所以此法恐怕不行
回复

使用道具 举报

我的人缘0
henryoier 2016-12-13 07:07:28 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
我的想法是: 不失一般性,首先假定m > n否则我们将m,n对调,那么枚举边长从1 到 n的正方形去覆盖一个矩形的一个角,那么剩下的L形(如果正方形边长为n那么剩下的是一个矩形)可以有两种分解的方法。那么状态转移方程式为dp(m, n) = min{min{dp(m, n - i) + dp(m - i, i), dp(i, n - i) + dp(m - i, n)} + 1}, 边界条件是m == n, return 1, m或n中有一个为0 return 0
回复

使用道具 举报

我的人缘0
ke8511368 2016-12-13 06:56:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (5)
 
 
0% (0)    👎
问问: 分解为最少多少个??
什么意思。
是指最少能分解出多少个,还是最多能分解出多少个。每个小方形都算是一个square吧
回复

使用道具 举报

我的人缘0
mmliu 2016-12-13 07:05:23 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   87% (21)
 
 
12% (3)    👎
递归的解法能详细说下么~
回复

使用道具 举报

我的人缘0
byrlhb 2016-12-13 07:12:39 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (66)
 
 
1% (1)    👎
这不leetcode题么
回复

使用道具 举报

我的人缘0
蜗牛君 2016-12-13 07:22:04 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   33% (20)
 
 
66% (40)    👎

题号是?
回复

使用道具 举报

我的人缘0
byrlhb 2016-12-13 07:36:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (66)
 
 
1% (1)    👎

sorry 看错了,
回复

使用道具 举报

我的人缘0
byrlhb 2016-12-13 07:51:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (66)
 
 
1% (1)    👎
henryoier 发表于 2016-12-13 07:07
我的想法是: 不失一般性,首先假定m > n否则我们将m,n对调,那么枚举边长从1 到 n的正方形去覆盖一个矩形 ...

感觉应该是对的

补充内容 (2016-12-13 08:19):
sorry,找到返例了
回复

使用道具 举报

我的人缘0
henryoier 2016-12-13 08:19:28 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (14)
 
 
0% (0)    👎
byrlhb 发表于 2016-12-13 07:51
感觉应该是对的

这是个NP问题...我一个大神同学去面g家最后一轮第一题就是这个他上来先证了个NP,不知道他后来给的解法是什么...
回复

使用道具 举报

我的人缘0
期末求过 2016-12-13 11:59:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   80% (4)
 
 
20% (1)    👎
henryoier 发表于 2016-12-13 08:19
这是个NP问题...我一个大神同学去面g家最后一轮第一题就是这个他上来先证了个NP,不知道他后来给的解法是 ...

反例是啥,dp不行吗
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-12-12 12:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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