东营php法式员技巧_从一个面试题意见式员的几项基本功

序言

一个精良的程序员具备挺多特质的，比如好奇心，学习能力等，但在我看来一个精良的程序员必须具备几项核心能力，哪几项，先卖个关子，程序员最喜好说的话是「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 所在的省市呢?

如图示：在百度上输入一个 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，让对方猜，若何猜才能猜最快。

统共只猜了 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 个一组翻转），所以为了同时具备这两项能力，我们须要提前节制大量的理论知识，做大量的刻意练习。

共勉！
大家加油：）