go.blog/面试题应该来源实践.md at master · tiancaiamao/go.blog · GitHub
花一天的时间把《剑指offer》看完了。说实话，不敢恭维。
以前总觉得，面试不必要刻意准备，自然地发挥就可以了。但后来发现，面试中总是遇到傻逼太多，牛逼的太少。正常人是干不过傻逼的，因为傻逼总是会把你的智商拉到跟他同一水平，再用它丰富的经验打败你。
于是就有了这类书就有了市场，它让傻逼迅速积累经验。
我觉得面试题应该来源于实践的，而这类题目却与实践大大脱节，它考察的是一个人有没有刻意去准备。我可以立刻想到一些实用的面试题，都是实践中遇到的：
1.在一块矩形区域内随机选取一些点，要求任意两个点之间的距离不小于一个值
这个是一个同事做的一款手机游戏中的一关，它要在屏幕上随机位置生成一些鬼火，然后用多个手指 点同时把所有的鬼火都点上，就可以过关了。大概随机出5到6个点就够了，如果点数更多可以加大难度。因为位置随机，如果两个点靠得太近，手指的姿势会很别扭，会很不好点。
回到题目，菜鸟级别应该立马可以想到最暴力的方法，随便生成一些点，然后做校验，如果满足条件就退出，否则再随机生成一批数据。分析一下复杂度，生成数据O(n)，校验数据O(n^2)。如果能想着排序之类的方式去把校验过程的复杂度优化，就是不错的引导。面试应该这种开放式的讨论，不是考察面试者准备的怎么样。
由于校验后不一定满足，可能很多计算都是浪费的。所以，杀一点脑细胞的方式就会再继续思考。在构造的时候就生成满足条件的点。
比如我们可以对矩形区域打一些格子，然后用一个二维数组来标记这些格子。格子的直径的两倍大于要求的距离。然后我们来随机选格子而不是选点。选完一个格子以后，就将它周围格子标记起来，下一次随机选格子的时候，不能选择被标记的格子。最后从选择的格子中去取点，每个格子取一个，由于格子间距离是能保证大于一定值的，最终选取的任意两个点间的距离也是不小于一个值的。
当然，这不是最优解。我可以告诉你工程中最简单的做法，我同事的做法：自已用手在屏幕上点了一些点（感觉大概两个之间距离差不多就行），记录下坐标，存到数组里。然后使用的时候随便到从中取一些就行了......这才是高大上，丝毫不装逼。
2.有很多大小不一的小矩形，如何将它们填充到一个大矩形里面，使得填充得尽量的满，空间利用率尽量高。
做过游戏的人应该都知道texture packer，就是合图啦。把许许多多的小图合到一张大图里，抽象出来就是上面这个问题。
任选一个小矩形，放进去，大矩形剩下的区域就可以分为两个矩形，有两种分法。然后对子矩形递归地执行这个划分过程，就可以得到所有可能的方法。这是暴力的做法。
但是这状态数增长得太夸张，然后就应该思考有什么规律能利用到，比如按从大到小先将小矩形排序。
其实，有更好的答案：问google。这才是最工程的做法，绝对比自己闷着头想来得容易。
Read full article from go.blog/面试题应该来源实践.md at master · tiancaiamao/go.blog · GitHub
No comments:
Post a Comment