分享一下Google笔试算法题_求职面试_非技术区_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 非技术区 > 求职面试 > 分享一下Google笔试算法题

分享一下Google笔试算法题

 2010/11/3 11:57:42    程序员俱乐部  我要评论(0)
  • 摘要:今天我又干牛B事情了……听说三教有Google的实习生招聘笔试,再想到传说中Google笔试里的牛题,我毫不犹豫地就杀去了。说实话,我倒真没想认真做题,只是过去看一看传说中的Google笔试题是什么样子的。由于我什么都没准备,连事前是否要报名都不知道,因此呢,与其说是“处女笔”,倒不如说是一次“霸王笔”。BBS上说要带简历和成绩单,于是打印了一份巨牛无比的“简历”和很不像话的成绩单。考试时间19
  • 标签:笔试

今天我又干牛B事情了……听说三教有Google的实习生招聘笔试,再想到传说中Google笔试里的牛题,我毫不犹豫地就杀去了。说实话,我倒真没想认真做题,只是过去看一看传说中的Google笔试题是什么样子的。由于我什么都没准备,连事前是否要报名都不知道,因此呢,与其说是“处女笔”,倒不如说是一次“霸王笔”。BBS上说要带简历和成绩单,于是打印了一份巨牛无比的“简历”和很不像话的成绩单。

考试时间19:00-20:30,来自各个学校的人几乎坐满了整整一层楼的教室。两个挂着工作牌的MM进来,给每个人发了一张质量巨好的草稿纸和一个用来把试卷、简历、成绩单固定在一起的曲别针。试卷很厚一叠。选择题很简单。编程题没看(最讨厌在纸上写代码了)。算法题很有意思,和大家分享一下。

说有一台机器,上面有m个储存空间。然后有n个请求,第i个请求计算时需要占R[i]个空间,储存计算结果则需要占据O[i]个空间(其中O[i]<R[i])。问怎么安排这n个请求的顺序,使得所有请求都能完成。你的算法也应该能够判断出无论如何都不能处理完的情况。

比方说,m=14,n=2,R[1]=10,O[1]=5,R[2]=8,O[2]=6。在这个例子中,我们可以先运行第一个任务,剩余9个单位的空间足够执行第二个任务;但如果先走第二个任务,第一个任务执行时空间就不够了,因为10>14-6。

这个题到底该怎么整呢?我当时花了全部的时间去想各种网络流、费用流、图的分层思想等等,最后写了一个铁定错误的贪心上去。直到考试结束4个小时以后我才想到了正确算法的——只需要按照R值和O值之差(即释放空间的大小)从大到小排序,然后依次做就是了……

来自:http://www.matrix67.com/blog/archives/1714

发表评论
用户名: 匿名