从一个面试题看程序员的几项基本功

太过爱你忘了你带给我的痛 2023-07-03 12:27 49阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

## 前言 ##

一个优秀的程序员具备挺多特质的，比如好奇心，学习能力等，但在我看来一个优秀的程序员必须具备几项核心能力，哪几项，先卖个关子，程序员最喜欢说的话是「Talk is Cheap, show me your code」,所以先来看一道很常见的面试题

> 如何快速定位IP对应的省份地址？

我们知道，每个省市都分配了一个 ip 段，如下

[202.102.133.0, 202.102.133.255]    山东东营市
    [202.102.135.0, 202.102.136.255]    山东烟台
    [202.102.156.34, 202.102.157.255]   山东青岛
    [202.102.48.0, 202.102.48.255]   江苏宿迁
    [202.102.49.15, 202.102.51.251]  江苏泰州
    [202.102.56.0, 202.102.56.255]   江苏连云港

输入一个 ip 地址怎么做到秒级定位此 ip 所在的省市呢?

![format_png 2][]

*如图示：**在百度上输入一个 ip 地址,能做到秒级展示其所属地,怎么做到的呢，背后用到了什么原理*

这就引入了我们要谈的程序员需要具备的第一项能力: **抽象问题**或者说**数据建模**的能力

## 抽象问题的能力 ##

所谓抽象问题或者说数据建模的能力，即能把一个问题抽象或归类为某种方案来解决，比如要实现负载均衡， 会想到一致性哈希算法，要实现最短路径，想到使用动态规划, 微服务下要保证服务可用引入降级机制等等,一句话就是把具体的问题抽象成到解决此问题背后的方法论，进而用相关的技术方案得以解决。

回归到如何快速定位 IP 对应的省份地址这道题来看，如果我们不具备抽象问题的能力，硬着头皮从头到尾把输入的ip 与所有区间段的 ip 都遍历对比一遍，然后判断它落到哪个区间，那么 ip 地址有 32 位，共有 2^32 个，约有 42.9 亿个，用暴力遍历法每查找一个 ip 最坏情况下要遍历约 42 亿次，这种方法显然是不可行的。

所以我们必须得把这个问题抽象为另一种可行的方法，即：**二分查找**, ip 地址查找怎么就跟二分查找扯上关系了，背后的逻辑是什么，我们一起来看看。

ip 地址不容易比较，那我们首先把 ip 地址转成整数，于是每个省市对应的 ip 地址区间就变成了整数区间,假设为如下区间

[1, 5]
    [11, 15]
    [16, 20]
    [6, 10]
    ....

再以每个整数区间的起始数字对这些区间进行排序，排序后的区间如下

[1, 5]
    [6, 10]
    [11, 15]
    [16, 20]
    ...

看到这些排序后的区间，想到了啥，二分查找就是在一组有序的数字中进行查找！是不是找到相似点了?

这里给没听过二分查找的读者简单普及下啥是二分查找，小时候可能我们都玩过猜字游戏，在纸面上写一个 1 到 100 的数字，比如 70，让对方猜，怎样猜才能猜最快。

1.  首先猜 1 和 100 的**中间数字** (1+ 100) / 2 = 50（取整）
2.  50 < 70, 于是我们继续猜 50 和 100 的**中间数字** (50+100) / 2 = 75
3.  75 > 70，于是我们继续猜 50 和 75 的**中间数字** (50+75) / 2 = 62
4.  依次持续类似以上的步骤，不断地缩小范围，直至找到 70

![format_png 3][]

总共只猜了 7 次，比起我们从 1 猜到 100 效率高了十几倍，如果被猜字的范围从一扩大到成百上千万，提升的效率是指数级的！二分查找也叫折半查找（注意上文中加粗的**中间数字**），仔细看上图，每查找一次，问题规模缩小一半，整体时间复杂度是O(logn)，即使我们要在 42 亿的数字中查找数字，最多也只要查 32 次，所以采用二分查找对查找性能的提升无疑是巨大的！

二分查找是要在一堆**有序**的数字中精准地查找所要查找的数**是否存在**，而回过头来看已经排序好的以下 ip 段

[1, 5]
    [6, 10]
    [11, 15]
    [16, 20]
    ...

我们要查找的是某个整数是否在一个有序数组的相邻两个数字的区间里，例如：取这些 ip 区间的起始地址组成一个数组 （1,6,11,16,....）（有序数组）,如果我们要找的 ip 对应的整型为 14， 由于它在 \[11,16) (11是闭区间，16是开区间) 之间，所以这个 ip 就落在 \[11, 15\] 这个 ip 区间，这样就找到了这个 ip 对应的省市了。

所以就由二分查找某个值是否存在转变成了查找某个值是否在有序数组中相邻的两个值之间了，这就引入了程序员要具备的第二层能力：举一反三或者说修改模型的能力

## 修改模型的能力 ##

就像机器学习，现在其实有很多现成的模型可用，比如识别物的模型等等，我们需要的话可以直接拿来用，但是现有模型的准确率可能不是那么理想（比如只有80%），如果我们需要进一步地提升识别准确率，可能就需要对其参数进行进一步的调优，以进一步地优化模型，达到我们预期的值。

再比如当当网基于 Dubbo 的扩展版本开发的 Dubbox 也是由于原来的 Dubbo 功能不满足其团队需求而在其基础上修改扩展的。

回过头来看以上说的原来二分查找只是查找某个值是否存在，而我们现在要解决的问题是查找某个值是否在相邻的两个值之间,这本质是也是对模型的调优或修改，以进一步满足我们的要求。于是我们写下了如下代码

