大约从2011年开始，一些比较大的IT公司开始在面试中加上技术/技能测试，比如Amazon，Facebook，等公司，这种现象所反映出的问题大概是对美国现有大学教育质量的一种不信任。从我的理解而言，大学应该是为社会培养并选拔人才的地方，当一个人完成了四年的学业之后，其所在的大学有义务对该学生进行一番客观的鉴定，对其才能和特长应该加以归类，评估，以便交给未来的用人单位，如此可以减少用雇佣时的失误。毕竟一个公司面试最多也就是6个小时左右，它比一个人化四年的时间读大学要少的多。但现在的美国大学除了赚钱就是赚钱，其社会功效与社会义务基本降低到零。这就促使用人单位不得不自己出考题，以考察应试者的技术水平，这对整个一个国家的教育体系而言，真是一个莫大的讽刺。下面就是一道Facebook的面试题，是通过Skpye对应试者进行测试的。如果你的小孩恰好在学计算机专业，不妨让他们也感受一下，这是一道什么样水平的题？

-----------------------------------

首先对26个英文字母进行如下的编码：

0-A, 1-B, 2-C, 3-D, 4-E, 5-F, 6-G, 7-H, 8-I, 9-J, 10-K,

11-L, 12-M,13-N, 14-O, 15-P, 16-Q, 17-R, 18-S, 19-T,

20-U, 21-V, 22-W, 23-X, 24-Y, 25-Z.

然后随便给你一个有限的数字串，举个例子：12320562345610，现在让你设计一个算法，计算一下，如果把这个数字串转化为英文字母串，能有多少种转化方法？

------------------------------------

解决这道题的关键是要想出一个能够遍历的方法。就拿上面的那串数字串来说，如果采用单数字编码，那么它可以转化为：BCDCAFGCDEFGBA.当然也可以采用一部分的双数字编码。但要遍历全部各种可能性，就要找到一种次序，沿着它可以找到全部的字母串。

------------------------------------

一个比较简单的办法是要把遍历的次序与自然数建立一个一一的对应关系，由于给定的数字串是由有限的数字所构成，因此可以设想，一旦建立起与自然数的某种对应关系之后，通过遍历自然数的一个子集，就可以找到它的全部字母串。如此就不会遗漏某个字母串。

自然数从0开始，即：0, 1, 2, 3, 4, ....; 然后把这个自然数用2进制表示，即：0, 1, 10, 11, 100, 101, ....;

然后构造一个像图灵机一样的自动机，它要把这些2进制数读进来，每次只读一个。比如说在开始的时候，第1次它读进来的数是0，然后按照0这个指令，对上述的数字串进行转化，把之转化为字母串，其指令规则如下，

0 = 0000000000...；每个0对应相应的数字串的位置，如果都是0，那自动机就把给定数值串按照一位进行转换，换句话说，就是每个数字转化为一个字母。如此得到第一个字母串。

1 = 100000000....; 自动机要把数字串最左端的两位数字合并在一起转化为一个字母，而其余的都是一位数字转化为一个字母。总结一下，其转换规则为：（2位）（1位）（1位）....

2 = 010000000...; 其转换规则为：(1位）（2位）（1位）（1位）....;

3 = 110000000,...;其转换规则为：（2位）（2位）（1位）（1位）,...;

4 = 001000000,...;其转换规则为：(1位）（1位）（2位）（1位），...;

5 = 101000000,...;其转换规则为：（2位）（1位）（2位）（1位）,...;

....

按照上述的次序，自动机每读进一个自然数，先把它化为2进制数，根据其相应的0与1的位置，对给定的数字串进行转换，如果那一位是0，就把单个数字转化为字母，如果那位是1，就把相应的2个数字转化为字母。如此得到遍历。

当然这里边还有个小问题：并不是任何两个数字的编码都有相应的字母向对应的，比方说，如果机器遇到像30这样的两位数，那它就无法转换为字母。为了解决这个问题，你可以设计一个计数变量，存储着到目前为止的全部转换成功的字母串的个数。如果遇到中间含有30这样的无效编码，自动机可以读下一个自然数，就把这个数给跳过去了，当然那个计数变量并没有改变，因为你读了一个无效的编码指令。

---------------------

上面的这种方法有一定的普遍性，比方说我给你一个汉字编码表如下：

0 - 啊

1 - 阿

2 - 呵

...;

一共给你3000个，然后随便给你一个数字串，让你把它转化为汉字串，问能有多少种转换方法？

这个问题涉及到：1位数字编码，2位数字编码，3位数字编码，和4位数字编码。因此，你要把自然数先转化为4进制数，那么整个自然数就是由0，1，2，3所组成，当自动机读进一个自然数并把它转化为一个4进制数以后，然后把这个4进制数当成一个指令串，遇到0，就取1位编码，遇到1就取2位编码，遇到2就去3位编码，以此类推，这样可以覆盖整个可能转换的汉字串。