今天先出一道题目，感受一下ai入门试题的style：
下面这个被污损的二维码中，存储的信息是：
有结题思路了么？别着急，考试才刚刚开始。。
▌思路清奇的笔试题？
2018 年，创新工场ai工程院举办的 deecamp 人工智能训练营打算培养 300 名大学生。这是 deecamp 的第二期。报名异常踊跃，全球近 7000 名学生申请。
6 月 8 日和 9 日两天，报名的同学接受了在线笔试。笔试还没结束就出现了各种热闹事儿。比如，有的同学想通过运行考题中的代码来寻找答案，没想到，简单的几行代码很快耗尽了电脑资源，有的电脑竟直接崩溃！笔试结束，微信群里热闹非常。同学们兴致勃勃地讨论笔试题目。有的题目，大家讨论了几小时还热情不减。有同学连连感叹，这题目真是思路清奇！
什么样的在线笔试题，才能让电脑崩溃，才能给人留下思路清奇的印象呢？
为了让帮助参试同学更好地做答，同时供对ai感兴趣的同学学习， 创新工场ai工程院副院长王咏刚在本文写下了deecamp 在线笔试的设计思路。
▌设计 ai 入门级开卷笔试题的挑战
设计在线笔试题，本来就难。设计 deecamp 的在线笔试题，尤其有挑战。
在线笔试本身就是半开卷的性质。想要所有同学都严格遵守闭卷规定，极难。好多公司为了防止所谓在线笔试“作弊”，尝试过各种好玩的招数，比如要求开着摄像头答题，其实大多是掩耳盗铃。真正好的在线笔试题，应该是即便开卷，答题者也需要动脑筋思考的题目。
记得以前 google 使用的在线笔试题，大多是偏重算法的题目，可以看做是简化版的 acm。这的确是一种设计开卷笔试题的思路，因为很多经典算法问题，都可以被包装到一个很具体的场景中。学生考试时，即便用搜索引擎去查找这个具体场景，只要以前没考过类似的题目，就很难搜到正确答案。最起码，学生需要有一定的算法知识，能够将遇到的问题抽象成特定的算法模式，然后再去搜索对应的解决方案。
但是，回到 deecamp，如果按照简化版 acm 的思路，就不能满足要求了。因为 deecamp 希望招聘的学生标准与 google 要招聘的学生标准有很大不同。google 是一家公司，想招进来的是最聪明的、编程能力和算法能力最强的学生。deecamp 是一个训练营，本来就是以培训为目的，当然不能把入门考试的要求设得太高。
deecamp 想招进来的是这样的学生：聪明、知识面广、动手能力强、有不错的数学和编程基础，了解机器学习特别是深度学习的基本概念。因为 deecamp 强调ai人才培养，入门考试当然不会要求每个学生都能熟练掌握 cnn、rnn 之类的网络细节，或者特别擅长解决算法难题。
也就是说，我们创新工场 ai 工程院这个命题小组，要设计的是一套 ai 入门级的开卷笔试题，无论是数学、编程、算法还是 ai，都只适合考察最基本的知识技能，而不适合强调题目的专深。同时，这套题还需要在题目的趣味性、灵活度等方面下功夫，最好有一些平常很少见到的新场景，以考察同学们在解决新问题时的实战技能。更重要的，这些题目需要在学生开卷答题的情况下，还能有足够的区分度。
各种要求的叠加下，并没有完美的解决方案。既不能完美防作弊，也没法在难度、知识点、趣味性等方面达到完美均衡。我们这个命题小组只是尽力而为。
https://challenger.ai
▌如何考察基本概念？
考察基本概念的题目都是送分题，但送分也不能太直接、太坦白。也就是说，对那些没学好基本概念的同学，开卷考试时，好歹也要让他们在搜索引擎里费些周折，不能太直接查到答案。比如下面这道原题：
下面有关计算机基本原理的说法中，正确的一项是：
(a) 堆栈（stack）在内存中总是由高地址向低地址方向增长的。(b) 发生函数调用时，函数的参数总是通过压入堆栈（stack）的方式来传递的。(c) 在 64 位计算机上，python3 代码中的 int 类型可以表示的最大数值是 2^64-1。(d) 在任何计算机上，python3 代码中的 float 类型都没有办法直接表示 [0,1] 区间内的所有实数。
每个选项，都涉及计算机基本原理或编程语言的某种基本知识。如果没学好计算机原理，或没掌握程序设计的一些本质问题，即便开卷，大概也很难搞清楚该如何用搜索引擎快速查找答案吧。
另外，既然是开卷，选项（c）和选项（d）就没有回避 python3 这样的具体编程语言的具体版本。因为即便不懂 python 编程，也至少能搜索到，python3 里面的整数类型取值范围是什么。或者，对于选项（d），只要从编程语言的本质出发，明白计算机里的浮点类型只是一种用离散方式近似表达实数区间的方法，就可以知道，python 里的 float 是不可能涵盖 [0,1] 区间内的所有实数的。
类似的，有关深度学习基本概念和基本框架的选择题是这个样子的：
有关深度神经网络的训练（training）和推断（inference），以下说法中不正确的是：(a) 将数据分组部署在不同 gpu 上进行训练能提高深度神经网络的训练速度。(b) tensorflow 使用 gpu 训练好的模型，在执行推断任务时，也必须在 gpu 上运行。(c) 将模型中的浮点数精度降低，例如使用 float16 代替 float32，可以压缩训练好的模型的大小。(d) gpu 所配置的显存的大小，对于在该 gpu 上训练的深度神经网络的复杂度、训练数据的批次规模等，都是一个无法忽视的影响因素。
总结起来，这次笔试里的基本概念题，大概涵盖了以下几个方面的基本知识：
1、基本数学知识，比如函数和矩阵运算。
2、计算机原理和编程基础知识，比如堆栈、数据类型。
3、机器学习的基础知识，比如 precision 和 recall。
4、深度学习的基础知识，比如表示学习的概念。
5、tensorflow 的基本概念，比如 variable 和 placeholder 的区别。
补充一下，有同学问到，概念题里，有一个有关 tensorflow 的题目，提到了 tensorflow 的符号执行（symbolic execution）和计算图优化（computational graph optimization），相关的参考资料到底在那里？
其实，tensorflow 白皮书里，“5.1 common subexpression elimination”就是关于计算图优化的一个举例说明。有关符号执行对于计算图优化的作用，mxnet 文档里有一篇特别浅显的讲解：programming models for deep learning。其中对流行的框架做了一个归类：“examples of imperative style deep learning libraries include torch, chainer and minerva. while the examples of symbolic style deep learning libraries include theano, cgt and tensorflow.”
▌如何考察 ai 相关的数学知识？
比如，卷积是深度学习常用的数学知识，一些熟悉 cnn 的同学可能没有仔细想过卷积的数学含义到底是什么？卷积在 cnn 中常以二维数学形式出现，那么，卷积的n维表达式是什么？一维卷积又是如何计算的？cnn 中的卷积，和语音信号处理中的卷积，数字图像处理中的卷积，是如何联系在一起的？
知乎有一个很好的问题，“如何通俗易懂地解释卷积？”这个问题下面，有好几个特别有趣的答案，大家可以参考。
zhihu/question/22298352
当然，实际笔试题里，关于卷积的问题特别简单：
一维离散卷积的定义是 给定一维数组 a = [1, 2, 3], v = [4, 5, 6]，它们的离散卷积结果是？
熟悉卷积计算的同学，可以很快写出答案。因为是开卷，就算搞不清这么简单的公式，如果能想起来手头有很多现成的工具可用，比如用 numpy 的卷积计算函数实际算一下
numpy.convolve(a, v)
这种愿意学习、勤于动手的学生也很不错！
类似的，真题中，还有一些结合机器学习或深度学习的场景，但其实只是做一个数学运算的题目，比如这一题：
给定词典 [a, b, c, d, e]，基于这个五单词词典的三个文档（document）内容如下：
doca: [a, b, b, d, d]docb: [b, b, b, e, e, e, d]docc: [d, d, b, b, e]
如果使用 bag-of-words model 将每个文档表示成五维的向量，例如，doca 可以被表示为 {a:1, b:2, c:0, d:2, e:0}。基于这三个五维向量，计算两两之间的余弦相似性（cosine similarity），最相似的两个向量是？
这个题目，对很多没有太多自然语言处理（nlp）经验的同学来说，最难的主要是理解题目中bag-of-words model、cosine similarity 之类的基本概念。但因为是开卷，学习能力强的同学应该能快速查到这些概念的基本定义，然后根据 cosine similarity 的公式，写几行代码，算出结果。善于偷懒的同学，其实也不难查到，像 sklearn.metrics.pairwise 包中的 cosine_similarity 函数，其实都是可以直接拿过来用的。
▌到底是什么题让电脑崩溃？
一般开卷在线笔试，是很难设计那种根据代码写出运行结果的题目的，因为参加考试的同学只要在电脑上运行一遍程序，就知道结果了。
我们命题组偏偏不信邪，设计出了几道编程和数学结合的题目，不仅给出代码，还无法通过直接执行得到答案。
比如说，其中一道题是这样的：
假设可以不考虑计算机运行资源（如内存）的限制，以下 python3 代码的预期运行结果是：
importmathdefsieve(size):sieve=[true]*sizesieve[0]=falsesieve[1]=falseforiinrange(2,int(math.sqrt(size))+1):k=i*2whilek
所以，遇到这种题是不能硬来的。做题的学生还是要回过头来，读代码，理解代码的含义。
这个代码的函数名sieve其实暗示了代码的功用，sieve of eratosthenes，这是用筛法计算质数个数的一个经典方法。当然，不知道筛法这个词也不重要，重要的是要从代码逻辑里，读懂最关键的几行其实是在把所有非质数都筛掉。就算读起来费劲，那么，至少能想到，把最后一行改成比较小的输入数字，比如 10，比如 100，比如 1000，运行一下试试吧。
这段代码的功能很明显：求 10,000,000,000 以内质数的个数。至于 10,000,000,000 以内质数的个数到底有多少，这个容易，搜索一下不就知道了？当然了，数学不好，或者不善于信息检索的同学，这个搜索估计也要费不少时间。
这种根据代码写运行结果，又可以开卷考试的命题思路，其实还有不少。比如实际考题里的另一个例子，是在用类似蒙特卡洛方法的思路，让计算机不断生成随机数，然后去暴力统计随机坐标落在平面上不同图形区域的计数比例，以逼近图形区域的面积或面积占比。真题如下：
下面的 python3 函数，如果输入的参数 n 非常大，函数的返回值会趋近于以下哪一个值（选项中的值用 python 表达式来表示）？
importrandomdeffoo(n):random.seed()c1=0c2=0foriinrange(n):x=random.random()y=random.random()r1=x*x+y*yr2=(1-x)*(1-x)+(1-y)*(1-y)ifr1<=1andr2<=1:c1+=1else:c2+=1returnc1/c2(a) 4 / 3(b) (math.pi - 2) / (4 - math.pi)(c) math.e ** (6 / 21)(d) math.tan(53 / 180 * math.pi)
这个题目，要计算面积比值的图形区域极其简单，只要搞懂了代码的基本思路，就不难把这个问题转化成一个毫无压力的初中几何题了。
▌算法题都不算难
这套卷子中，算法题的难度不大，但形式上会追求新颖，以便考察学生应对新问题的能力。比如下面这样的题目：
有一个画图用的函数库，提供三个 api 接口：
set_color(color) #设置画笔颜色。初始画笔颜色为黑色。move_to(x, y) # 移动画笔到给定的坐标。初始坐标为(0,0)。line_to(x, y) # 在画笔的当前位置到给定的终点坐标之间画一条线段。已知每调用 set_color 函数一次，要支付 3 元；每调用 move_to 函数一次，要支付 2 元；调用 line_to 函数免费。请问，要从初始状态开始，用这个函数库画出下图，最少支付多少钱就可以完成？（图中，左侧红绿蓝三条线段相互连接，右侧红绿蓝三条线段相互分离）
这个问题当然可以抽象成一个变形的最短路径问题，但显然没有那么复杂。思路缜密、清晰的同学在头脑中设计一条最佳路径，其实也不算困难。如果只在脑子里，或者只用纸笔想不清楚，那么，选择直接编程解决的方案也很容易。因为搜索空间不大，编程可以轻易穷举六条线段全排列的所有可能性，从里面找到最小的 cost 即可。
▌有趣的图灵奖得主问题
实际笔试中，一道大题是这么设计的（篇幅原因，下面题目中的字符串不完整，不能用于实际解题，只是一个示意）：
有一张图灵奖得主的肖像照片，被一个学生用简单的异或加密方法，编码成了如下这样的字符串：
mg4rzijpimkvaixplgwrbjrxn3mxdzn3m3s……（篇幅原因，此处省略若干字符）
已知肖像照片是 64x64 像素的 0~255 级灰度图片，内存中用 raw bitmap 方式，每个像素用一个字节存储。对肖像照片的原始数据，学生使用的加密代码片段如下（python3 代码，代码中的 key 值是未知的加密密钥）：
_key_len = 2bitmap = pil.image.open(image_path).tobytes()encrypted = []for index, byte in enumerate(bitmap): encrypted.append(byte ^ key[index % _key_len...