請選擇盡可能高效的算法，算法復(fù)雜度（大O表示法）比最優(yōu)解高的話啄清，得一半分。
前三題答案（拿到offer）
題目一.文件input.txt是一個文本文件，每一行有多列（用空格分隔）辣卒。keyword.conf是一個關(guān)鍵詞配置文件掷贾，每一行是一個詞。請找出文件input.txt中第一列包含keyword.conf中任意一個關(guān)鍵詞的文本行并輸出荣茫。（25）
示例
輸入：
文件input.txt內(nèi)容：
abc xxx
bcd xxx
def xxx
xyz xxx
文件keyword.conf內(nèi)容：
bc
eft
輸出（打印到標(biāo)準(zhǔn)輸出）：
abc xxx
bcd xxx
題目二****. input.txt中有10萬個隨機整數(shù)想帅，每行一個，范圍從0-99999啡莉，需要分別統(tǒng)計[0-99]港准、[100-199]、[200-299]咧欣、[300-399] …… [99900, 99999]浅缸，出現(xiàn)的次數(shù)。輸出為每個范圍及其中數(shù)字出現(xiàn)的次數(shù)魄咕，范圍和數(shù)字間空格分隔衩椒，每行一個。（20）
示例：
輸入文件input.txt:
123
12
5
123
…
輸出（打印到標(biāo)準(zhǔn)輸出）：
0-99 26
100-199 128
200-299 3
題目三****. 在對域名進(jìn)行分析中哮兰，常常會碰到“主域歸屬”問題毛萌。首先，我們有一個主域列表喝滞，如下所示：
*.sports.sina.com.cn
*.sina.com.cn
*.baidu.com
*.tencent.com
*.com
*.cn
等等，這個列表可能會包含百萬級別的配置右遭。
在有這個配置的前提下做盅，給定一個域名言蛇，比如roll.sports.sina.com.cn，希望能夠找到它所匹配的最長的“主域”宵距，比如腊尚，對于上面這個域名，應(yīng)該匹配到*.sports.這個主域满哪。
請實現(xiàn)一個程序婿斥，從配置文件domain.txt讀取主域列表，每行一個哨鸭；從標(biāo)準(zhǔn)輸入讀取需要匹配的域名民宿，每行一個；向標(biāo)準(zhǔn)輸出打酉窦Α：需要匹配的域名\t它匹配到的最長主域活鹰。注意，請盡可能高效，使用正則匹配會非常慢志群。
題目四****.給定如下設(shè)備數(shù)據(jù)文件input.txt着绷，其中每行一條記錄，空格分隔锌云。一行記錄包含3個字段：設(shè)備ID荠医、連接的wifimac、時間戳桑涎。輸入文件是一個設(shè)備一段時間范圍內(nèi)連接過的wifimac的列表（設(shè)備ID都一樣）彬向，請計算每個設(shè)備連接過的wifimac的熵莺禁。
熵的計算方法：對于一個長度為n的序列xs谷饿，它包含m+1中不同的取值，s0, s1, …, sm呀狼，這些取值對應(yīng)的出現(xiàn)概率分別是p0, p1, …,pm讲衫，則這個序列的熵為H(X) = -(p0log2(p0) + p1log2(p1) + … + pm*log2(pm)). 其中缕棵，某個取值出現(xiàn)的概率p的計算方法為：這個取值出現(xiàn)的次數(shù) 除以 長度n。
示例：
輸入input.txt：
deviceId1 wifimac1 t1
deviceId1 wifimac2 t2
deviceId1 wifimac3 t3
deviceId1 wifimac3 t4
輸出:
devicId1, 1.5
熵的計算過程：
deviceId1活躍4次涉兽，
wifimac1 出現(xiàn)1次 wifimac1 概率：0.25
wifimac2 出現(xiàn)1次wifimac2 概率：0.25
wifimac3 出現(xiàn)2次 wifimac3 概率：0.5
deviceId1下wifimac熵值：-0.25log2(0.25)- 0.25log2(0.25)- 0.5*log2(0.5)
題目五****. 輸入兩個JSON對象招驴，第二個JSON對象是第一個JSON對象的類型描述（schema），請寫代碼檢查第一個對象（數(shù)據(jù)對象）是否滿足第二個對象定義的類型要求枷畏。例如别厘，
對于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"}]
}
}
說明：假設(shè)在我們簡化的類型系統(tǒng)中拥诡，僅支持以下類型 1. 基礎(chǔ)類型：字符串(string)触趴，整數(shù)(long)
- 復(fù)合類型：數(shù)組([])，對象({})
請寫代碼實現(xiàn)函數(shù)
boolean type_check(const json &data, const json &schema);
如果data滿足schema的類型要求渴肉，返回true冗懦，否則返回false
注：可以使用你熟悉的一個json庫，也可以假設(shè)json對象支持如下操作:
obj[name]: 如果obj是個復(fù)合json對象仇祭，返回這個對象中名字叫name的字段值（也是json）
obj.has(name)：如果obj是個復(fù)合json對象披蕉，返回名字name是否是該對象的一個成員名
obj[i]：如果obj是個json數(shù)組，返回這個數(shù)組中下標(biāo)為 i的元素乌奇。
obj.size()：如果obj是個json數(shù)組没讲，返回該數(shù)組的大小
obj.type(): 返回當(dāng)前json對象（原子對象或者復(fù)合對象）的類型，可能返回值“string”礁苗、“l(fā)ong”爬凑、“object”、“array”试伙。
