谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 1009|回复: 7
收起左侧

[编程题] 这样的熄灯问题会不会面试?

[复制链接] |试试Instant~ |关注本帖
我的人缘0
数字媒体技术 发表于 2014-5-16 21:40:47 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

x
本帖最后由 数字媒体技术 于 2014-5-16 21:45 编辑

2.jpg 3.jpg 4.jpg 5.jpg 6.jpg 7.jpg 360桌面截图20140516213320.jpg



这得老长时间了。。。
4.jpg

上一篇:Binary Tree和Binary Search Tree的递归写法空间复杂度?
下一篇:关于怎么刷算法题的困惑
我的人缘0
ccarter 发表于 2014-5-23 14:31:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
本帖最后由 ccarter 于 2014-5-23 14:33 编辑

会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历所有可能 但是复杂度太高
我们考虑这样的一个矩阵
11010
00100
01001
........
如果我不动第一排的灯,那我怎么能让第一排的第三个和第五个灯熄灭呢?我只能通过第二排的第三个灯和第五个灯。注意第二排我只能动第三个和第五个灯,动其他灯都会造成第一排的某个灯亮起。
这样矩阵变成了:
11111
01001
01100
........
对第三行做同样的操作:目的是灭掉第二行亮着的灯。只能操作第三行的1、3、4号灯。如此往复直到最后一行,如果最后一行操作完,也全灭了,那你就成功了……
于是问题变成了:第一行应该怎么操作。
这个就好办了,2^n遍历。然后进行刚才介绍的操作看最后一行能否全灭。总复杂度(2^n)*m*n。
那如果n特别大呢?比如5*100000?那当然按列操作了……所以总复杂度是(2^min(m,n))*m*n。如果m和n都特别大呢?面试不会问的,相信我……(其实是我也不知道有没有有效的算法了)

评分

参与人数 2大米 +30 收起 理由
北美农民 + 15
RonHe + 15

查看全部评分

回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
RonHe 发表于 2014-5-23 17:19:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ccarter 发表于 2014-5-23 14:31
会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历 ...

赞思路。这个面试的时候会要求把代码也写出来么
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 数字媒体技术 发表于 2014-5-23 22:01:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
ccarter 发表于 2014-5-23 14:31
会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历 ...

大神啊!我写出来要一个多小时。。。。
回复 支持 反对

使用道具 举报

我的人缘0
robinho364 发表于 2014-5-23 22:39:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个问题是经典算法题,早就被人研究透了。

复杂度就是mn(2^n),我相信很难有更优的算法了。

事实上也可以用高斯消元法求一组解。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| 数字媒体技术 发表于 2014-5-23 22:43:07 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
robinho364 发表于 2014-5-23 22:39
这个问题是经典算法题,早就被人研究透了。

复杂度就是mn(2^n),我相信很难有更优的算法了。

嗯,我刚刚开始算法这类的训练,以前玩开发,用些小工具,活少简单,算法太难,懒得搞~
回复 支持 反对

使用道具 举报

我的人缘0
robinho364 发表于 2014-5-23 22:46:21 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
哦,对了。

如果你只要求输出一组解的话,高斯消元的确就是高效解法哈。
回复 支持 反对

使用道具 举报

我的人缘0
robinho364 发表于 2014-5-23 22:53:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
数字媒体技术 发表于 2014-5-23 22:43
嗯,我刚刚开始算法这类的训练,以前玩开发,用些小工具,活少简单,算法太难,懒得搞~

Hi,突然发现你看的是pku的课件?

pku讲的倒是很不错!
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html





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

custom counter

GMT+8, 2018-6-24 13:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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