备战秋招】每日一题:2022年9月23日-华为OD(第二题)-DNS本地缓存

为了更好的阅读体检，可以查看我的算法学习网站
在线评测链接:P1164

题目内容

塔子哥是一名软件工程师，他正在开发一个 $D NS$ 本地缓存系统。在互联网中， $D NS$ （ $Do main N am e S ys t e m$ ）用于将域名（例如www.example.com）解析为IP地址，以便将请求发送到正确的服务器上。通常情况下， $D NS$ 请求会发送到互联网上的某个 $D NS$ 服务器，这会造成一定的网络延迟和负载。为了解决这个问题，塔子哥想要开发一个本地 $D NS$ 缓存系统，可以在本地缓存一部分 $D NS$ 请求的结果，以提高性能和减轻网络负载。

塔子哥的这个 $D NS$ 本地缓存系统有功能如下：

系统初始状态无存储记录，最大可缓存N条记录;
系统每 $1$ 秒能解析 $1$ 个 $U R L$ 地址，先从本地 $D NS$ 上查找，如果本地缓存中能查到就直接返回 $f ro m$ _ $c a c h e$ ;
如果本地 $D NS$ .上没有该地址，返回 $f ro m$ _ $in t er n e t$ , 并从 $U R L$ 的属性列表 $tl s$ 上，读取该 $U R L$ 的 $TT L$ ( $T im e$ $T o$ $L i v e$ 代表该 $U R$ L的生存时长，即能够保存到缓存系统中的时长)，并将 $U R L$ 存入缓存系统中;如果在 $t s$ 上未能读到该 $U R L$ 的 $TT L$ ,设置默认 $TT L$ 为 $5 s$ ;
本地缓存系统中 $U R L$ 地址的 $TT L$ 每秒减 $1$ ，当 $TT L = 0$ 时，将该 $U R L$ 地址从缓存系统中移除;
在系统空间装满后，如果还有新的 $U R L$ 要录入，则将TTL最小的一个 $U R L$ 移除，如果TTL最小的 $U R L$ 存在多个，按照先进先出的方式移除 $1$ 个 $U R L$ .

现在每 $1$ 秒输入一个 $U R L$ 地址,求每个 $U R L$ 地址的解析方式( $f ro m$ $c a c h e$ 还是 $f ro m$ $in t er n e t$ )。

输入描述

第一行两个整数 $N\ X$ ，代表 $D NS$ 的缓存空间以及待请求的 $U R L$ 的数量

接下来一行 $X$ 个整数，分别代表对应的 $u r l$ , 形如: $url_1 ,url_2 , url_3 , ... ,url_X$ , 元素允许重复

接下来一行整数 $Y$ , 代表 $U R L$ 的属性列表 $tl s$ 长度.

接下来 $Y$ 行，每行两个整数， $url_i$ 和 $ttl_i$ .

数据范围说明:

$\leq 65535,N,X,Y$ 为正整数

$\leq url_i , ttl_i \leq 65535 , url_i , ttl_i$ 为整数

输出描述

每秒中url的解析方式列表( $0 :$ $f ro m$ _ $c a c h e$ , $1 : f ro m$ _ $in t er n e t$ )

样例

输入

输出

1 1 1 0 1

样例2

输入

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

思路

优先队列 + 模拟

按题意模拟即可。需要想到使用优先队列维护本地 $D NS$ 缓存。这里注意不要直接使用 $TT L$ 存储而是直接存储一个 $U R L$ 的生存周期结束时间，这样利于优先队列排序和删除处理。

更多的细节可以见代码的逐行注释。

类似题目推荐

LeetCode

1.239. 滑动窗口最大值 - 优先队列入门

2.264. 丑数 II

3.621. 任务调度器

4.857. 雇佣 K 名工人的最低成本

CodeFun2000

1.P1211 塔子大厂真题模拟赛-第一题-魔法石(Ⅰ)

2.P1057 华为od 2022.11.17-分奖金

3.P1052 华东师范大学保研机试-2022-乘法

