面试题应该来源实践

2014-06-15

花一天的时间把《剑指offer》看完了。说实话,不敢恭维。

以前总觉得,面试不必要刻意准备,自然地发挥就可以了。但后来发现,面试中总是遇到傻逼太多,牛逼的太少。正常人是干不过傻逼的,因为傻逼总是会把你的智商拉到跟他同一水平,再用它丰富的经验打败你。

于是就有了这类书就有了市场,它让傻逼迅速积累经验。

我觉得面试题应该来源于实践的,而这类题目却与实践大大脱节,它考察的是一个人有没有刻意去准备。我可以立刻想到一些实用的面试题,都是实践中遇到的:

1.在一块矩形区域内随机选取一些点,要求任意两个点之间的距离不小于一个值

这个是一个同事做的一款手机游戏中的一关,它要在屏幕上随机位置生成一些鬼火,然后用多个手指 点同时把所有的鬼火都点上,就可以过关了。大概随机出5到6个点就够了,如果点数更多可以加大难度。因为位置随机,如果两个点靠得太近,手指的姿势会很别扭,会很不好点。

回到题目,菜鸟级别应该立马可以想到最暴力的方法,随便生成一些点,然后做校验,如果满足条件就退出,否则再随机生成一批数据。分析一下复杂度,生成数据O(n),校验数据O(n^2)。如果能想着排序之类的方式去把校验过程的复杂度优化,就是不错的引导。面试应该这种开放式的讨论,不是考察面试者准备的怎么样。

由于校验后不一定满足,可能很多计算都是浪费的。所以,杀一点脑细胞的方式就会再继续思考。在构造的时候就生成满足条件的点。

比如我们可以对矩形区域打一些格子,然后用一个二维数组来标记这些格子。格子的直径的两倍大于要求的距离。然后我们来随机选格子而不是选点。选完一个格子以后,就将它周围格子标记起来,下一次随机选格子的时候,不能选择被标记的格子。最后从选择的格子中去取点,每个格子取一个,由于格子间距离是能保证大于一定值的,最终选取的任意两个点间的距离也是不小于一个值的。

当然,这不是最优解。我可以告诉你工程中最简单的做法,我同事的做法:自已用手在屏幕上点了一些点(感觉大概两个之间距离差不多就行),记录下坐标,存到数组里。然后使用的时候随便到从中取一些就行了......这才是高大上,丝毫不装逼。

2.有很多大小不一的小矩形,如何将它们填充到一个大矩形里面,使得填充得尽量的满,空间利用率尽量高。

做过游戏的人应该都知道texture packer,就是合图啦。把许许多多的小图合到一张大图里,抽象出来就是上面这个问题。

任选一个小矩形,放进去,大矩形剩下的区域就可以分为两个矩形,有两种分法。然后对子矩形递归地执行这个划分过程,就可以得到所有可能的方法。这是暴力的做法。

但是这状态数增长得太夸张,然后就应该思考有什么规律能利用到,比如按从大到小先将小矩形排序。

其实,有更好的答案:问google。这才是最工程的做法,绝对比自己闷着头想来得容易。

算了,扯远了。继续看书...

面试题