机试题——DNS本地缓存

题目描述

正在开发一个DNS本地缓存系统。在互联网中，DNS（Domain Name System）用于将域名（例如www.example.com）解析为IP地址，以便将请求发送到正确的服务器上。通常情况下，DNS请求会发送到互联网上的某个DNS服务器，这会造成一定的网络延迟和负载。为了解决这个问题要开发一个本地DNS缓存系统，可以在本地缓存一部分DNS请求的结果，以提高性能和减轻网络负载。

DNS本地缓存系统有以下功能：

• 系统初始状态无存储记录，最大可缓存N条记录。
• 系统每1秒能解析1个URL地址，先从本地DNS上查找：
  • 如果本地缓存中能查到就直接返回from_cache。
  • 如果本地DNS上没有该地址，返回from_internet，并从URL的属性列表tls上，读取该URL的TTL（Time To Live，代表该URL的生存时长，即能够保存到缓存系统中的时长），并将URL存入缓存系统中；如果在tls上未能读到该URL的TTL，设置默认TTL为5秒。
• 本地缓存系统中URL地址的TTL每秒减1，当TTL=0时，将该URL地址从缓存系统中移除。
• 在系统空间装满后，如果还有新的URL要录入，则将TTL最小的一个URL移除，如果TTL最小的URL存在多个，按照先进先出的方式移除1个URL。
• 现在每1秒输入一个URL地址，求每个URL地址的解析方式（from_cache还是from_internet）。

输入描述

输入包含多行：

1. 第一行包含两个整数N和X，分别表示DNS缓存系统的最大缓存记录数和待请求的URL数量。
2. 第二行包含X个整数，分别代表对应的URL地址，形如：url1, url2, url3, ..., urlX，元素允许重复。
3. 第三行包含一个整数Y，表示URL的属性列表tls的长度。
4. 接下来的Y行，每行包含两个整数url_i和ttl_i，分别表示URL的编号和对应的TTL值。

数据范围说明：

• 0 < N, X, Y ≤ 65535，N、X、Y为正整数。
• 0 ≤ url_i, ttl_i ≤ 65535，url_i、ttl_i为整数。

输出描述

输出每秒中URL的解析方式列表：

• 0表示from_cache。
• 1表示from_internet。

用例输入

5 5
3 1 2 1 2
2
1 4
2 2

1 1 1 0 1

10 15
11 14 10 5 8 3 8 13 12 9 12 15 15 7 7
8
11 2
14 11
10 9
5 7
8 1
13 10
9 10
15 8

1 1 1 1 1 1 1 1 1 1 0 1 0 1 0

解题思路

本题需要模拟一个DNS本地缓存系统的工作过程，主要思路如下：

1. 数据结构设计：
   • 使用一个优先队列（最小堆）来管理缓存中的URL，以便快速找到TTL最小的URL。
   • 使用一个布尔数组f来记录某个URL是否在缓存中，以便快速判断是否命中缓存。
2. 初始化：
   • 读取输入数据，包括缓存大小N、URL数量X、URL列表以及URL的TTL属性。
   • 初始化所有URL的默认TTL为5秒。
3. 模拟每秒的解析过程：
   • 每秒处理一个URL：
     • 先检查缓存中是否有该URL：
       • 如果有，输出0（from_cache）。
       • 如果没有，输出1（from_internet），并将该URL加入缓存。
     • 如果缓存已满，移除TTL最小的URL（如果TTL最小的URL有多个，按照先进先出移除）。
     • 更新缓存中所有URL的TTL，移除TTL为0的URL。
4. 输出结果：
   • 按照每秒的解析结果输出对应的0或1。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <string>
#include <stack>
#include <algorithm>
#include <map>
using namespace std;
#define msize  100005struct node {int edt, stt, id; // edt代表生存周期结束时间，stt代表开始时间bool operator<(const node& b) const {// 优先队列默认为大堆顶，所以要将优先删除的TTL最小的// 即结束时间最小的排在前面，相等时按先进先出原则，按开始时间排序。if (edt == b.edt) return stt > b.stt;return edt > b.edt;}
};int n, x, y; // 请求数量 cache大小 ts表大小
priority_queue<node> q; // 优先队列定义
int re[msize];          // 请求数量
int ttls[msize];        // 每个URL的ttl
bool f[msize];          // 记录当前队列中有没有某个URLint main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> x;for (int i = 1; i <= x; i++) {cin >> re[i];}for (int i = 0; i < msize; i++) {ttls[i] = 5;f[i] = 0;}cin >> y;for (int i = 0; i < y; i++) {int u, t;cin >> u >> t;ttls[u] = t;}for (int i = 1; i <= x; i++) {// 已经过期了while (q.size() && q.top().edt <= i) {f[q.top().id] = 0; // 该url不在了q.pop();}if (f[re[i]]) {// 存在缓存中cout << "0 ";} else {// 缓存满了就得扔出去一个if (q.size() == n) {f[q.top().id] = 0;q.pop();}f[re[i]] = 1;q.push({i + ttls[re[i]], i, re[i]});cout << "1 ";}}
}