从一道面试题谈起,大厂到底看重程序员的什么能力?
唐磊，他谦逊的自我介绍，是“在阿里云打工的清华学渣”。
上周的一篇《字符串比较，居然暗藏玄机》，我最早是在唐磊《这10行比较字符串相等的代码给我整懵了》里看到的，我用通俗的语言，展开了“密码破解”案例。文末却没有提引用的出处，这里和唐磊道个歉。
看了唐磊的其他一些文章，源于一线，深入细节，不禁想起了4-5年前提笔写技术文字的自己。
希望他的好文被更多热爱技术的小伙伴看到，这里转一篇唐磊的好文。
文章：《从一道面试题谈起，大厂到底看重程序员的什么能力？》
这是我在面试过程中，经常问的一道题。一起看看，一起动笔试试吧。
实现一个函数，完成开根号的操作：
double sqrt(int v, double t)要求：（1）不能调用系统库函数，例如 Math.sqrt(v)；（2）假设计算出的结果为 r，要求满足这个条件： 
，其中
是真实的值， t 为给定的一个误差范围，例如0.1等，即你计算出的值要在给定的误差范围内； 画外音：例如，调用你的接口 sqrt(9, 0.21) 返回值属于 [2.79, 3.21] 这个区间就行。你可以拿出笔和纸，尝试解答一下。画外音：leetcode上遇见过类似的也没问题。
面试官：有什么思路吗？可能候选人内心在骂你：出这样的题目是不是有病啊，明明有 lib 函数可以直接用的。
求职者：没有啊。
我想说的是，面试，并不在于题目本身，而是以题目为抓手，考察候选人在分析问题和解决问题的能力，以及在交流过程中，所体现的理解能力，逻辑能力和思维方式，当然，也会从 Code 中考察候选人的编程习惯与编程风格。
此时，我会引导候选人：
面试官：根号10等于多少？这里是希望提醒候选人，要先解决，再优化。在实际工作场景也一样，先思考解决问题的方法，再考虑优化。
求职者：3点几吧。
面试官：你怎么知道是3点几？求职者：9开根号是3，明白了，我再想想……
暴力搜索法面试过程中，很多人能回答到这一步：先用一个循环找到 r，使得 r^2 是离给定 v 最近的平方数，即你希望算根号10 ，先找到3，因为3^2=9 。然后再用一个循环， 每次 r+=t ，直到 r^2 > v 为止。
面试官：这是一个可行的方案，但如果精度要求很高，v 也很大，如 sqrt(v = 10000000, t = 0.000001) 之类的，效率不会很低么?其实，在与候选人的不断交流中，可以看出候选人的理解能力，与解决问题的能力，这本身也是面试过程中的一部分。
求职者：可以这样优化，比如设置一个步长，一次迭代后，如果没有达到预期，可以不断修改这个步长来增大逼近真实值的速度，比如10倍误差，100倍误差等。
面试官：恩，这样做确实可以优化。但从本质上讲，该题目其实是在一个有序的列表里，去搜索满足条件的特定的值。除了你说的线性搜索，还有其它方法吗？
求职者：二分搜索？
面试官：借助二分的意思就是，比如算 根号10，搜索范围是 [0, 10]：
- 因为5^2 = 25 > 10 ， 所以 r 属于[0, 5)
- 因为(5/2) ^2 = 6.25 < 10 ， 所以 r 属于 (2.5, 5)
- 因为(3.75^2 = 14.0625 > 10) ，所以 r 属于 (2.5, 3.75)
- ...
求职者：明白了。
能写出二分，作为一线开发者基本就不成问题了。
但很多人都喜欢用递归写，却容易遗漏递归里的结束条件。所以一般情况下，代码写完后，我会让候选人自己写测试用例。
面试官：假设这个接口是别人写的，应该从哪几个角度去测试？为什么要别人提示要测试用例，才去 check 自己写的代码的正确性呢。
求职者：sqrt(-4, 0.21)，哎呀，我这里忘了判断了。改一下代码。
求职者：sqrt(0, 0.21)，sqrt(4, 0.21) 还有问题，再改改。
面试官：……
能够到达这一个步骤的人已经较少了，如果你有较全测试用例和边界条件的判断，再加上后面的结束条件能够正确，基本上这道题目就算满意了。
关于结束条件本质上讲，这个算法就是一个迭代逼近的过程，用二分的思路后，关键就在于什么时候结束。 题目中已经给了误差条件
，难点在于其中的不知道，不太方便直接进行计算判断。不少人用一个另外的结束条件来进行了判断即： 
，额，这一样吗？其他解法当然本题还有一些其他的数学解法，例如用牛顿迭代法，梯度下降法，泰勒公式展开等等。如果候选人能想到这些，说明他还是有一定数学基础的，可以让他讲讲。
结语其实，上面大部分内容只谈到了这道题目本身，也穿插了一些对这道题目的分析和理解，这样的题目考察校招的同学会比较合适。 但类似的题目，社招完全不适用吗？社招的的同学，写不出来就有很充分的理由吗？
或许你在工作场景中不会遇到实际这种题目，但我其实想表达的是，作为一线的工程师，在面试官讲解了二分算法，并且自己也能理解的情况下，写出相关的 Code ，真的很过分吗？
在日常有些场景下，“复制粘贴”工程师貌似也够用，遇到问题，叫更高水平的人来帮你，这样的话，你的核心竞争力在哪里？
我建议一线的程序员们，应该对基本的数据结构和算法有所了解，对常见的算法复杂度有所了解。这样的要求，不高吧。
之前遇到过一些候选人，Java 开发七八年经验了，却不清楚 ArrayList, HashMap 内部是怎么做的。还有些候选人，口头表达头头是道，结果落实到写代码就根本下不了笔。
希望我们不要抛弃一些基础的东西，多培养一下我们的编程素养，在用编程语言，利用各种工具来实现我们想要达到的目的的时候，能做到“知其然，知其所以然”。
==全文完==程序猿石头
希望大家有收获，欢迎扫码，关注这个“在阿里云打工的清华学渣”。
评论