Skip to content
Tech Interview Prep
Technical interview guide

Sliding Window

A variable- or fixed-size window over a sequence, expanded and contracted in O(n) total instead of recomputing from scratch.

Read
42 min
Practice MCQs
25
Interview Q&A
25
Edition
v6
Editorial status
Reviewed

Scope: Language-neutral, with container costs cited from CPython 3.14 and the C++ standard containers.

Curated: · Written: · Reviewed:

25 questions

MCQ-1A telemetry service receives 100,000 events one at a time and must report the sum of the last 1,000 events after each arrival. It cannot buffer the full stream or allocate an O(n) prefix array. The current code calls sum(last_1000) on every event, and profiling counts 100 million additions. Which change makes the per-event work O(1), and what is the total number of additions and subtractions for the run?
MCQ-2A metrics job reports the largest total of exactly 4 consecutive samples. Run over an 8-sample buffer it prints 30: a = [10, 10, 10, -100, 5, 5, 5, 5] total, best = 0, float('-inf') for r in range(len(a)): total += a[r] if r >= 4: total -= a[r - 4] best = max(best, total) print(best) Which statement about this run is correct?
MCQ-19A capacity job computes the peak load as the maximum sum of any contiguous window of exactly k minutes from a list of per-minute deltas. The implementation seeds `best = 0` and updates it only inside the loop. Run with k = 3 and deltas [-4, -2, -7, -1, -3], what does it return, and what is the correct peak?
MCQ-23A dedup service must flag a request ID that repeats within the last k requests. The deployed implementation (Python 3) is: ```python window = set() for i, v in enumerate(ids): if i > k: window.discard(v) if v in window: return True window.add(v) return False ``` Which input below does it misclassify: returning False when a correct sliding-window check returns True?
MCQ-3A rate limiter scans a 7-element array of per-second request counts, `a = [4, 1, 3, 2, 5, 1, 2]`, with `limit = 6`, using the two-pointer loop below. A reviewer flags the inner `while` as making the scan O(n²). Tracing the loop, how many times does `left` advance in total, and what does that say about the bound? ```python left = total = 0 best = 0 for right, v in enumerate(a): total += v while total > limit: total -= a[left] left += 1 best = max(best, right - left + 1) ```
MCQ-9When counting contiguous subarrays that satisfy a monotonic condition (such as having sum at most S on non-negative integers), a sliding window expands right and contracts left until the window [left, right] is valid. Why does adding (right - left + 1) to the running total at each right step count all newly formed valid subarrays without omissions or double-counting?
MCQ-4Consider this sliding-window function, intended to return the length of the longest subarray whose sum is at most `limit`: ```python def longest_leq(a, limit): left = 0 total = 0 best = 0 for right, v in enumerate(a): total += v best = max(best, right - left + 1) # line A while total > limit: total -= a[left] left += 1 return best ``` For `a = [1, 1, 1, 1, 10, 1]` and `limit = 5`, what does this function return?
MCQ-22A routine returns the length of the longest contiguous run of 1s obtainable by flipping at most k zeros in a binary array. It keeps a window [left, right] and a count of the zeros inside it, extending right by one each step and shrinking from the left while the zero count exceeds k. For a = [1,0,0,1,0,1,1,0,0,0,1] and k = 2, what does the routine return?
MCQ-18Python 3.12. This function is meant to return the longest substring of `s` containing at most `k` distinct characters: ```python def longest(s, k): left = best_len = best_start = 0 counts = {} for right, ch in enumerate(s): counts[ch] = counts.get(ch, 0) + 1 while len(counts) > k: counts[s[left]] -= 1 if counts[s[left]] == 0: del counts[s[left]] left += 1 if right - left + 1 > best_len: best_len, best_start = right - left + 1, left return s[left:right + 1] ``` What does `longest("eceba", 2)` return?
MCQ-7A developer traces the last-seen-index sliding-window solution for longest substring without repeating characters on `s = "abcabcbb"`. At the step where `right = 6`, the window covers indices 3..5 (`"abc"`), and `s[6] = 'b'` is already in the window with `lastSeen['b'] = 4`. What does the algorithm do next, and what is the maximum length recorded so far?
MCQ-8When counting contiguous subarrays containing exactly K distinct values, standard two-pointer sliding window implementations routinely evaluate atMost(K) - atMost(K - 1) instead of matching exactly K in a single pass. What fundamental property enforces this formulation?
MCQ-6In an implementation of Minimum Window Substring over a string of length N, the outer loop advances a right pointer character by character while an inner loop advances a left pointer until the window no longer satisfies all target character frequencies. What mechanics guarantee that the overall runtime remains O(N) rather than O(N^2)?
MCQ-10Find every permutation of a pattern (M characters, k of them distinct) inside a text of length N over an alphabet of size Σ, where Σ can reach 65,536. The matcher must decide at each of the N window positions whether the window is a permutation (exactly, with no false positives) and per-slide work must stay O(1) independent of Σ. Which pairing does that?
MCQ-5A team implements 'longest subarray with sum ≤ k' as a window that grows right and shrinks left while the running sum exceeds k. On a = [5, 5, -10, 5] with k = 5, what does the function return, and what is the correct answer?
MCQ-25A service logs the net change in active connections over four consecutive minutes: +3, +3, -5, +3. You want the longest contiguous span whose net change totals at most 4. The standard two-pointer window: advance right, add to the running sum, and while the sum exceeds 4 subtract a[left] and advance left: reports a longest span of 3. What is the correct longest span, and why does the two-pointer miss it?
MCQ-17A function counts contiguous subarrays of a = [3, -1, 4, -2, 5] whose elements sum to k = 4. The array contains negatives, so a two-pointer window is unreliable. Which count does the prefix-sum-with-hash-map version return?
MCQ-20A service needs, for each position in a stream of n = 10^6 positive integers, the length of the shortest suffix ending at that position whose sum is at least S. A candidate's first implementation is: ```python for right in range(n): total = 0 left = right while left >= 0 and total < S: total += a[left] left -= 1 ``` The stream is 10^6 copies of 1 and S = 10^6 + 1. How many times does the inner while-loop body execute in total?
MCQ-11A service maintains the maximum over the last k readings of a stream of n readings using a monotonic deque of indices. Profiling shows a single reading can evict up to k indices from the back of the deque, and the team worries the approach is O(k) per reading. Which statement about the per-element cost and the invariant that bounds it is correct?
MCQ-12A service computes the maximum of the last k = 1000 readings from a stream of n = 10^7 strictly increasing values (each reading is higher than the previous). It uses a max-heap of (-value, index) and after each push runs `while heap[0][1] <= i - k: heappop(heap)`. At the end of the stream, what does the heap contain?
MCQ-15A batch job computes the sliding-window maximum over a 10,000,000-element array with window size 10,000. It keeps candidate indices in a Python `list`: append the new index, pop from the back while the back's value is smaller, and drop the front with `del q[0]` once it leaves the window. On an input that keeps the queue near full, the job takes about four minutes. Which change makes the pass linear?
MCQ-21A queue-depth monitor publishes the largest depth seen in the last 1000 samples. It stores the raw window, keeps a running maximum, and when the departing sample equals that running maximum it scans the 999 samples still in the window for the next largest. A 5,000,000-sample replay from a draining connection has depths that fall strictly from sample to sample. About how many comparisons does that scan perform over the whole replay?
MCQ-16A 4K capture pipeline works on 3840 x 2160 frames, 8,294,400 cells each, and emits for every position the maximum over the 5 x 5 window at that position. The implementation is two monotonic-deque passes: one sliding a window of 5 along each row, writing an intermediate frame of the same 3840 x 2160 size, then the same deque pass down each column of that intermediate. The team's cost model counts one unit for every enqueue and one unit for every dequeue and nothing else, and in a deque pass each element it walks is enqueued once and dequeued once. How many units does one frame cost?
MCQ-13A metrics service computes an exact rolling 5-minute sum over an unbounded event stream of ~200-byte events. The implementation appends every event to a Python list and, on each new event, walks backwards from the end summing events until it reaches one older than 5 minutes. It passes a 10-minute replay test. In production at 2,000 events/s the process is OOM-killed after about 3 hours at a 4 GB limit. Which change fixes the failure?
MCQ-14A metrics service keeps a 60-second sliding window of request timestamps in a deque: each request appends its timestamp, and the front is popped while its timestamp is older than now − 60 s. The deque is also capped at 100,000 entries, and when the cap is reached the oldest entry is dropped. Traffic runs at 200 req/s, then bursts at 20,000 req/s for 30 seconds. At the end of the burst, how many entries does the window hold and what span do they cover?
MCQ-24A limiter enforces 1,000 requests per 60 seconds by keeping the timestamps of the last 1,000 admitted requests and rejecting a new request when the oldest of those is younger than 60 seconds. Traffic runs steady at 1,000 req/min, then spikes to 10,000 req/min for several minutes. What does the limiter admit during the spike, and how many timestamps does it hold?