Loadingone moment…
Sign in to run and submit your work
Reading is open to everyone. Running code and saving drafts need an account so your work is yours and comes back on your next visit.
or
CODE WORKSPACE
The platform team is testing a cache that is only warm on a limited set of hosts. From a load-balancer log they want the longest stretch of consecutive requests that was served by no more than k distinct hosts — that is the longest burst the cache could have absorbed.
Write longest_stretch(hosts, k). It takes hosts, a list of host-name strings where item i is the host that served request i, and k, an integer limit on distinct hosts. It returns a dict {"start": int | None, "length": int} giving where the longest qualifying stretch begins and how many requests it covers.
Function to write
longest_stretch(hosts: list[str], k: int) -> dictA dict with the start index and length of the earliest longest stretch touching at most k hosts; start is None when there is none.
How to approach it
Count each host inside the window. When there are too many hosts, shrink from the left — and remove a host from the counts the moment its count reaches zero.
Sample cases
+ 3 held back until you submit
requests fanning across three hosts
Three hosts with k = 2; the window must shed whole hosts to find the four-request stretch.
Input
Argument 1
[
'web-1',
'web-2',
'web-1',
'web-3',
'web-3',
'web-2',
'web-3',
'web-1'
]Argument 2
2Returns
{
'start': 3,
'length': 4
}one host at a time
Two stretches of length 2 tie under k = 1, so the earliest start (0) wins.
Input
Argument 1
[
'db-a',
'db-a',
'db-b',
'db-b',
'db-c'
]Argument 2
1Returns
{
'start': 0,
'length': 2
}k larger than the fleet
Only two hosts exist and k is 5, so the whole list is one valid stretch.
Input
Argument 1
[
'api-1',
'api-2',
'api-1'
]Argument 2
5Returns
{
'start': 0,
'length': 3
}no requests
An empty request log has no stretch: start is None and length is 0.
Input
Argument 1
[] (empty list)
Argument 2
2Returns
{
'start': None,
'length': 0
}Constraints
hosts. It qualifies when it contains at most k distinct host names (fewer is fine).{"start": i, "length": n} where n is the longest qualifying length and i is its first index.k <= 0 or hosts is empty, return {"start": None, "length": 0}.k is at least the number of distinct hosts, the whole list qualifies.Worked example
Take ["web-1", "web-2", "web-1", "web-3", "web-3", "web-2", "web-3", "web-1"] with k = 2. Counting hosts in the window: indices 0–2 hold web-1 ×2 and web-2 ×1 — two hosts, length 3. Index 3 adds web-3, making three hosts, so shrink from the left: drop index 0 (web-1 → 1), still three hosts; drop index 1 (web-2 → 0, so delete web-2). Now the window 2–3 holds two hosts. Continue: at index 6 the window 3–6 is web-3, web-3, web-2, web-3 — two hosts, length 4, the best. The answer is {"start": 3, "length": 4}.
The trap: if web-2 stays in the dict with a count of 0, len() still says three hosts and the window keeps shrinking (or, if it shrinks only once per step, keeps a window that really holds three hosts), so the reported stretch is wrong.
What this tests
The variable-size sliding window with a frequency map — LeetCode 'Longest Substring with At Most K Distinct Characters' in load-balancer clothing. The target is O(n) time and O(k) space; recounting the hosts of every candidate stretch is O(n²). Data engineers meet this when analysing cache affinity, shard hot-spotting, or the longest window a consumer read from only a few partitions. This exact problem is not named in the data engineering reports we could find; it is the standard Longest Substring with At Most K Distinct Characters shape and covers the frequency-map variant of the pattern.
longest_stretch(hosts: list[str], k: int) -> dictSubmit for review to find out what your query gets right, what it gets wrong, and how it compares with the best working query for this exercise.
This scenario runs a full workspace — editor, canvas and results side by side. It needs a laptop or desktop to be usable. Open this page on a bigger screen to start building.