龙空技术网

从一道Google的面试题说起

Stephen的小书屋 313

前言:

而今咱们对“google面试算法”大约比较注意,朋友们都想要分析一些“google面试算法”的相关文章。那么小编同时在网络上收集了一些对于“google面试算法””的相关内容,希望各位老铁们能喜欢,兄弟们快快来了解一下吧!

今天先讲Google的一道面试题,它其实是考察候选人的工程思维,题目是这么说的:

给你两个一模一样的玻璃球。这两个球如果从一定高度掉到地上就会摔碎,当然,如果在这个高度以下往下扔,怎么都不会碎,超过这个高度肯定就一次摔碎了。

现在已知这个恰巧摔碎的高度范围在1层楼到100层楼之间。如何用最少的试验次数,用这两个玻璃球测试出玻璃球恰好摔碎的楼高。

为了便于你理解这道题,我不妨讲两个具体的策略。

第一个策略是从第一层楼开始,一层一层往上试验。 你拿着球跑到第一层,一摔,没有碎,接下来你又跑到第二层去试,也没有摔碎。你一层层试下去,比如说到了第59层摔碎了,那么你就知道它摔碎的高度是59层。这个策略能保证你获得成功,但显然不是很有效。

第二个策略是预测一下,试一试, 你跑到30层楼一试,没有碎,再跑到80层楼一试,碎了。虽然你把摔碎高度的范围从1-100减小到30-80,但接下来你就犯难了,因为你就剩一个球了,再这样凭感觉做试验,可能两个球都摔碎了,也测不出想知道的高度。

这道题好的方法是什么呢?两个球,一个用来做粗调,一个用来做精调,具体做法是以下这样的。

首先拿第一个球到10层楼去试,如果没有摔碎,就去20层楼,每次增加10层楼。如果在某个十层摔碎了,比如60层,就知道摔碎的高度在51-60层之间,接下来从51层开始一层层地试验,这样可以保证不出二十次,一定能试出恰巧摔碎玻璃球的高度。

数学好的读者朋友可以去证明一下这是从统计的角度讲最优的策略,为了照顾所有的读者,我就不占用时间证明了。

这道题和计算机技术完全无关,和产品设计或者市场推广似乎也无关,那么为什么Google要考这道题?其实有两个目的, 一是为了找到聪明人,二是为了判断这个候选人的工程素养。

世界上顶级的公司在招人时都要强调一个人未来的可塑性,其中的一条就是要足够聪明便于培养,因此都会考一些看似智力题的问题。这个传统在IT行业,特别是在硅谷,源于诺贝尔奖获得者夏克利挑选人的思维方式。

为什么可塑性比过去的经历重要呢?因为大部分公司招人是做未来的事情,而不是重复过去的事情,尤其是对于大学刚毕业的年轻人,过去在大学几年学的东西,和后来一辈子要不断学习的东西相比,实在少得可怜。

因此, 如果一个资质平庸、学习能力不强的学生在大学时多学了一点专业知识,比那些聪明好学,少学一两门专业课的人相比,后劲是不足的。

不过,如果你今天再应聘这些顶级跨国公司,倒不必太担心被考这样的智力题,这要感谢美国的政治正确。一些左派人士讲,那些智力题有歧视倾向,因为它们让一些族裔的人显得不聪明,而政治正确要强调的是必须承认所有的族裔同等聪明。当然这是题外话。

那么这道题考的是什么样的工程素养呢?就是今天标题所说的粗调和精调。如果我要问,有一个数字是40.365,比如说天文望远镜的焦距,你怎样达到它?

一般人按照生活直觉,直奔这个数字去就可以了。但是在工程上,这样简单的一个数字并非抽象的,而是非常具体的。

如果是天文望远镜的焦距,你是否会用手把握着望远镜的那个圆筒,前后移动,估摸着镜片之间的距离来调整呢?如果这是导弹发射的角度,你自己是否会用个量角器估算导弹和水平线的角度呢?

显然我们不能这么做,我们必须有一个可以准确达到这个数字的办法,这就是工程的思维—— 不仅仅要知道目标在哪里,还必须设计一个能够达到目标的道路。

对于天文望远镜,设计它们的工程师必须设计一个能够转动的旋钮,让它的长度接近40.365这个数字。

精确的天文望远镜

但是接下来的问题来了,如果这个旋钮每转动一圈,调整的幅度太大,要调到小数点后面三位几乎不可能。如果每转动一圈调整的幅度太小,比如每次调整0.001,那么可能要花很长时间才能调到40.365这个数。类似地,调整导弹的角度也是如此。

那么工程师们是怎么做的呢?就是要 设计各种粗调和精调的方法。

在中国学习生物时用过光学显微镜的朋友,可能还会记得在显微镜上有两个旋钮, 第一个是粗调,让你大致看到图像,第二个是精调,能让你看清楚图像。

如果不用粗调,只用精调,不仅做事的效率会很低,而且可能会因为一开始的范围找得不对,在花了半天时间后没有找到后,最后干脆放弃了尝试。

今天最先进的手术机器人的精度可以做到0.001毫米,这样精密的仪器里面的电机一开始速度相对比较快,否则一个手术做的时间会长得不得了。

但是手术刀接近目标距离时,会变得非常慢,但精度会非常高。这样,手术机器人才能同时保证效率和准确性。

类似地,任何一个机器学习的过程,其实都是不断地调整数学模型参数的过程,直到参数收敛到最佳点。

每一次调整被称为是一次迭代,调整的幅度被称为迭代的步长。一开始的时候,迭代的步长要比较大,这样能够很快地确定大致范围,效率比较高。

这就如同测试玻璃球的那个问题中,一开始一次测试10层是一样。但是,如果总是把步长设计得很大,那么最后可能会找不到最佳的参数,因为要么走过头了,要么没有走到。因此,机器学习到最后需要缩小步长,进行精调,以保证最后收敛到最佳点。

世界上每年有很多机器学习方面的论文,都是围绕提高学习效率展开的,而其中的核心其实就是怎样用最少次迭代,完成模型的训练。当然,任何好的机器学习算法都不是事先人为设定步长,而是在学习的过程中,自动找到合适的步长。

这种粗调和精调结合的工程设计方式,并不限于“调节”这个范围,而且用于了很多工程产品的设计。

比如本田最新的超级跑车NSX有四个发动机。一个传统的汽油发动机提供主要动力,这相当于是粗调。一个电动发动机提供在起跑一瞬间快速的加速,这相当于精调。

一辆汽车如果发动机功率太小,加速会比较慢,如果功率太大,在平时巡航的时候会太费油。因此混合动力的汽车就通过粗调和精调解决了这个矛盾,这也是为什么它比较省油的原因。

至于NSX为什么还有第三、第四个发动机,那是分别安装在两个前轮上的,主要是给它转向时提供动力,这两个很小的发动机甚至可以让轮子一个加速,一个减速,以减小拐弯半径,做大家在电影里看到的特技转弯的动作。当然这个功能用得更少了,属于进一步的精调。

能否通过一个发动机达到同样的目的呢?不是不可以,有一些极致的超级跑车就是这么做的,比如后轮可以拐弯,但是这样的工程极为复杂,成本比四个发动机要高得多。

粗调和精调的思维方式其实在生活中也有应用。很多时候我们先用低成本解决主要问题,然后再想办法把最后5%、10%做好。

标签: #google面试算法