2009-04-14 1:11| 
60 Comments | 本文内容遵从 今天我又干牛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值之差（即释放空间的大小）从大到小排序，然后依次做就是了……想到这里开始暴汗，有时候最简单的算法往往是最后才考虑到的。
好了，不多说了。最近期中，可能更新慢一些。明天一早考数理逻辑，赶紧抱佛脚。
我的“简历”：
我的成绩单 :-(
沙發
（我發現心情不好的時候就來逛街會變得好一點= =）
成績單。。。。幾分制啊= =。。。？
大哥，我三年没有写过程序了，但你说的算法我一分钟就想到了。虽然我不知道是否正确
差距就在知道正确与否之间
确实是巨牛B的简历....
地毯所言，我觉得有道理。有时最直观的想法其实就是解决问题的办法。
成绩不咋样亚，赶快赶赶吧，提高gpa
re 3楼:就是要证明正确性才有意义吧？乱想谁不会想。假如你碰到一道不会的题，然后设想了1000种做法，其中正好有一个就是对的，你能说这道题你就会做了么？
orz...这简历...
两个挂着工作牌的MM进来，给每个人发了一张质量巨好的草稿纸和一个用来把试卷、简历、成绩单固定在一起的曲别针。
大公司的MM都很PP，走的时候别忘记带走纸和笔。她们的质量真的很好。
re10楼，不过，“她们的质量真的很好”指的是纸和笔还是什么？
还没有霸王笔的人~~飘过~
潜水这么久，出来冒个泡。
这个貌似是算法书上的基础题。
我怎么看到了自己的名字……
太Orz了，拜一拜
拜简历
[...] 转自：http://www.matrix67.com/blog/archives/1714 分类：算法相关 / 04-14-09 / Trackback URI: trackback [...]
确实比较牛B......算法有点复杂
82，我喜欢你的简历，我的话就直接录用你了，你的学分居然敢比老子的还低，B
有意思~
绩点比我高多了...
巨牛无比的“简历”和很不像话的成绩单.......
简历有创意。
{display="none"}
这题应该反过来想，先把O[i]都存进去（存不下铁锭死掉），然后规定把O[i]取出来需要R[i]-O[i]的空闲空间，看能不能取完，这样肯定先取R[i]-O[i]小的。
10楼和11楼，她们的质量很不错，很有意思，哈哈哈
简历很强。。。
这个号称也是google的面试题，请教下怎么做。
11.在一条高速公路上，在30分钟内看到一辆汽车的可能性是0.95，那么在10分钟内看到一辆车的概率是多少（假设过车的概率是恒定的）？
我发现手机上看不清图片,就来PC上再看一遍~
看到你的gmail了- -
简历牛
关于算法的那道题，我画了下图，感觉最后放的一定是R-O最小的那个，其他的顺序无所谓
M67大牛不是中文系的吗？怎么也要学数理逻辑？
楼层: 27楼 | 2009-04-14 19:57 | jupiter 说：
这个号称也是google的面试题，请教下怎么做。
11.在一条高速公路上，在30分钟内看到一辆汽车的可能性是0.95，那么在10分钟内看到一辆车的概率是多少（假设过车的概率是恒定的）？
----------------0.63?
你对我们来说也只是个菜鸟而已！你虽然知道很多各种各样的算法，但你只不过是一个书柜...，实话实说，没有别的意思。
楼层: 32楼 | 2009-04-14 23:14 | 凌晨海风 说：
楼层: 27楼 | 2009-04-14 19:57 | jupiter 说：
这个号称也是google的面试题，请教下怎么做。
11.在一条高速公路上，在30分钟内看到一辆汽车的可能性是0.95，那么在10分钟内看到一辆车的概率是多少（假设过车的概率是恒定的）？
----------------0.63?
为什么呢，能告诉我怎么做吗，还有如果问题改成在根号下10分钟看到一辆车的概率是多少又该怎么做呢？
我怎么感觉按O从小到大排序，就可以啊？
想通了。。。
对于这个例子:m=12, n=2
R[1]=11,O[1]=8
R[2]=9,O[2]=7
你的算法好像不大对,正解应该是按照O从大到小排列吧
贪心算法往往就是先乱序排列,然后考虑如何交换相邻两个元素使目标变优
写错了,应该是
R[1]=11, O[1]=7
R[2]=9, O[2]=8
m=12
昨晚回宿舍的路上想明白我想错了。。大牛你想的没错
每天必看您的博客～很有趣～
身为你的老乡，为你骄傲哈:)
楼层: 35楼 | 2009-04-15 9:30 | jupiter 说：
在10分钟内看到一辆车的概率是多少（假设过车的概率是恒定的）？
----------------0.63?
为什么呢，能告诉我怎么做吗，还有如果问题改成在根号下10分钟看到一辆车的概率是多少又该怎么做呢？
-----------------------
不就是1-(1-x)^3=0.95吗？
如果是根号10分钟，那指数变成了30/根号10而已
这个简历是牛的,出来说一下，哈哈
太强悍了，呵呵
楼层: Answer to Life, the Universe, and Everything | 2009-04-15 21:13 | 凌晨海风 说：
楼层: 35楼 | 2009-04-15 9:30 | jupiter 说：
在10分钟内看到一辆车的概率是多少（假设过车的概率是恒定的）？
----------------0.63?
为什么呢，能告诉我怎么做吗，还有如果问题改成在根号下10分钟看到一辆车的概率是多少又该怎么做呢？
-----------------------
不就是1-(1-x)^3=0.95吗？
如果是根号10分钟，那指数变成了30/根号10而已
能看成独立事件吗
这个算法今天在上班路上想了想，思路是这样
假如请求已排好序，取任意相邻两个请求符号为x,y
假如需要的过程和结果空间为A,a B,b
然后考虑为什么x一定要排在y前呢？
关键是放完x的a再放y的B时所需空间比y在x前小，即
a+B = B-b
然后就是楼主的结论了。
btw: 最开始思考2个请求时得到结论，然后试图用数学归纳法证明出n个也成立，后来发现不行，反省的结果如上。
希望楼主给出思考过程。
发现上个回复被改了成 a+B = B-b
原意为：
a+B = B-b
有意思的题，描述挺简单
简历是巨牛。。。（比较美观）
M……你的C++……你的离散……成绩……
期待 google 回信给你一个大大的 true
我记得google应该是有保密协议的？难道笔试的时候没有？……
这简历无敌了...
简
楼层: 45楼 | 2009-04-16 9:37 | jupiter 说：
楼层: Answer to Life, the Universe, and Everything | 2009-04-15 21:13 | 凌晨海风 说：
楼层: 35楼 | 2009-04-15 9:30 | jupiter 说：
在10分钟内看到一辆车的概率是多少（假设过车的概率是恒定的）？
----------------0.63?
为什么呢，能告诉我怎么做吗，还有如果问题改成在根号下10分钟看到一辆车的概率是多少又该怎么做呢？
-----------------------
不就是1-(1-x)^3=0.95吗？
如果是根号10分钟，那指数变成了30/根号10而已
能看成独立事件吗
--------------------------------------
我觉得楼上答案没错，排队的等待时间应该是个指数分布，分布函数 F(x) = 1 - exp(- lambda * x), x >= 0; lambda > 0;
容易得到上面式子了，我理解这不是看成独立事件，而是因为指数分布无记忆性。参见华中科技大学数学系的《概率论与数理统计（第二版）》高等教育出版社，例2.14
至于为什么排队是指数分布，期待大牛解答。
我来证明一下：
证明：猜测是正确的，这是能完成任务的最好序列，也就是说如果这样的序列不能完成，那别的序列一定不能完成；假定在某一时刻设总空间有m，任取两个任务，设为r1，r2，其相应参数分别为请求r1，r2；剩余为o1，02；假设r1，r2能够顺利完成，其条件为，m>r1; m-o1>=r2=>o1+r2=<m; 而r2，r1不能顺利完成，则有，m<r2，或
m-02r1+o2>m ; 从而r1,r2能完成，而r2, r1不能完成一个限制条件为：r1+o2>m>=r2+o1; 从而有r1-o1>r2-o2;由于r1在前能够顺利通过，而r2在前不能通过，其本质不同在于差值（r1-o1)大的r1先过；故按照r值减去o 值之差从大到小排序，而且为了加快收敛（任务不能全部完成情况），可以把差值相同的任务中请求大的放在前面。
那张简历太有创意了，看文章的时候还真没猜到~~~
ORZ...Matrix67
n个请求的排序，由于计算后，存储单元会减少，所以算法的选择和R[i]有关，认为先计算R[i]大的。又希望O[i]小，这样存储空间剩余的多。所以，想到最后的算法，需同时考虑R[i]和O[i]。
接着，反过来考虑。认为所有的O[i],都已经存储，要取出来。则至少需要R[i]-O[i]的存储空间。先取R[i]-O[i]最小的。
所以，处理n个请求，先处理R[i]-O[i]最大的。
我好像看到了高数66？
很多年不学数学了也看不是很懂，但是要是结论是安释放空间的大小从大到小排序排序的话
m=100 n=2
r1=30 o1=5
r2=80 o2=70
的这种情况应该如何？
谢谢了 我们学校题库里也有这样一道题 用了你的方法顺利AC