工程师的面试与黎曼猜想

关于黎曼猜想的话题,最近真的很红。好多文章真是又臭又长,云里雾里看它半小时都不到正题。倒底黎曼猜想是啥,还没看到有能说清楚的。

面试工程师,是团队建立初期要做的最重要的事情。我在做技术面试时,是会请面试人当场在白板上手写代码作为考题(whiteboard coding interview)。如果是远程不方便用白板,也会通过 https://codepad.remoteinterview.io/ 或者 Skype 共享屏幕来进行面试。

我会提出一个简单的算法题,不是对类库和方法的记忆力比赛,而是看解决问题的思路和能力。然后请面试的童鞋在白板上用自己擅长的语言作答,甚至伪码也可以。

真实世界中,我是不会用黎曼ζ函数这么复杂的公式做面试问题。但是一直想聊聊手写代码面试这个话题。所以,在这篇文章中,我打算一边解释黎曼ζ函数和黎曼猜想,一边说说手写代码面试。

whiteboard-coding-interview.png


黎曼ζ函数(简单版)

黎曼ζ函数是黎曼猜想的背景。先说说 ζ 这个发音是 zeta ,所以正确的读法是:黎曼zei(贼)ta(塔)函数(Riemann zeta function)。

黎曼ζ函数,又写为 ζ(s)。先看面试第一题:

我们知道当 s > 1 , 1 < n < ∞ 时,黎曼ζ函数定义为下面的公式:

zeta-1.png

写一段代码,打印出 s = 2, 3, 4, 5 …. 10, n = 1000 的,所有 ζ(s) 的结果。

作为参考,我会告诉面试者,幂计算在该语言中的写法,比如 nodejs 中是 Math.pow(x, y)。

关于手写代码

不考虑本来黎曼ζ函数还能涵盖的负数和复数领域,前面这公式并不难。手写代码题只是为了观察工程师几个基本素质:

1. 能不能写代码

不要怀疑,有不少面试者真的是无法按题目的意思写代码。

2. 会不会硬来(brute force)

硬来(brute force) 在我看是加分项。工程师首先要解决问题,过渡思考数学算法却没有能解决问题,是无效思考。

3. 能不能让代码输出正确的结果

肯定要给面试者充足的检查时间。但是我还是常常惊讶于,只有如此少的人能写出能输出正确结果的代码。

4. 代码风格

面试当场手写代码是有心理压力的,但也更容易展现出第一反应下的代码书写风格习惯。没有IDE或者自动处理的帮助时,如果还能保持整齐的缩进风格,变量名走心,代码整齐,足以说明这是一个对代码质量有追求的人。

5. 能不能清楚地讲述自己的逻辑思路

在完成代码之后,我会请面试者逐行解释自己的代码。拥有技术沟通能力在团队合作中会有极大的加成。

6. 代码可读性

如果有习惯对代码结构进行拆解,降低代码复杂度,达到更高的可读性。也是重要的加分项。

黎曼ζ函数的代码与解读

在 s > 1 区间域的黎曼ζ函数,10行左右代码就可以了。例如:

function zeta(s, n) {
    var sum = 0;
    for (var i = 1; i <= n; i++) {
        sum += 1/(Math.pow(i, s));
    }
    return sum;
}
 
function main() {
   for (var i = 2; i <= 10; i++) {
        console.log(`zeta(${i}) = ` + zeta(i, 1000));
   }
}
 
main();

将 zeta 单独封装成一个函数,而不是像下面两个 for 循环向下面这样的写法,就是前面说的对代码结构进行拆解,来降低代码复杂度,以达到更高的可读性。

for (var i = 2; i <= 10; i++) {
    // 下面这样的写法虽然更短,但是可读性更差,
    // 增加别人看懂代码的难度,是扣分的
    var sum = 0;
    for (var j = 1; j <= 1000; j++) {
        sum += 1/(Math.pow(j, i));
    }
    
    console.log(`zeta(${i}) = ${sum}`);
}

正确的输出结果应该是:

zeta(2) = 1.6439345666815615
zeta(3) = 1.2020564036593433
zeta(4) = 1.082323233378306
zeta(5) = 1.0369277551431222
zeta(6) = 1.017343061984441
zeta(7) = 1.0083492773819207
zeta(8) = 1.004077356197943
zeta(9) = 1.0020083928260817
zeta(10) = 1.0009945751278182

