第2章

数字之魅

——数字中的技巧

面试是双方平等交流的过程，有时候分不清谁在面试谁。

这一章收集了一些好玩的对数字以及数组进行处理的题目。编程的过程实际上就是和数字打交道的过程。很多庞大的应用，例如搜索引擎查询并返回搜索结果的过程，就可以看作是对众多数组和数组中大量的数字（如：Page Rank，Page Id）进行计算、比较的过程。我们一方面不断地说要处理“海量数据”，另一方面同学们在程序课上定义数组的时候会写int array[10]，int array[100]往往就觉得“技止此耳”，“我掌握了”！如果数组的元素个数是百万、千万级，你的算法还有效率么？

有些题目看似简单，但是我们在面试中发现，有很多应聘者不能正确地写出“冒泡排序”或“二分查找”，所以还是要从简单的题目出发。能不能把简单的问题完完全全地解决，没有任何bug？

有读者会问——

那这些题目我都背好了，再来面试，行么？

当然行。比如“求数组的子数组之和的最大值”（见正文之“2.14”节）这道题目，正确的解法只有不到10行代码。你当然可以背好了再来面试。不过面试者肯定会问一些扩展问题，像“如果数组首尾相连，怎么办”，“如果要求数组的子数组乘积的最大值”等。不能举一反三的同学，可能会比较难过。你只有真正掌握了这些内容，才能应付自如。