NeetCode #959LC-2676MediumJavaScript
← Back to All Problems#959 · #2676 · Throttle(节流)
📌 Problem Statement & Constraints
Implement
throttle(fn, t): return a wrapper that invokes fn at most once in any window of t milliseconds; a call suppressed inside a window is replayed with the latest arguments when the window ends.💡 Core Algorithmic Approaches
- Track
nextCall, the timestamp when the next call becomes legal, andpending, the suppressed arguments. - If
now >= nextCall, invoke immediately and setnextCall = now + t. - Otherwise store the arguments in
pendingand schedule asetTimeoutfornextCall - nowto replay them. - On replay, clear
pendingand resetnextCall. The two distinct moments are the immediate leading call and the trailing replay.
💻 Benchmark Python3 Implementation
var throttle = function(fn, t) {
let nextCall = 0; // timestamp when the next call is allowed
let pending = null; // suppressed arguments
return function(...args) {
const now = Date.now();
if (now >= nextCall) {
nextCall = now + t;
fn(...args);
} else {
pending = args;
setTimeout(() => {
if (pending !== null) {
const a = pending;
pending = null;
nextCall = Date.now() + t;
fn(...a);
}
}, nextCall - now);
}
};
};⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1): constant time per call.
💾 Space Complexity
O(1): two state variables and at most one timer.
⚠️ Interview Pitfalls & Follow-ups
- Dropping suppressed calls entirely: the problem requires replaying the last one.
- Creating a new timer on every suppressed call: that causes duplicate executions; guard with the
pendingcheck. - Not resetting
nextCallafter a replay: later throttle windows would break. - Worrying that
nextCall = 0blocks the first call:Date.now()is far larger than 0, so the first call runs immediately.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.