Question

前言：我之前写过一篇文章《学会编程，而不是学会 Java 》， 文中那个简单的程序难住了不少人， 我意识到很多人只是掌握了一门语言的语法、类库等基本技能， 但是编程所要求的最最基础的 逻辑思维能力 还是远远不够。

今天推荐一篇 唐磊（微信公众号：唐磊 coder） 写的文章，讲的也是逻辑思维能力， 文中的 面试题是计算平方根， 有一点点数学公式和约束， 别被吓住，就是中学的知识， 仔细想想， 其实很简单。

不要一看到数据结构和算法题就开始喷， 面试官想观察的是解决问题的思路。

我个人认为， 对于这个面试题， 如果面试者有思路，并能实现的很好， 肯定是优秀程序员的候选；

如果没有思路，但是在面试官的提示下能找到二分的方法， 代码也能实现， 这样的人也不错；

就怕是完全没有思路，无论面试官怎么提示都不进门， 这就需要反思一下， 加强锻炼了。

题目

实现一个函数，完成 开根号 的操作，方法签名如下：

double sqrt(int v, double t)

要求:

1. 不能调用系统库函数，诸如 Math.sqrt(v) 之类的;
2. 假设函数的返回结果为 r , 要求 r 要满足一定的误差条件， 用公式表达就是： , 其中 是真实的值 , t 为给定的一个误差，例如 0.1 。 举例而言，我调用你的接口 sqrt(9, 0.1) ， 返回值是 3.05, 就满足上面的误差范围， 因为 9 的平方根是 3 ， |3.05 - 3| = 0.05 ， 0.05 是小于 0.1 的。 如果返回值是 2.95 也是满足条件的。

看到这里, 其实你可以 拿出笔和纸，尝试解答一下，强调一下，一定要注意 给定的误差条件 , 欢迎沟通交流. 其实这个题目是就是 leetcode 上原题稍加变化得到。

解答

其实刚开始，我认为这道题目比较简单，至少在给予提示后，理想当中大部分一线的码农都可以给出实实在在 code 的。

然后事实并非如此，然而在面试很很多人之后，发现此道题目并不简单。当然，估计也是 candidate 的质量问题。

其实，我刚开始面试时还用一些二叉树相关如非递归遍历等题目的，后来基本上没人能写出（社招) 也就放弃了。

当被问起这道题目之后，可能遇到的答案如下，这里我就直接根据答案的满意度排个升序。

直接放弃

题目给出后，我一般首先明确候选人弄清楚了题目的含义然后会给一两分钟让候选人先思考一下。

A: 你有什么思路吗?

B: 没有啊。

可能候选人内心 OS 是: “你出这样的题目是不是有病啊，明明有 lib 函数可以直接用的”.

(同组有小伙伴确实有遇到这样的候选人，语言虽没这样夸张，大意是: 实际工作中会出现这样的问题吗? 我直接给你百度一个就行了)

也有候选人刚开始抱着那个约束误差范围的不等式研究 N 久，然后没有然后了的. 刚开始看这个条件当然好，但如果这个不等式没有思路可以先放一放，没必要在那苦熬。

A: 这样吧，如果我问题 根号 10 等于多少，你怎么回答。

B: 3.? 吧

A: 你怎么知道是 3.几，因为你知道 9 开根号是 3, 想象一下，你可以完全用程序帮忙模拟你大脑思考的过程。

B: ……

其实这里是希望提醒候选人，我们首先是要解题，然后才考虑效率. 即不管用什么方法能够给出一个答案的. 这个时候候选人可能进入下一个阶段了。

暴力搜索

实际面试过程中也有人是直接到这个阶段的。

先用一个循环找到 r, 使得 r^2 是离给定 v 最近的平方数，即你希望算根号 10 , 先找到 3, 因为 3^2=9 , 计算根号 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 属于[0, 5)
• 因为(5/2) ^2 = 6.25 < 10 , 所以 r 属于 (2.5, 5)
• 因为(3.75^2 = 14.0625 > 10) , 所以 r 属于 (3.75, 5)
• 继续，如果你结束条件不太确定，可以暂时不管…

