数美科技研发笔试题
请选择尽可能高效的算法，算法复杂度（大O表示法）比最优解高的话，得一半分。
前三题答案（拿到offer）
题目一.文件input.txt是一个文本文件，每一行有多列（用空格分隔）。keyword.conf是一个关键词配置文件，每一行是一个词。请找出文件input.txt中第一列包含keyword.conf中任意一个关键词的文本行并输出。（25）
示例
输入：
文件input.txt内容：
abc xxx
bcd xxx
def xxx
xyz xxx
文件keyword.conf内容：
bc
eft
输出（打印到标准输出）：
abc xxx
bcd xxx
题目二****. input.txt中有10万个随机整数，每行一个，范围从0-99999，需要分别统计[0-99]、[100-199]、[200-299]、[300-399] …… [99900, 99999]，出现的次数。输出为每个范围及其中数字出现的次数，范围和数字间空格分隔，每行一个。（20）
示例：
输入文件input.txt:
123
12
5
123
…
输出（打印到标准输出）：
0-99 26
100-199 128
200-299 3
题目三****. 在对域名进行分析中，常常会碰到“主域归属”问题。首先，我们有一个主域列表，如下所示：
*.sports.sina.com.cn
*.sina.com.cn
*.baidu.com
*.tencent.com
*.com
*.cn
等等，这个列表可能会包含百万级别的配置。
在有这个配置的前提下，给定一个域名，比如roll.sports.sina.com.cn，希望能够找到它所匹配的最长的“主域”，比如，对于上面这个域名，应该匹配到*.sports.这个主域。
请实现一个程序，从配置文件domain.txt读取主域列表，每行一个；从标准输入读取需要匹配的域名，每行一个；向标准输出打印：需要匹配的域名\t它匹配到的最长主域。注意，请尽可能高效，使用正则匹配会非常慢。
题目四****.给定如下设备数据文件input.txt，其中每行一条记录，空格分隔。一行记录包含3个字段：设备ID、连接的wifimac、时间戳。输入文件是一个设备一段时间范围内连接过的wifimac的列表（设备ID都一样），请计算每个设备连接过的wifimac的熵。
熵的计算方法：对于一个长度为n的序列xs，它包含m+1中不同的取值，s0, s1, …, sm，这些取值对应的出现概率分别是p0, p1, …,pm，则这个序列的熵为H(X) = -(p0log2(p0) + p1log2(p1) + … + pm*log2(pm)). 其中，某个取值出现的概率p的计算方法为：这个取值出现的次数 除以 长度n。
示例：
输入input.txt：
deviceId1 wifimac1 t1
deviceId1 wifimac2 t2
deviceId1 wifimac3 t3
deviceId1 wifimac3 t4
输出:
devicId1, 1.5
熵的计算过程：
deviceId1活跃4次，
wifimac1 出现1次 wifimac1 概率：0.25
wifimac2 出现1次wifimac2 概率：0.25
wifimac3 出现2次 wifimac3 概率：0.5
deviceId1下wifimac熵值：-0.25log2(0.25)- 0.25log2(0.25)- 0.5*log2(0.5)
题目五****. 输入两个JSON对象，第二个JSON对象是第一个JSON对象的类型描述（schema），请写代码检查第一个对象（数据对象）是否满足第二个对象定义的类型要求。例如，
对于JSON对象：
{
“organization”:”shumei”,
“type”: “tech”,
“features”:{
“timestamp”: 1558031759,
“cities”:[“BeiJing”,”ShangHai”，“ShenZhen”],
“apps”:[{“name”:”TianWang”, “date”:”2018-01”},
{“name”:”TianJing”, “date”:”2016-01”}]
}
}
的类型描述是：
{
"organization":"string",
"type":"string",
"features":{
"timestamp":"long",
"cities":["string"],
"apps":[{"name":"string", "date":"string"}]
}
}
说明：假设在我们简化的类型系统中，仅支持以下类型 1. 基础类型：字符串(string)，整数(long)
- 复合类型：数组([])，对象({})
请写代码实现函数
boolean type_check(const json &data, const json &schema);
如果data满足schema的类型要求，返回true，否则返回false
注：可以使用你熟悉的一个json库，也可以假设json对象支持如下操作:
-
obj[name]: 如果obj是个复合json对象，返回这个对象中名字叫name的字段值（也是json）
-
obj.has(name)：如果obj是个复合json对象，返回名字name是否是该对象的一个成员名
-
obj[i]：如果obj是个json数组，返回这个数组中下标为 i的元素。
-
obj.size()：如果obj是个json数组，返回该数组的大小
-
obj.type(): 返回当前json对象（原子对象或者复合对象）的类型，可能返回值“string”、“long”、“object”、“array”。