代码

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 65536;
struct Node		//维护一个URL的信息
{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;}
};
priority_queue<Node> que;	//优先队列定义
int n, x, y;
int q[N];			//询问数组
int ttls[N];		//每个URL的ttl
bool f[N];			//记录当前队列中有没有某个URL
int main()
{cin >> n >> x;for(int i = 1 ; i <= x ; i ++) {		//输入待处理的YLRLcin >> q[i];}for(int &t:ttls) {	//将所有的ttl初始化为5t = 5;}cin >> y;while(y--) {		//循环y次int url, ttl;cin >> url >> ttl;ttls[url] = ttl;		//更新这些URL的ttl}for(int i = 1 ; i <= x ; i++) {while(que.size() && que.top().edt <= i) {		//删除所有结束时间在i之前的本地缓存f[que.top().id] = 0;que.pop();}if(f[q[i]]) {		//如果本地缓存中有输出0cout << 0 << " \n"[i==x];} else {cout << 1 << " \n"[i==x];	//没有则输出1，然后添加到本地缓存中if(que.size() == n) {		//如果满了删除队列顶一个元素f[que.top().id] = 0;que.pop();}f[q[i]] = 1;que.push({i+ttls[q[i]], i, q[i]});//将当前的URL放入队列}}
}

python

import copy
from queue import PriorityQueueN, X = map(int, input().strip().split()) # 输入 DNS 缓存上限和 TTL 上限
askurls = list(map(int, input().strip().split())) # 多次 DNS 查询的 URL 序列 
urltmap = {} 
Y = int(input().strip())
for i in range(Y):url, ttl = map(int, input().strip().split()) # 输入 DNS 地址以及相应的生存周期 TTLurltmap[url] = ttl # 将 URL 和 TTL 存储在字典 urltmap 中
ans = ""
fn = [False] * 65536 # 初始化布尔数组 fn，用于判断某个 URL 是否已经被缓存
pq = PriorityQueue() # 初始化优先队列 pq，用于维护本地 DNS 缓存
for i in range(len(askurls)):while not pq.empty() and pq.queue[0][0] <= i:# 找到优先队列中已过期的生存周期的 URL，进行删除处理cur = pq.get() fn[cur[2]] = False # 如果当前 URL 已经被缓存，则将结果字符串连接 "0 "if fn[askurls[i]]: ans += "0 "else: # 否则当前 URL 还未被缓存，则将结果字符串连接 "1 "ans += "1 "if len(pq.queue) >= N: # 如果已缓存的 URL 数量达到 DNS 缓存上限 N，则进行删除处理cur = pq.get() # 取出优先级最高的 URL，进行删除处理fn[cur[2]] = False # 将被删除的 URL 对应的缓存状态设置为 Falsepq.put((i+urltmap.get(askurls[i], 5), i, askurls[i])) # 将当前 URL 存储在优先队列中，并根据 TTL 计算其生存周期结束时间fn[askurls[i]] = True # 将当前 URL 对应的缓存状态设置为 True，表示已被缓存
print(ans[:-1]) # 输出结果字符串

Java

import java.util.*;
public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);int n= scanner.nextInt(),x= scanner.nextInt();int[] url=new int[x];int max=0;for (int i = 0; i < x; i++) {url[i]= scanner.nextInt();}int y= scanner.nextInt();Map<Integer,Integer> map=new HashMap<>();for(int i=0;i<y;i++){map.put(scanner.nextInt(),scanner.nextInt());}PriorityQueue<int[]> pq=new PriorityQueue<>((o1, o2) -> o1[1]==o2[1]?o1[0]-o2[0]:o1[1]-o2[1]);Map<Integer,int[]> cache=new HashMap<>();int[] ans=new int[x];for(int i=0;i<x;i++){//先删除持续时间结束的while(pq.size()>0&&pq.peek()[1]<=i){int[] rem=pq.poll();cache.remove(rem[2]);}if(cache.containsKey(url[i])){ans[i]=0;}else {ans[i]=1;//如果优先队列的第一个元素的结束时间小于当前时间if(pq.size()==n){int[] rem=pq.poll();cache.remove(rem[2]);}//开始时间 结束时间 urlint[] add=new int[]{i,i+map.getOrDefault(url[i],5),url[i]};pq.offer(add);cache.put(url[i],add);}}for(int i=0;i<x;i++){System.out.print(ans[i]+" ");}}
}
// by 月与海

