Oracle首席工程师：技术面试中，怎样的问题才是好问题？( 五 ) 作者介绍熊燚

极端地说，这个问题可以一直缩小到这样的程度：
假定说有这样一个 API ，名字叫做 isAllowed ，这个 API 在系统每次收到请求的时候就调用，传入的是请求对象，传出 boolean 值表示是否允许这次调用——如果最近一分钟内调用次数小于 10000 次就允许，反之则不允许。你能否将这个 API 实现出来？
如果候选人还一脸迷茫，可以提供这样的参考 API：
class RateLimiter {
public boolean isAllowed(Request req) {// TODO
}
}
你看，这只是一个将问题明确、细化和分解的过程，并没有涉及到实际实现代码该用的算法。但是，上面提的那些问题，要么通过这个例子明确了，要么给出具体数字了。
这本身，就将一个模糊的问题，降低难度明确为一个具体的算法问题了。
2、不止一个解
前面一步已经谈到了有不同的方式可将模糊的 “实际问题” 映射成一个可解的 “软件问题” 。而现在，这个 “软件问题” 依然没有标准答案。
可能会有几个参考答案，它们互相比较起来各有优劣。但大多数情况下，候选人的思路都会在这几个参考答案的思路之中，不过有时也能看到特立独行的新奇思路。
如同前一步所说的那样，对于不同级别的软件工程师职位来说，需求分析、系统设计这些方面的要求可能有着很大的差别。但是在这一步，对于数据结构和算法这样的基础能力，却是接近的。
这里谈到的流量控的算法，实现方式有很多种，代码复杂程度，控制精度，时间复杂度和空间复杂度等等都有着非常大的区别。当然此时涉及到的，只是基本算法层面的话题。
我可以再举一个我曾经常用在面试中的例子：
某社交网站有两百万的注册用户，每个用户都有积分属性，且积分根据用户在社交网站上的行为而不断有小幅度的频繁变更（比如登陆一次就+1 分，评论一次就+2 分等等），怎样设计一种算法，能够高效、准确地实时获取指定用户在所有用户中基于积分的排名？
上面的问题从模糊逐步落实到实现上的时候，异步、定时地排序，是最容易想到的方案，而题目表述中的 “高效” 和 “实时” 这两个修饰词让这个问题变得困难。这个过程中，我见到的不错的办法就至少有七、八种，比方说，下面这个推进问题解决的例子：
候选人：在需要的时候进行排序，方案是……
面试官：好，这样的方式下，时间、空间复杂度是多少？
候选人：……（说着说着自己意识到时间消耗可能巨大）
面试官：对，你能否优化？
候选人：……（提出了一些优化思路，但是他自己对它们的实时性也不满意）
面试官：好，有换个角度更进一步优化的方式吗？
候选人：对了，可以让数据一直是排好序的！
面试官：好主意，那你怎么设计数据结构呢？
候选人：我可以使用一个 map 来保存用户 id 到积分的映射，再把积分从小到大按序放在数组中，这样二分查找就可以找到对应积分所处的排名。
面试官：听起来不错，那么这时候获取排名的复杂度是多少？
候选人：……
面试官：对，每当用户的积分小幅变化的时候，你怎么维持这个数组依然有序？
候选人：从数组中拿掉一个老的积分，再放入一个新的积分……
面试官：这个变更影响的数据量有多少，时间复杂度又是如何？
候选人：……
面试官：不错，可这个方法有什么问题吗？
候选人：（恍然大悟）如果新添加一个用户，新的积分会出现在数组头部，数组内的所有数据都要向后移动一个单位！
面试官：没错，那你打算怎么优化？
候选人：可以把数组内的积分从大到小排序，这样新添加的用户所对应的积分总在尾部。
面试官：很好，这个方法还有什么问题吗？