搜狗校招顺序随机整数编码

2014年8月24日 11:42

要准备找工作了,这几天在看july整理的面试题目,很全很强大。其中有个搜狗校招的笔试题目,觉得很有意思。思考了下,感觉相比给出的方法还有更好的方法。

题目

N个整数(数的大小为0-255)的序列,把它们加密为K个整数(数的大小为0-255).再将K个整数顺序随机打乱,使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法,且要求K<=15*N. 如果是:

1. N<=16,要求K<=16*N.
2. N<=16,要求K<=10*N.
3. N<=64,要求K<=15*N

第1、2问

因为N条件相同,所以第1问和第2问其实是同一个问题,解决了第2问也就搞定了第1问。

简单方法

原理

应题目要求,加密后的K个整数打乱顺序后还要能恢复原文,那么就需要将原文整数的位置信息也编码进密文。

一种简单的方法就是把密文的8位数分成3段

第1部分编码位置,N<=16的情况需要4位来表示
第2部分编码整数的第几位,000表示第0位,111表示第7位
第3部分编码某一位上的数值,如:0110 101 1表示,第6个数的第5位为1

原文整数范围[0-255]有8位,因此编码1个原文数字需要8个密文整数,即 K<=8N。已经可以满足第1、2问的要求了。

栗子

假设原文第6个整数为77,二进制表示为 01001101,那么可以编码成

0110 111 0
0110 110 1
0110 101 0
0110 100 0
0110 011 1
0110 010 1
0110 001 0
0110 000 1

好一点的方法

原理

这里我想到了一种更好一点的方法,可以使 K<=4N

首先,我们将原文整数写成4进制:x = a3 * 64 + a2 * 16 + a1 * 4 + a0(也就是将原文整数分为4段,每段2位),记系数为ai。由于i属于{0, 1, 2, 3}并且ai也属于{0, 1, 2, 3},因此我们考虑用2位编码i,2位编码ai。于是密文的数字就被分为了这么三段

第1部分依然编码位置
第2部分编码i
第3部分编码ai

这样只需要4个密文整数就可以编码一个原文整数了,即 K<=4N

栗子

假设原文第6个数字为77,二进制表示为 01001101,那么可以编码成

0110 11 01
0110 10 00
0110 01 11
0110 00 01

第三问

好一点的方法

原理

由于N<=64这样就必须用6位来编码位置,剩下只有2位来编码数值了。

继承第1、2问好一点的方法,我们用剩下的2位编码i,用出现的次数编码 ai。也就是ai等于多少对应的密文整数就出现多少次。由于i有4个,ai<=3,故每一个原文整数最多需要4*3=12个密文整数来编码,也就是 K<=12N

栗子

假设原文第6个数字为77,二进制表示为 01001101,那么可以编码成

000110 11
000110 01
000110 01
000110 01
000110 00

更好一点的方法

原理

假设每1个原文整数最多能使用 n 个密文整数来编码。

对于1个密文数字依然需要6位来编码位置,剩下2位来编码数值信息。2位对应4个状态(00, 01, 10, 11)。n 个密文整数分给4个状态,状态出现的次数可以位0,并且n可以不用完。相当于5个状态分n个整数,最后一个状态表示没有用完的整数。则一共有C(n+4, 4)种组合方式。

我们用1种组合方式编码1个数值,[0-255]共有256个数值。那么要求满足 C(n+4, 4) >= 256。求的当n=7时,C(n+4,4)=330 > 256。故这种编码方式可以使得 K<=7N。状态对应的表格在这里下载

栗子

假设原文第6个数字为77,二进制表示为 01001101,那么可以编码成

000110 10
000110 10
000110 01
000110 01
000110 00
000110 00