我觉得我提示到这里，已经很明显了。

A: 你现在明白了吗?

B: 明白了。

A: 那你写一下代码吧。

一个二分搜索，算法都结合例子讲一遍了，在候选人回答明白的情况下，理想当中，作为一线开发者写出来应该不成问题吧。

然而…理想和现实还是有差距的。

很多人都喜欢用递归写，可是很多人递归里面的最重要的结束条件都木有，一些边界条件等等都木有. 所以一般情况下，代码写完后，我会让候选人自己写测试用例。

A: 写好了是吧，你写几个测试用例吧，假设这个接口是别人写的，你应该从哪几个角度去测试。

B: sqrt(-4, 0.21), 哎呀，我这里忘了判断了，改一下代码

B: sqrt(0, 0.21), sqrt(4, 0.21)… 还有问题，再改改

A: ……

为什么要别人提示要测试用例，才去 检查自己写的代码的正确性呢. 有的候选人写的代码，就不拿一些异常情况去检查，就用上面讲的 sqrt(10, 0.21) 的例子都得不到预期结果。

能够到达这一个步骤的人已经较少了，如果你有较全测试用例和边界条件的判断，再加上后面的结束条件能够正确，基本上这道题目就算满意了。

关于结束条件

本质上讲，这个算法就是一个迭代逼近的过程，用二分的思路后，关键就在于什么时候结束. 题目中已经给了误差条件, , 难点在于其中的不知道，不太方便直接进行计算判断。

不少人用一个另外的结束条件来进行了判断即: , 其实这两个条件是不一样的，应该是不符合本题目的条件的。

对于这个结束条件，你有什么看法吗? 能证明你的想法吗?

面试的人多了，感觉预期都有所下降了. 现在基本上如果能够把整个二分整体框架写出来，还能分析个二分复杂度之类的，一些基础还说得过去，我这里也就算过了. 当然目前我司是 3 轮技术面过才能拿到 Offer.

其他解法

当然本题还有一些其他的数学解法，例如用牛顿迭代法，梯度下降法（最速下降法), 泰勒公式展开等等。

如果候选人能想到这些，说明他还是有一定数学基础的，如果愿意可以让他讲讲。

对于这道题目，你有什么比较好的思路吗? 欢迎讨论。

结语

本文题目是"从一道面试题谈谈一线码农应该具备的基本素质”, 其实，上面大部分内容只谈到了这道题目本身（也穿插了一些对这道题目的分析和理解).

上述题目的场景是社招面试中的，对于这样的题目来说校招的反馈会更好，但我想说的是，难道社招确实写不出来么? 我其实想表达的是，作为在最前线 coding 的码农，在别人讲解了二分算法的条件下，能写出这个二分算法难道不是一线码农应该具备的基本素质?

一线码农难道不应该对一些基本的算法有所了解? 对常见的算法复杂度有所了解? 比如二分搜索复杂度为什么是 .

很多人对算法复杂度的概念了解甚微，面试前死记硬背，但二分搜索的复杂度应该还是能推导出来吧，没让推导快排啊（啊，我自己貌似也忘记了快排复杂度的推导).

之前有一个候选人, Java 开发七八年经验了，问 ArrayList, HashMap 怎么实现的都不知道。

还有一个印象比较深，在 XX 做搜索，面试职位也是开发啊，结果落实到代码就根本下不了笔。

还有候选人写精通 Java, 结果连 GC 原理都不清楚，还有什么熟练掌握 Vim, 结果连基本文本替换都不会。

本文题目貌似取的范围有点大，本篇强调的主要还是 coding 能力，不过对于一线开发者来讲, coding 能力难道不是最基本中的基本吗?