江苏龙网

  1. 首页 > 人文 > >

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


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


推荐阅读


上一篇：iPhone12值不值得买？一张图带你看完苹果新品发布会

下一篇：安卓给苹果设坑？苹果12 mini做小屏试水，可预约少的可怜