FastPrep

Description

Solutions

Submission

Get Minimum Time for DNS Resolution

🔥 FULLTIME

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

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"].

Constraints:

1 ≤ n ≤ 10^5
1 ≤ cache_size ≤ 10^5
1 ≤ cache_time, server_time ≤ 10^9
1 ≤ size of urls[i] ≤ 20