Go

package mainimport ("fmt"
)const N = 70000var n, x, y, idx int
var urls, tls map[int]int //urls: key url,value ttl
var q, ans, seq []int     //seq记录url进入的时机func getMin() int {//选择缓存中ttl最小的删除var res int = -1minTtl := Nfor url, ttl := range urls {if ttl < minTtl {minTtl = ttlres = url} else if ttl == minTtl {if seq[url] < seq[res] {res = url}}}return res
}func main() {//初始化所有slice和mapq = make([]int, N)ans = make([]int, N)seq = make([]int, N)urls, tls = make(map[int]int), make(map[int]int)fmt.Scan(&n, &x)for i := 0; i < x; i++ {fmt.Scan(&q[i])}fmt.Scan(&y)for i := 0; i < y; i++ {//初始化urls序列var url, ttl intfmt.Scan(&url, &ttl)tls[url] = ttl}//每1秒输入一个URL地址 那么x有个暗含的意思就是处理时间for i := 0; i < x; i++ {//先从本地DNS上查找，如果本地缓存中能查到就直接返回from_cache -> 0if _, ok := urls[q[i]]; ok {ans[i] = 0} else {//本地缓存中查不到 -> from_internet 1ans[i] = 1//将这条url加入 urls中 先判断有没有装满 如果装满了就ttl最小的移除 如果ttl一样 就将入队时间早的移除if len(urls) == n {delete(urls, getMin())}//将url 放入urls 从URL的属性列表tls上，读取该URL的TTL 并将URL存入缓存系统中;如果在ts上未能读到该URL的TTL,设置默认TTL为5s;if _, ok := tls[q[i]]; ok {urls[q[i]] = tls[q[i]]} else {urls[q[i]] = 5}seq[q[i]] = idxidx++}//一秒结束了 URL地址的TTL每秒减1，当TTL=0时，将该URL地址从缓存系统中移除;for url := range urls {urls[url]--if urls[url] == 0 {delete(urls, url)}}}for i := 0; i < x; i++ {fmt.Printf("%d", ans[i])if i != x-1 {fmt.Printf(" ")}}
}
// by xchen

Js

// 设置 stdin 接收输入数据
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {input += data;return;
});process.stdin.on('end', () => {// input 数组以字符串形式存储了所有输入内容。input[i] 存储第i行的所有内容.input = input.split('\n');// 获取输入参数const param0 = input[0].split(' ')const N = Number(param0[0]) // 缓存容量const X = Number(param0[1]) // 请求个数const urlList = new Array() // url 请求列表const param1 = input[1].split(' ')for (let m = 0; m < X; m++) {urlList.push(Number(param1[m]))}const Y = Number(input[2]) const tls = new Map() for (let i = 0; i < Y; i++) {let tmp = input[3+i].split(' ')tls.set(Number(tmp[0]), Number(tmp[1]))}const cache = new Array() // 缓存const set = new Set() // 缓存中 url 集合// 添加 url 到缓存function add(url){if(cache.length < N){cache.push([url, tls.get(url) || 5])set.add(url)} else {if(set.has(url)){// 当前 url 已经存在于缓存中，不需要进行任何操作} else {// 缓存已满，删除缓存中生命周期最短的 url ，并将新的 url 添加到缓存中cache.sort((a, b) => a[1]-b[1])set.delete(cache[0][0])cache.shift()cache.push([url, tls.get(url) || 5])set.add(url)}}}// 更新缓存中 url 的 TTLfunction TTL() {for(let i = 0; i < cache.length; i++){cache[i][1] -= 1let urlTTL = cache[i][1]if(urlTTL === 0){set.delete(cache[i][0])cache.splice(i,1)i--}}}let result = new Array()for (let i = 0; i < X; i++) {// 更新缓存中 url 的 TTLTTL()if(set.has(urlList[i])){// url 存在于缓存中result.push('0')}else{// url 不存在于缓存中，将其添加至缓存中result.push('1')add(urlList[i])}}let ans = ''for(let i = 0; i < result.length - 1; i++){ans += result[i] + ' '}ans += result[result.length-1]console.log(ans)
})