A Domain Name System (DNS) translates domain names to IP addresses which are then used by browsers to load internet resources. For quicker DNS lookups, browsers store a number of recent DNS queries in a DNS cache. Retrieving data from the cache is often faster than retrieving it from a DNS server. This task aims to simulate DNS resolution and determine the time taken to process different URLs. Assume that each DNS cache can store a maximum of the cache_size most recent DNS requests, i.e., URL-IP mappings. The cache is initially empty. It takes cache_time units of time to fetch data from the DNS cache, and server_time units of time to fetch data from the DNS server. Given a list of URLs visited as an array of strings, urls, determine the minimum time taken to resolve each DNS request. Note: New DNS requests are dynamically added to the cache, and the cache stores mappings according to the order in which the requests were made. Function Description Complete the function getMinTime in the editor. getMinTime has the following parameters(s):

• int cache_size: the size of the DNS cache
• int cache_time: the time taken to fetch data from the cache
• int server_time: the time taken to resolve an address using the DNS server
• String urls[n]: the URLs visited by a user Returns int[n]: the minimum time to resolve each DNS request

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ cache_size ≤ 10⁵
• 1 ≤ cache_time, server_time ≤ 10⁹
• 1 ≤ size of urls[i] ≤ 20

Example 1

Input:

cache_size = 2
cache_time = 3
server_time = 5
urls = ["www.google.com", "www.yahoo.com", "www.yahoo.com", "www.google.com", "www.yahoo.com", "www.yahoo.com", "www.coursera.com", "www.coursera.com"]

Output:

[3, 3, 2, 2, 3, 3, 5, 5]

Explanation: The DNS resolution process for each URL is as follows:

• www.google.com: Cache is empty, so it takes 5 units of time. Cache becomes ["www.google.com"].
• www.yahoo.com: Not in cache, so it takes 5 units of time. Cache becomes ["www.google.com", "www.yahoo.com"].
• www.yahoo.com: Already in cache, so it takes 3 units of time. Cache remains unchanged.
• www.google.com: Already in cache, so it takes 3 units of time. Cache remains unchanged.
• www.yahoo.com: Already in cache, so it takes 3 units of time. Cache remains unchanged.
• www.yahoo.com: Already in cache, so it takes 3 units of time. Cache remains unchanged.
• www.coursera.com: Not in cache, so it takes 5 units of time. Cache becomes ["www.yahoo.com", "www.coursera.com"].
• www.coursera.com: Already in cache, so it takes 5 units of time. Cache becomes ["www.coursera.com", "www.yahoo.com"].

解法

用 LRU 模型实现：哈希表存 URL 是否在缓存，加双向链表维护访问顺序。每次查询：若命中(在缓存)，时间为 cache_time 并把该项移到 MRU；否则时间为 server_time，把该 URL 插入 MRU，若超出 cache_size 则淘汰 LRU。Python 用 OrderedDict 简化。复杂度均摊 O(1) per 查询，总 O(n)。

from collections import OrderedDict
from typing import List

def get_min_time(cache_size: int, cache_time: int, server_time: int, urls: List[str]) -> List[int]:
    cache = OrderedDict()
    res = []
    for url in urls:
        if url in cache:
            cache.move_to_end(url)
            res.append(cache_time)
        else:
            cache[url] = True
            if len(cache) > cache_size:
                cache.popitem(last=False)
            res.append(server_time)
    return res

import java.util.*;

class Solution {
    int[] getMinTime(int cacheSize, int cacheTime, int serverTime, String[] urls) {
        LinkedHashMap<String, Boolean> cache = new LinkedHashMap<>(16, 0.75f, true);
        int[] res = new int[urls.length];
        for (int i = 0; i < urls.length; i++) {
            String u = urls[i];
            if (cache.containsKey(u)) {
                cache.get(u);
                res[i] = cacheTime;
            } else {
                cache.put(u, true);
                if (cache.size() > cacheSize) {
                    Iterator<String> it = cache.keySet().iterator();
                    it.next();
                    it.remove();
                }
                res[i] = serverTime;
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<int> getMinTime(int cacheSize, int cacheTime, int serverTime, vector<string>& urls) {
        list<string> order;
        unordered_map<string, list<string>::iterator> pos;
        vector<int> res;
        res.reserve(urls.size());
        for (auto& u : urls) {
            auto it = pos.find(u);
            if (it != pos.end()) {
                order.erase(it->second);
                order.push_back(u);
                pos[u] = prev(order.end());
                res.push_back(cacheTime);
            } else {
                order.push_back(u);
                pos[u] = prev(order.end());
                if ((int) order.size() > cacheSize) {
                    pos.erase(order.front());
                    order.pop_front();
                }
                res.push_back(serverTime);
            }
        }
        return res;
    }
};