public static int bsearch(int[] a, int length, int value) {
        int low = 0;
        int high = length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] > value) {
                if (mid == 0) {
                    return -1;
                }
                if (a[mid-1] <= value) {
                    return mid-1;
                } else {
                    high = mid-1;
                }
            }else {
                low = mid + 1;
            }
        }
        return -1;
    }

那这段代码有啥问题吗，或者说有哪些可以优化的空间，这就引入了程序员需要具备的第三项能力: 代码要有足够的健壮性

## 代码要有足够的健壮性 ##

仔细看上文的代码，有两个地方有潜在隐患，一个是 length 可能是负数，而显然数组的长度不可能是负数，也就是说对这种异常数据应该**抛异常**。另外 **(low + higth) / 2** 这段代码中的 low+high 如果在数组很大的情况下比较容易造成溢出，所以可以改造成 low + (high - low) / 2, 另外为了提升性能可以把除以 2 改成位运算，即 **low + ((high - low) >> 1)**，于是代码变成了

public static int bsearch(int[] a, int length, int value) throws Exception {
    
        if (length < 0) {
            // 实际应该抛出一个继续自Exception的异常，这里为了方便直接抛出Exception
            throw new Exception("数据长度不合法");
        }
    
        int low = 0;
        int high = length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                if (mid == 0) {
                    return -1;
                }
                if (a[mid-1] <= value) {
                    return mid-1;
                } else {
                    high = mid-1;
                }
            }else {
                low = mid + 1;
            }
        }
        return -1;
    }

有人可能觉得判断数组长度小于 0 过于严苛了，但是是人就会犯错误，这里也是为了强调我们对异常情况的处理要到位，说到代码的健壮性，这里再多说几句,在创业初期我司主要用的是 php，主要是创业团队追求快，用 PHP 这种弱类型语言开发确实效率高，不过不安全，线上多次出现因为变量可以随意赋值造成的多次线上故障，而 Java 这种强类型语言虽然开发效率上比 PHP 慢了不少，但强类型语言的特征保证了它的稳定，**足够安全**，所以后期随着人员的扩充，为了保证线上足够安全，我司去年把大部分的服务都 Java 化了，近年来有不少人唱衰 Java，但 Java 的安全，稳定性以及强大的生态能力注定了它的长久生命力。

代码写成这样看起来确实完美了，还能再优化吗，注意上文中的代码只适用于 int 的数组，如果用二分查找法进行区间查找具有通用性，比如我们想针对 short 或 long 型等类型的数组进行查找就无能为力了，所以这就引入了程序员需要具备的第四项能力: 代码要有足够的可扩展性

## 代码要有足够的可扩展性 ##

怎么让 bsearch 这个二分查找也支持 long 型或 short 型数组呢，Java 支持重载，再针对 bsearch 进行多个函数的重载是一种方式，不过会造成代码的大量冗余，所以另一种更合适的方式是利用 Java 语言中的泛型，于是我们的代码改造如下

public static <T extends Comparable> int bsearch(T[] a, int length, T value) throws Exception {
        if (length < 0) {
            // 实际应该抛出一个继承自Exception的异常，这里为了方便直接抛出Exception
            throw new Exception("数据长度不合法");
        }
        int low = 0;
        int high = length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid].compareTo(value) > 0) {
                if (mid == 0) {
                    return -1;
                }
                if (a[mid-1].compareTo(value) <= 0) {
                    return mid-1;
                } else {
                    high = mid-1;
                }
            }else {
                low = mid + 1;
            }
        }
        return -1;
    }

写成这样，可以说我们的代码具有足够的健壮性与可扩展性了。

## 总结 ##

本文通过一个常见的面试题来详细阐述了优秀程序员必须具备的四项核心能力：抽象问题，修改模型，写出健壮性，可扩展性的代码！

所以为什么面试中大厂喜欢考算法，主要是想详细地了解你是否具备解决此算法题背后的思想，即 **抽象问题** 的能力，面试官还喜欢对相应算法题进行各种变形，其实也是为了考察你是否具有 **修改模型** 的能力（比如一个翻转链表，可以引申出顺序每 k 个一组翻转，逆序每 k 个一组翻转），所以为了同时具备这两项能力，我们需要提前掌握大量的理论知识，做大量的刻意练习。

共勉！大家加油：）

**-----------------------**

**公众号：五分钟学算法****（ID：CXYxiaowu****）**

**博客：www.cxyxiaowu.com**

**知乎：程序员吴师兄**

**一个正在学习算法的人，致力于将算法讲清楚！**

长按下图二维码关注，和你一起领悟算法的魅力**。**

![format_png 4][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVFFbFczUFpDNDBHaG5NVmpVcVhhTlJPSWZ1TzB4MWFLY0hWVXNpYVBRQ1pwbHppY3lWSGh3YXdLeUsxU09KREwwaE5VSXoxTnF0MG5TZy82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9PeXdleXNDU2VMV1JpYjlEQ1ZJQnlyNkVGZFJIZnd3S2Y0bjgxdWJPMHdxRkY3UTdpY3l4aE42VjFLN05zN2hjVklOcDY4VHBLdUk1cmtGMmlhNnByS1VYZy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9PeXdleXNDU2VMV1JpYjlEQ1ZJQnlyNkVGZFJIZnd3S2Z0R3k3TW16aWN2WFAyOGM5enE1SENNVHdyZmVjemlhWjBrMngwTzJTQ3VuQTJuUTNGbUs2ZWlhT1EvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9ENjdwZWNlaWJlSVJnTjYxb1pBaWFiNHpKOE9SbG03ektWY2lhUTFGRFFkSHFpYXA5UjlmTWRVM29BWkxiNEwxWk50dnFzeFFLbGljVkxpY0d4ekZ2NFRmV3BtQS82NDA?x-oss-process=image/format,png