从一道面试题谈谈一线码农应该具备的基本素质

码农翻身 · 公众号 · 程序员 · 2016-12-30 17:55

正文

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

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

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

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

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

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

题目

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

double sqrt(int v, double t)

要求:

不能调用系统库函数, 诸如 Math.sqrt(v) 之类的;
假设函数的返回结果为 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
因为(3.75^2 = 14.0625 > 10) , 所以 r 属于 (3.75, 5)
继续, 如果你结束条件不太确定, 可以暂时不管…

我觉得我提示到这里, 已经很明显了.

A: 你现在明白了吗?
B: 明白了.
A: 那你写一下代码吧.

一个二分搜索, 算法都结合例子讲一遍了, 在候选人回答明白的情况下, 理想当中, 作为一线开发者写出来应该不成问题吧.
然而…理想和现实还是有差距的.
很多人都喜欢用递归写, 可是很多人递归里面的最重要的结束条件都木有, 一些边界条件等等都木有. 所以一般情况下, 代码写完后, 我会让候选人自己写测试用例.