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 serve_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 cacheint cache_time: the time taken to fetch data from the cacheint serve_time: the time taken to resolve an address using the DNS serverString urls[n]: the URLs visited by a user
Returns
int[n]: the minimum time to resolve each DNS request
Example 1:
Input: cache_size = 2, cache_time = 3, serve_time = 5, urls = ["www.google.com", "www.yahoo.com", "www.yahoo.com", "www.google.com", "www.coursera.com"]
Output: [3, 3, 2, 3, 3]
Explanation:Shown in the image above.
Example 2:
Input: cache_size = 3, cache_time = 2, serve_time = 5, urls = ["http://www.hackerranck.com", "http://www.google.com", "http://www.yahoo.com", "http://www.gmail.com", "http://www.yahoo.com", "http://www.hackerrank.com","http://www.gmail.com"]
Output: [5, 5, 5, 5, 5, 2]
Explanation:Shown in the image above.
- 1 ≤ n ≤ 10^5
- 1 ≤ cache_size ≤ 10^5
- 1 ≤ cache_time, serve_time ≤ 10^9
- 1 ≤ size of urls[i] ≤ 20
input:
output: