百度今年一道笔试题——ip攻击这是今年百度的一道笔试题。给你1亿个ip地址和每个ip访问的时间(00:00:00时间
百度今年一道笔试题——ip攻击
这是今年百度的一道笔试题。给你1亿个ip地址和每个ip访问的时间(00:00:00=<时间<=23:59:59，并且已经按照时间排好序了)，然后给定一段时间X，定义在X内如果某IP的访问次数超过Y次，则判定该IP为攻击IP。要求输出所有攻击IP。只有一组测试用例。第一行输入IP记录数(即10万)，时间X(10=<X<=120秒)，次数Y(2=<Y<=100)。输出按访问的时间顺序输出，IP重复不再输出。
输入示例：(为了方便，只给出8个，意思意思)
8 10 2
10.254.82.126 00:00:39
10.85.124.135 00:00:40
10.254.82.126 00:00:44
10.254.82.126 00:00:44
10.1.82.125 00:00:45
10.85.124.135 00:00:48
10.254.82.126 00:00:48
10.254.82.126 00:00:49
输出示例：
10.254.82.126
10.85.124.135
[解决办法]
偶觉得算法思想可以如下：
输入队列比如是
struct ipChain{
char ip[16];
char date[16];
}ipArray[100000];
在这个ipArray上 维持 2个动态标记： head 初始为0 tail为的index为 ipArray[tail].date - ipArray[head].date <= X 并且 ipArray[tail+1].date - ipArray[head].date > X。
将 tail - head + 1个元素 进行散列，加下每个ip的 count 大于Y的直接 可以输出
以后 tail++, 查看先加入的元素是否 使 ipArray[tail].date - ipArray[head].date > x, 大于 则 head++,且 散列表中其count--,一旦为0，删除之。然后 将新加入的ipArray[tail] 加入散列表 查看是否 count > Y。
这样的话 算法 应该比 O（n)差不了多少。
[解决办法]
[解决办法]我实现了14楼的算法，数据量10万个，仅用了0.16秒，很好很强大..
[解决办法]iprec = record
iparr: array of string //也可以采用, 也可采用IP多叉树
iptimes: array of integer //ip 重复次数
end
timestate = record
bgtime: time;
time: array[0.X-1] of iprec;
end;
1: 定义一个已经重复的IP多叉树，寻找IP更快
10 1 254
(2, 85, 254, 120 , 28)
(3, 2, 3 4
(4, 23, 4, 5
2. 定义两个数组(A, B), 大小为X, 分别存在两个时间段X内的攻击IP.
按时间存储到相应数组, 如果相邻次(i-1, i)时间相同且IP也相同, 重复次数+1
A:bgtime: 00:00:39
time[0]: 10.254.82.126
time[1]: 10.85.124.135
time[2]: null
time[3]: null
time[4]: null
time[5]: 10.254.82.16
1
time[6]: 10.1.82.125
time[7]: null
time[8]: 10.85.124.135
time[9]: 10.254.82.126
B:bgtime: 00:00:49
time[0]: 10.254.82.126
time[i]: 10.1.82.125, 10.254.82.125, 10.254.82.127
3. 求出两个数组之内时间内重复IP,
A:bgtime: 00:00:39
time[0]: 10.254.82.126
1
time[1]: 10.85.124.135
1
time[2]: null
time[3]: null
time[4]: null
time[5]: 10.254.82.16
time[6]: 10.1.82.125
time[7]: null
time[8]: 10.85.124.135
1
time[9]: 10.254.82.126
1
B:bgtime: 00:00:49
time[0]: 10.254.82.126
time[i]: 10.1.82.125, 10.254.82.125, 10.254.82.127
4. 求出两组之间有重复的IP, 通过bgtime，及数组对应比较
1.如果B.bgtime - A.bgtime > X 肯定没有重复
2.只要判断A.下标数组 往后X 数组内是否有重复就可以了
5. 输出A、B重复的IP，输出的需要根据IP多叉树查找已经输出过IP，避免重复输出, 同时把输出的IP加入IP多叉树
同时把B数组没有重复的IP移入A数组, 再继续读取填入A, B数组
6. 重复1. 2. 3. 4, 5步
7. 这样可以减少存储空间，如果是1亿级的IP，用哈稀估计内存不能接受
[解决办法] 我的想法是这样的，按照时间字段作为主要的关键00:00:00= <时间 <=23:59:59总共有 86400秒钟，假设时间段x为4秒，那么第一个时间段为00：00：00-00：00：04，第二个时间段
t2为00：00：01-00：00：05，依次类推时间段可以分为86400-x个时间段，可以另外建立一个hash表，记录在某个时间段的摸个ip的访问次数，结构如下：
主键为ip地址，{ip地址，时间段标识，时间标识， 访问次数}。 说明： 时间段标识表示访问时间在那一个时间段中， 时间标识表示访问的时间点。
算法如下：
1，顺序读取时间段t（m）内的第一个ip，
2，判读是否在hash表中，不在的话，插入，设置时间标识字段为m，时间标识为当前访问时间的秒数， 访问次数为1。
如果存在， 如果访问次数大于=y， 直接返回。（改进： 这里可以另外用一个数组保存攻击的ip）
否则的话 ，如果 m - 原来的时间段标识 <= 1 && 时间标识不等于原来的时间段标识 , 那么访问次数加一。
否则的话, 访问次数设置为1.
3，依次循环。
4，最后，在hash表中找出访问次数大于=y的所有记录。
