一道程序猿面试题目, 大家来看看?

[tl3shi]

原文在此 看看 V 站的开发者对此问题怎么看.

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

double sqrt(int v, double t)

要求:

1. 不能调用系统库函数, 诸如 Math.sqrt(v) 之类的;
2. 假设计算出的结果为 r, 要求满足如下条件 (防止图片有问题留下 $|r - \sqrt v| \leq t $), 其中, ($\sqrt v$) 是真实的值, t 为给定的一个误差, 例如0.1等, 即你计算出的值r 要在给定的误差范围内.
3. 实现语言不限, 你条件可以比上述更加苛刻, 但不能宽松, 举例而言, 我调用你的接口 sqrt(9, 0.21) 返回值属于 [2.79, 3.21] 这个区间的任意一个都满足条件.

其实你可以 拿出笔和纸, 尝试解答一下 强调一下, 一定要注意给定的误差条件, 欢迎沟通交流.

原文点我 是在微信上搞了一个投票调查(求投票), 微信公众号里的阅读原文是一个对该问题在面试过程中的模拟.

[msg7086]

上面的解法好像改变了精度了。

按照原题要求的精度来的话，牛顿迭代和二分法的 Ruby 实现：
test = ->(sq, t, rt) { (rt+t) * (rt+t) < sq || (rt-t) * (rt-t) > sq }
sqrt1 = ->(sq, t) { rt = sq * 1.0; rt = (rt + sq / rt) / 2 while test.call(sq, t, rt); rt }
sqrt2 = ->(sq, t) { (0..sq.to_f).bsearch { |rt| test.call(sq, t, rt) ? sq - rt * rt : 0 } }

sqrt1.call(9, 0.21)
# => 3.023529411764706
sqrt1.call(9, 0.0001)
# => 3.00009155413138

sqrt2.call(9, 0.21)
# => 2.993255615234375
sqrt2.call(9, 0.0001)
# => 2.9999834150075912

[q397064399]

如果让我面试做这种狗屎题，我心里肯定会说，
你这套路不对，这题我平时刷的时候没怎么见过，
面试时间一般也就 20 分钟-1 小时
这还要人编写正确的程序出来，还不给上网查资料，
这么简单的题目，写错了就没分，我操，面试官 傻逼 脑残 负分 滚出
为什么说这题简单呢？因为这题 一看就是烂大街的题目 我要是做不出来 不就负分了么
（虽然我能把二分整数搜索的算法记忆的滚瓜烂熟）

[kingdaa]

public static double sqrt(int v, double t) {
assert (v > 0 && t > 0);
double lo = 0.0, hi = v * 1.0;
while (lo < hi) {
double mid = lo + (hi - lo) / 2;
double midSq = mid * mid;
double diff = (midSq - v) >= 0 ? (midSq - v) : (v - midSq);
if (diff <= t)
return mid;
if (midSq > v)
hi = mid;
else
lo = mid;
}
return -1.0;
}

[q397064399]

现在让我来说为什么这题是狗屎题了吧

让我解的话，只能想到一种办法 ，那就是根据 t 的精度进行 暴力搜索
每次只加 0.0000001 （假设） 直到 条件不满足的时候，那么前一个解 必然是在区间范围内的

这样一来，想到什么了没有，被我们暴力搜索的候选结果集 是一个等差数列
既然是等差数列，那么就是有序候选集，搜索有序结果集 必然采用我大 二分搜索法 能大大降低算法复杂度

关键是你 TM 的这公式，让我根本想不出这 二分搜索 递归结束的条件啊
（我们平常用二分搜索 都是搜索 整数 递归的结束条件 比较简单 ）

所以呢？

面试的时候，如果面试者讲暴力搜索，面试官心里面会想 这么暴力？连二分都不会

面试者心里想，什么狗屎题，老子也知道这题二分是能解的，但是你这破公式，我就是想不出 一个递归检索的条件

[q397064399]

@kingdaa
你这错了 我瞄一眼 就知道你这错了，
面试你这样写 直接负分滚出，题意都没看懂

[q397064399]

所以这题在没有其他数学功底等套路的情况下，
最多只能想到二分搜索，但是这题 难点并不在二分搜索本身，而在于从公式中(ﾉ*･ω･)ﾉ推导出结束条件，
结束条件，刷过这个题的人，肯定会心一笑，正好踩到面试官的点
没刷过这个题的人，心里就骂娘了

[q397064399]

如果你真要考察 对二分搜索的应用能力，我建议出一个题目
讲一个故事 需要应用到 3sum ，要求算法复杂度低于 O(n3) ，即可
你这题目，面试者很难 get 到结束条件

[nagato]

这题解法太多了，之前网上看到过一篇文章，对比了 13 种不同的解法

[Cbdy]

方法很多，最常见就是牛顿迭代法。收敛比较快

[Death]

出题人有数值分析的基础吗？……

[misaka19000]

```lisp
;Newton's method 二次开方
(define (sqrt x)
(define (sqrt-iter guess x)
(cond ((< (abs (- x (* guess guess))) 0.001 ) guess)
(else (sqrt-iter (improve guess x) x))
))
(define (improve guess x)
(/ (+ guess (/ x guess)) 2))
(define (abs x)
(if (< x 0)
(- x)
x))
(sqrt-iter 1.0 x))

(sqrt 4)
```

[Cabana]

还记得以前看过一个开平方的神奇常数，用一个常数值作为起始猜值进行迭代，收敛会特别快

[tl3shi]

我想强调的不是说这道题目本身 而是说当有人给你一种思路后、能否在一步一步引导情况下思考并解决问题，最后能否将已经明白的思路变成实实在在的 code ，这肯定是较好的程序员应该具备的能力。

二分就是期待的答案，然而事实上就是并没有多少人写出。 结束条件就是一个坑给刷过这道题的人埋的，没刷过的人期望是经过提示后能写出二分。

楼上的代码貌似有不少是满足不了题意的

[ytmsdy]

想到了当年 POJ 上面的一道打表题。。

[Cbdy]

@Cabana 是 0x5f375a86

贴一段神奇的代码，据说比编译器的开方函数还快 5 倍
```
float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f375a86- (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f-xhalf*x*x); // Newton step, repeating increases accuracy
return x;
}
```

[elvodn]

没有用到系统库函数啊 ：）
```
double h_sqrt(int v, double t) {
double vd = (double)v;
double sqrt;
asm ("sqrtsd %1, %0"
: "=x" (sqrt)
: "xm" (vd));
return sqrt;
}
```

[metowolf]

牛顿迭代法，没有查资料写的
https://gist.github.com/metowolf/859e9d1b116b55c553c828ff1b99bd3e

[necomancer]

我想到平方根倒数快速算法，基于牛顿法，是雷神 3 里的一段代码，有对应 64 位的魔法数，也有误差分析，最后取倒数行不？

https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95

[pumpkin]

计算机程序的构造和解释中有非常详细的分析，由牛顿迭代法到最后抽象出的不动点搜寻，可以解决许多问题，比如求方程的根，求 PI 的值这种类型。

[xumaoxing]

def simple_sqrt(v, t):
if v < 0:
raise ValueError('domain error')

if v == 0:
return 0

# binary search
if v < 1:
left, right = v, 1
else:
left, right = 0, v
while True:
mid = (left + right) / 2.0
dest = mid * mid
diff = dest - v

if diff > 0 and (mid - t) * (mid - t) <= v:
return mid
if diff < 0 and (mid + t) * (mid + t) >= v:
return mid
if diff == 0:
return mid

if diff > 0:
right = mid
else:
left = mid