背景
谈起这个题目也主要是自己作为面试官参与技术面试多多少少也有五六十次了(算上校招的话更多), 各种各样的人(有厉害的, 也有奇葩的)都遇到过, 虽然当面试官经验不是很多, 但这里也想谈谈自己的一些看法. 或许你有不同的意见或者觉得我的做法有不恰当的地方, 希望你可以指出或参与讨论.
面试本来就是一个双向选择的过程, 面试官和候选人的地位本应该是一个平等的位置, 面试官希望通过简单的交流沟通可以对候选人的技术, 沟通等(可能主要是技术)有一定了解进而确定候选人是否匹配相应的职位.
因为面试时间有限, 1个小时(一般情况)的时间很难去全面了解候选人的技术实力. 所以在面试过程中很难做到完全公平.
举个简单的例子, 面试官出一道题目, 候选人 A 可能曾经做过或见过, 所以能够比较轻松地回答出这个问题, 而候选人 B 没有做过, 虽然不能答出让面试官满意的答案, 但 B 提供了一些解题的思路, 虽然最终并没有答出这道题目, 这就一定说明候选人 B 比 A 差么? 并不见得.
额, 发现编不下去了, 直接上本文 title 里所指的题目吧, 这道题目是我经常出的一道面试题.
(不过这个题目公布后, 以后面试可能就得换题目了, 不过其实鉴于目前我公号/blog的阅读量可以直接忽略的 :( )
题目
实现一个函数, 完成 开根号 的操作, 方法签名如下.
double sqrt(int v, double t) |
要求:
- 不能调用系统库函数, 诸如
Math.sqrt(v)之类的; - 假设计算出的结果为
r, 要求满足如下条件 $|r - \sqrt v| \leq t $, 其中, $\sqrt v$ 是真实的值,t为给定的一个误差, 例如0.1等. 千万别被这个不等式吓住, 其实就是希望你计算出的答案r要在给定的误差范围内. 举个例子, 我调用你的接口sqrt(9, 0.21)返回值属于[2.79, 3.21]这个区间的任意一个都满足条件. 因为 $\sqrt 9 = 3$, 对于任意的 $r \in [2.79, 3.21]$, 都满足 $|r - 3| \leq 0.21$. - 实现语言不限, 你条件可以比上述更加苛刻, 但不能宽松.
看到这里, 其实你可以 拿出笔和纸, 尝试解答一下, 强调一下, 一定要注意给定的误差条件, 欢迎沟通交流. 其实, 这个题目就是 leetcode 上的一个原题 sqrtx 稍加变化得到.
解答中 ing
解答
其实刚开始, 我认为这道题目比较简单, 至少在给予提示后, 理想当中大部分一线的码农都可以给出实实在在 code 的.
然后事实并非如此, 然而在面试很很多人之后, 发现此道题目并不简单. // 当然, 估计也是 candidate 的质量问题.
其实, 我刚开始面试时还用一些二叉树相关如非递归遍历等题目的, 后来基本上没人能写出(社招)也就放弃了.
当被问起这道题目之后, 假设一个候选人从完全没有思路到最后的 Code 环节可能会经历如下一个循序渐进的一个过程.
直接放弃
题目给出后, 我一般首先明确候选人弄清楚了题目的含义然后会给一两分钟让候选人先思考一下.
A: 你有什么思路吗?
B: 没有啊.
可能候选人内心OS是: “你出这样的题目是不是有病啊, 明明有 lib 函数可以直接用的”.
(同组有小伙伴确实有遇到这样的候选人, 语言虽没这样夸张, 大意是: 实际工作中会出现这样的问题吗? 我直接给你百度一个就行了)
也有候选人刚开始抱着那个约束误差范围的不等式研究 N 久, 然后就没有然后的. 刚开始看这个条件当然好, 但如果这个不等式没有思路可以先放一放, 没必要在那苦熬.
A: 这样吧, 如果我问题 根号10 等于多少, 你怎么回答.
B: 3.? 吧
A: 你怎么知道是3.几, 因为你知道9开根号是3, 想象一下, 你可以完全用程序帮忙模拟你大脑思考的过程.
B: ……
其实是希望提醒候选人, 我们首先是要解题, 然后才考虑效率. 即不管用什么方法能够给出一个答案的. 这个时候候选人可能进入下一个阶段了.
暴力搜索
实际面试过程中也有人是直接到这个阶段的.
先用一个循环找到 $r$, 使得 $r^2$ 是离给定 v 最近的平方数, 即你希望算 $\sqrt {10}$, 先找到3, 因为$3^2=9$, 计算 $\sqrt {10011}$, 先找到 $100$.
然后再用一个循环, 每次 $ r += t $, 直到 $r ^2 > v$ 为止.
A: 这个方法从理论上讲, 是一个可行的方案, 设想一下, 如果我的精度要求很高, 希望计算的 v 也很大,
如sqrt(v = 10000000, t = 0.000001)之类的, 调用你这个方法效率是不是很低, 这个时候应该怎么优化?
B: 这样的话, 我这个方法效率确实比较低, 不过可以这样优化, 比如设置一个步长, 一次迭代后, 如果没有达到预期, 可以不断修改这个步长来增大逼近真实值的速度, 比如10倍误差, 100倍误差等.
其实, 在与候选人的不断交流中可以看出候选人在 Problem Solving 的能力, 例如关于上面问题的优化, 也可能用于在实际工作中遇到的问题.
例如, 我们在实际工作中可能经常会写一些异步的回调通知接口等, 这个接口可能是其他团队维护的, 有可能由于网络问题等回调接口可能会失败进而需要重试, 对于重试的机制其实就可以借鉴上面的”步长”机制, 第一次回调失败, 我等待 1s 后重试, 失败再重试, 也许间隔 1s 不太恰当, 是否可以修改等待的步长, 等待比如 5s, 10s? 等等再重试直到成功. 为什么要这样做? 也许对方 server 本来现在就处于峰值, 你不停的重试不但没有增加你接口调用成功的机会, 反而增加对方 server 的负担.
回到这个问题本身, 继续
A: 恩, 这样做确实可以优化, 是不是稍微有些复杂, 你听说过二分搜索/折半查找吗? 可以借用一下这个思路.
B: 我想想…
二分搜索
当然, 部分候选人提示二分后, 就直接能够 get 到点, 并且能够写出二分大体框架, 但很有可能结束条件写的不对.
(当然, 部分人可能之间见到过类似的, 但很有可能精度要求不一样, 这个精度的设置也是为了考察候选人对一个新问题的理解能力, 以及防止刷过题的人直接”背”出答案. 不过, 如果候选人不是很能理解这种思路, 一般会让候选人先忽略这个精度问题. )
如果候选人还没有思路, 就会继续
A: 这样理解吧, 你刚刚的搜索整数部分的过程其实是线性的, 一个一个数去暴力穷举, 借助二分的意思就是, 比如算 根号10, 你搜索范围是, [0, 10] (其实除了几个数之外范围可以更小[0, v/2], 你能证明么?).
- 因为 $5^2 = 25 > 10$, 所以 $r \in [0, 5)$
- 因为 $(5/2)^2 = 6.25 < 10$, 所以 $r \in (2.5, 5)$
- 因为 $((2.5+5)/2) ^ 2 = 14.0625 > 10$, 所以 $r \in (2.5, 3.75)$
- 继续, 如果你结束条件不太确定, 可以暂时不管…
我觉得我提示到这里, 已经很明显了.
A: 你现在明白了吗?
B: 明白了.
A: 那你写一下代码吧.
一个二分搜索, 算法都结合例子讲一遍了, 在候选人回答明白的情况下, 理想当中, 作为一线开发者写出来应该不成问题吧.
然而…理想和现实还是有差距的.
很多人都喜欢用递归写, 可是很多人递归里面的最重要的结束条件都木有, 一些边界条件等等都木有. 所以一般情况下, 代码写完后, 我会让候选人自己写测试用例.
A: 写好了是吧, 你写几个测试用例吧, 假设这个接口是别人写的, 你应该从哪几个角度去测试.
B: sqrt(-4, 0.21), 哎呀, 我这里忘了判断了, 改一下代码
B: sqrt(0, 0.21), sqrt(4, 0.21)… 还有问题, 再改改
A: ……
为什么要别人提示要测试用例, 才去 check 自己写的代码的正确性呢. 有的候选人写的代码, 就不拿一些异常情况去 check, 就用上面讲的 sqrt(10, 0.21) 的例子都得不到预期结果.
能够到达这一个步骤的人已经较少了, 如果你有较全测试用例和边界条件的判断, 再加上后面的结束条件能够正确, 基本上这道题目就算满意了.
哪些边界条件可以考察呢? 除了常规的一些比如负数开根号等, 还可以比如有可能传入精度 t=0 这样的 BT 的输入, 如果候选人代码没有排除这个可能就会导致 “无限循环” 下去(事实情况暂且不讨论), 这个时候再看看候选人的应变能力和思维方式.
关于结束条件
本质上讲, 这个算法就是一个迭代逼近的过程, 用二分的思路后, 关键就在于什么时候结束. 题目中已经给了误差条件,
$ |r - \sqrt v| \leq t $, 难点在于其中的 $ \sqrt v $ 不知道, 不太方便直接进行计算判断.
不少人用一个另外的结束条件来进行了判断即: $ |r^2 - v| \leq t $, 其实这两个条件是不一样的, 这里就需要考察一下候选人是否正确区分并理解这两个条件.
对于这个结束条件, 你有什么想法吗? 你能证明你的想法吗?
面试的人多了, 感觉预期都有所下降了. 现在基本上如果能够把整个二分整体框架写出来, 还能分析个二分复杂度之类的, 一些基础还说得过去, 我这里也就算过了. 当然目前我司是3轮技术面过才能拿到 Offer.
其他解法
当然本题还有一些其他的数学解法, 例如用牛顿迭代法, 梯度下降法(最速下降法), 泰勒公式展开等等.
如果候选人能想到这些, 说明他还是有一定数学基础的, 如果愿意可以让他讲讲, 如果候选人能够井井有条的将牛顿迭代等讲清楚, 且能将代码实现, 那单从这道题目本身来讲肯定是优秀的候选人了.
对于这道题目, 你有什么比较好的思路吗? 欢迎讨论.
常见问题
- 问: 为什么题目中的
v的类型是int?
答: 还真没有理由,double也无所谓, 可能仅仅是因为 leetcode 上原题计算的数是int吧. - 问: 我能正确答对这道题目就一定能通过这次面试吗?
答: 强调一下, 面试中考察这样一个题目, 并不是仅仅考察这道题目本身, 不是说你将这道题做对了, 就能通过我们的面试, 反之, 也不是说你没做对这道题目就一定不能通过我们的面试. 我们通过这道题目为契机, 希望考察的是候选人在分析问题, 解决问题的能力, 在交流过程中所体现的逻辑推理和思维方式等, 当然也有最后实实在在的 code. - 问: 这不是一道数学题目吗, 为什么程序员面试需要考察这样的数学问题?
答: 同上, 不是考察这道题目本身. 另外, 这也不是一道数学题目, 当然能用数学的方式解答. 候选人能用数学的方式解答也算正确. - 问: 二分是这道题目的标准答案吗, 我能用其他解法吗?
答: 同上, 题目没有标准答案, 就算你用最暴力的算法搜索出来也是正确的解法, 其他数学方法也对. - 问: 这道题目这么简单, 牛顿迭代, 二分逼近分分钟秒掉, 是不是太简单了?
答: 欢迎来面试. - 问: 这题目在说什么, 我搞了半天没看懂, 这太难了?
答: 如果看完整篇文章或跟面试官交流了那么久, 你还是根本不明白这到底再说一个什么问题, 那么我真心建议还是趁早转行吧. - 问: 我在实际工作中根本就不会遇到这样的问题, 你问这个有什么用?
答: 同第2条答案, 如果还有疑问, 再见. - 问: 你们公司还缺人么, 面试会考察哪些点?
答: 人一直缺的, 有兴趣或者有其他问题可以戳我邮箱, 邮箱地址: ==gCl1mLpVGbn5WY0BUa (地址没错, 就是这个), 面试考察可能会涉及: CS 基础/Coding/算法/解决问题/项目经验/系统设计/沟通团队协作等等.
结语
本文题目是”从一道面试题谈谈一线码农应该具备的基本素质”, 其实, 上面大部分内容只谈到了这道题目, 中间也穿插了一些对这道题目的分析和理解.
上述题目的场景是社招面试中的, 对于这样的题目来说校招的反馈会更好, 但我想说的是, 难道社招确实写不出来么? (了解了一下, 确实 candidate 的质量不一) 我其实想表达的是, 作为在最前线 coding 的码农, 在别人讲解了二分算法的条件下, 能写出这个二分算法难道不是一线码农应该具备的基本素质?
一线码农难道不应该对一些基本的算法有所了解? 对常见的算法复杂度有所了解? 比如二分搜索复杂度为什么是 $\log_2 N$.
很多人对算法复杂度的概念了解甚微, 面试前死记硬背, 但二分搜索的复杂度应该还是能推导出来吧, 没让推导快排啊(啊, 我自己貌似也忘记了快排复杂度的推导).
之前有一个候选人, Java 开发七八年经验了, 问 ArrayList, HashMap 怎么实现的都不知道.
还有一个印象比较深, 在 XX 做搜索, 面试职位也是开发啊, 结果落实到代码就根本下不了笔.
还有候选人写精通 Java, 结果连 GC 原理都不清楚, 还有什么熟练掌握 Vim, 结果连基本文本替换都不会, 有的会说精通 MySQL, 然而索引的原理也不清楚.
本文题目貌似取的范围有点大, 本篇强调的主要还是 coding 能力, 不过对于一线开发者来讲, coding 能力难道不是最基本中的基本吗?
可能感觉大部分程序员都被大量的需求压迫着, 被产品经理催促着, 仓促地码着繁琐的业务代码, 不断的改着 Bug, 又引入新的 Bug. 业务代码重要么, 当然重要, 但同时也还是希望我们不要抛弃一些基础的东西, 多培养一下我们的编程素养.
全文完, 本人才疏学浅, 望各位看官轻拍.
欢迎交流讨论, Blog 用的 Disqus 评论系统, 如果希望留言讨论的话, 可以找梯子, 或者扫描下面的二维码, 到我微信公众号参与讨论, 感谢.
p.s 如果你觉得这文章对你有那么一点点收获, 请不要犹豫扫描下面二维码关注我的公众号, 如果你再能帮忙转发一下就更好了. 么么哒.
