Get Min Time
Reported by candidates from Walleye Capital's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Walleye Capital reported this one in February 2024, and it's an LRU cache in disguise. The story is DNS lookups, but the real question is which data structure gives you O(1) hit checks and O(1) eviction of the oldest entry. If you've got an OA coming up, expect to build a small cache simulator and return an array of times, one per URL. The logic is short, but the example in the prompt is confusing, so read it twice. StealthCoder sits invisibly on your screen as a safety net if you blank on the structure mid-assessment, but you can know this one cold before you start.
The problem
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 getMinTime(cache_size: int, cache_time: int, server_time: int, urls: String[]) → int[] 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 Examples Example 1 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"] return = [3, 3, 2, 2, 3, 3, 5, 5] 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
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is an ordered hash map, the same structure behind LeetCode's LRU Cache. For each URL, check whether it's in the cache. If it is, record cache_time and move it to the most recent position. If not, record server_time, insert it, and evict the oldest entry when size exceeds cache_size. In Python use OrderedDict, in Java use LinkedHashMap with access order, or build a hash map plus doubly linked list. The pitfall is the example. The last line shows a hit costing 5, which looks like a typo, since a cache hit should cost 3. Trust the stated rules and the earlier lines, not that line. Another pitfall is using a plain list for the cache, which makes lookups O(n) and times out at n = 10^5. If you freeze on the eviction order during the live OA, StealthCoder is the hedge that hands you the working structure.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Get Min Time cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderYou've seen the question.
Make sure you actually pass Walleye Capital's OA.
Walleye Capital reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Get Min Time FAQ
What's the trick in Get Min Time?+
It's an LRU cache simulation. Keep an ordered hash map of URL to a placeholder. On a hit, add cache_time and move the URL to the most recent end. On a miss, add server_time, insert it, and drop the oldest if you exceed cache_size.
How hard is this really?+
Easy to medium. The logic is a dozen lines if you know LRU. It gets hard only if you build the linked list by hand or use an array scan, which is too slow for 10^5 URLs. Walleye Capital reported it in February 2024.
Does a cache hit refresh the entry's position?+
Yes, treat it as LRU. Moving a hit URL to the most recent spot is the standard reading. The example's last line is inconsistent with the stated costs, so don't build your logic around it. Follow the written rules.
What time complexity should I aim for?+
O(n) overall, with O(1) per URL. With n up to 10^5 and cache_size up to 10^5, anything that scans the cache per request risks O(n^2) and a timeout. Use a hash map with ordering, not a list.
How do I prepare in 48 hours?+
Write LRU Cache from scratch twice, once with a built-in ordered map and once with a hash map plus doubly linked list. Then code this simulator and test it on the sample. Also check the edge case of cache_size 1 and repeated URLs.