黎曼ζ函数(完整高难版)

黎曼ζ函数的参数 s,可以是复数,也就是说可以是实数加虚数。如果我们将 s 的实数部分简写为 Re(s) 。当 Re(s) > 1 时,也就是参数 s 的实数部分大于1时,黎曼ζ函数还是前面那个简单版本。

当黎曼ζ函数延展到 Re(s) < 0 负数领域中,表达就不同了:

zeta-2.png

其中 Γ 读为 Gamma (伽玛函数),是一种支持复数(实数加虚数)的阶乘。

当 0 < Re(s) < 1 时,表达又不同:

zeta-3.png

三个公式分别有各自的作用域,组合起来就是完整形态的黎曼ζ函数。至于说为什么 s < 1 时黎曼ζ函数突然就像变形金刚一样的展开了,这是以一种叫 Analytic continuation 的技巧得来的唯一优雅解法。这里我推荐一个 Visualizing the Riemann hypothesis and analytic continuation 的视频解说。

黎曼猜想的代码表达

题目:写一段代码,n 为 1000,分别计算 s = -1, -2, 1/2+14.1347i, -3 的结果。这里的 i 是虚数 (Imaginary number)。

题目会附带提示可以操作复数的完整数学函数 math.js | an extensive math library for JavaScript and Node.js 的方法文档做参考。

将前面的公式代码化:

const math = require('mathjs');

function zetaComplex(s, n) {
    if (math.re(s) > 1) {
        var sum = math.complex(0,0);
        for (var i = 1; i <= n; i++) {
            sum = math.add(sum, math.divide(1, math.pow(i, s)));
        }
        return sum;
    } else if (math.re(s) > 0) {
        var sum = math.complex(0,0);
        for (var i = 1; i <= n; i++) {
            sum = math.add(sum, math.divide(math.pow(-1, i+1), math.pow(i, s)));
        }
        return math.prod(math.divide(1, math.subtract(1, math.pow(2, math.subtract(1, s)))), sum);
    } else {
        return math.pow(2, s) * math.pow(math.PI, math.subtract(s, 1))
        * math.sin( math.divide(math.PI * s, 2)) * math.gamma(math.subtract(1, s)) 
        * zetaComplex(math.subtract(1, s), n);
    }
}

var input = [-1, -2, math.complex(1/2, 14.1347), -3];

input.forEach(function(el) {
    console.log(`zeta(${el}) = ` + zetaComplex(el, 1000));
});

ζ(-1) 应该等于 -1/12,先人已经算好。

ζ(-2) 就是黎曼ζ函数中常说的负偶数,结果应该等于 0。

ζ(1/2+14.1347i) 就是黎曼猜想的部分:除了参数s为负偶数的情形外,令ζ函数结果为0的参数s的实数部分必然是 1/2。

ζ(-3) 应该等于 -1/120。

为了更直白的解释,代码精度有限,所以输出结果是近似值,大约是:

zeta(-1) = -0.08328269806336473
zeta(-2) = -2.3738653665425513e-18
zeta(0.5 + 14.1347i) = 0.00665796802251104 - 0.00027328853234271006i
zeta(-3) = 0.008333333330770697


杂记

面试时以黎曼猜想为题是不人道的。所以真实的情况中,我的面试题会简单的多得多。但会是一道和数学有关,和记忆类库或方法无关的题目。

如果面试者确实能做出正确的结果,我还会请面试者尝试优化一下代码的性能。一个优秀的程序员应该是非常关注性能优化的。这里我会希望看到面试者对计算开销的理解:是不是对性能优化的方向有思路,有没有寻找代码中被执行次数最多的计算,是否尝试去减少它的使用次数,能够倍数级甚至呈指数级的减少性能开销。


有好奇心。有责任心。能解决问题。就是个好工程师。

能够不断的突破自我,会不断的优化自己所做的事情,寻找更好的解决方案。就是个优秀的工程师。

更多参考:

Riemann zeta function - Wikipedia

Gamma function - Wikipedia

Visualizing the Riemann hypothesis and analytic continuation - YouTube