2676. Throttle
Problem Description
The given problem describes a scenario where we need to create a version of a function that is "throttled." Throttling in this context means that after the function is called once, it cannot be called again for a specified duration t
(in milliseconds). This ensures that the function doesn't execute too frequently within a short time frame.
If the function is triggered again during the throttle period, the parameters (arguments) of this call are saved but not immediately acted upon. Instead, once the throttle period elapses, the function should be executed with the latest saved arguments, resetting the throttle timer for another t
milliseconds. This effect is like postponing all function calls within the throttle period, and only the latest call's arguments are considered when the throttle period ends.
To further simplify:
- Call the function immediately if not within a throttle period.
- If a function call is made during a throttle period, store the latest arguments.
- When the throttle period ends, call the function with the last stored arguments (if any) and start a new throttle period.
An illustration provided shows the effect of throttle over time, emphasizing that only the latest inputs are executed after each throttle period.
Intuition
To achieve the throttling behavior, we maintain a state to track whether we are in a "pending" or throttle period. If the function is not in the pending state, we call it immediately and set it to pending. During this pending state, all subsequent calls will not trigger an immediate function execution but will update the arguments that the function will use after the pending state is resolved.
Here's a breakdown of the solution approach:
- Initialize a
pending
state tofalse
and a variablenextArgs
to store the latest arguments during the pending state. - Create a
wrapper
function that encapsulates the throttling logic:- If
pending
isfalse
, call the function immediately with the provided arguments and setpending
totrue
. This starts the throttle period. - Afterwards, for any calls received during the throttle period (when
pending
istrue
), only updatenextArgs
with the latest arguments.
- If
- Set a
setTimeout
with the durationt
that will reset thepending
state tofalse
after the specified time. It will also check if there arenextArgs
stored, and if so, call thewrapper
function with these arguments, effectively queuing the next execution and starting a new throttle period.
This approach ensures that the function is executed at the correct time intervals while discarding all intermediate calls except for the last one before the end of the throttle period.
Solution Approach
The solution implements throttling using closures and a simple state management system to track when the function should be executed or delayed. Here's a step-by-step breakdown of the algorithm:
-
State Tracking: Two important pieces of state are maintained:
- A boolean
pending
flag, which is initially set tofalse
and indicates whether the function is currently in a throttled period. - A variable
nextArgs
, which will store the arguments passed to the most recent call that occurred during the throttle period.
- A boolean
-
Closure and the Wrapper Function: A
wrapper
function is defined, which will be returned by thethrottle
function. Thewrapper
function serves as the throttled version of the originalfn
. Closures allow thewrapper
to have access to thepending
andnextArgs
variables even after thethrottle
function has finished execution. -
Immediate Execution: If the function is not currently in a pending state (throttle period), it is executed immediately with the given arguments, and
pending
is set totrue
. -
Setting Throttle Period: After the first execution, a
setTimeout
is set for the durationt
milliseconds. This timeout represents the delay during which the function cannot be executed again. -
Handling Subsequent Calls: If the wrapper is called again within the duration
t
(whilepending
istrue
), the arguments are stored innextArgs
. These arguments will be used for the next execution. If further calls are made during the delay, they only updatenextArgs
with the latest arguments, and the previous stored arguments are discarded. -
End of Throttle Period: Once the timer (
setTimeout
) completes, it will setpending
tofalse
, indicating that the throttle period has ended. If there were any calls during the delay period (nextArgs
is notundefined
), thewrapper
function is called again with the last stored arguments, and a new throttle period begins. -
Continuous Throttling: The cycle continues with the
wrapper
function being executed at most once per everyt
milliseconds with the latest arguments that were passed to it during the previous throttle period.
Here's a high-level overview of the coding pattern used:
1const throttle = (fn: F, t: number): F => {
2 let pending = false;
3 let nextArgs;
4 const wrapper = (...args) => {
5 nextArgs = args;
6 if (!pending) {
7 fn(...args);
8 pending = true;
9 nextArgs = undefined;
10 setTimeout(() => {
11 pending = false;
12 if (nextArgs) wrapper(...nextArgs);
13 }, t);
14 }
15 };
16 return wrapper;
17};
The primary data structure used is the JavaScript variable, while the predominant pattern is the use of closure and timer (setTimeout
) for managing the throttle state. This implementation ensures a function is throttled effectively, and its latest call arguments are respected.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a simple example. Suppose we have a function logMessage
that takes a string message as an argument and prints it. We want to throttle this function such that it only executes once every 2 seconds, despite being called multiple times.
Here's the logMessage
function:
1function logMessage(message) {
2 console.log(message);
3}
We'll create a throttled version of logMessage
using the throttle
function provided in the solution approach.
1const throttledLogMessage = throttle(logMessage, 2000);
Now let's simulate a series of calls to throttledLogMessage
with different messages:
1throttledLogMessage("First call - Immediate"); // Executed immediately
2throttledLogMessage("Second call - Discarded"); // Ignored during throttle period
3setTimeout(() => throttledLogMessage("Third call - 2s later"), 500); // Ignored, still in throttle period
4setTimeout(() => throttledLogMessage("Fourth call - 2.5s later"), 2500); // Executed after throttle period with these arguments
Here's how the throttling mechanism processes each call:
-
The first call to
throttledLogMessage("First call - Immediate")
executes immediately because we are not in a throttle period, prints "First call - Immediate", and starts the 2-second throttle period. -
During the throttle period (2 seconds), any calls to
throttledLogMessage
do not execute immediately. The second call's arguments are stored, but are soon overwritten by the third call's arguments, as it is the most recent before the timeout finishes. -
The
setTimeout
callback set during the first call times out after 2 seconds, ending the throttle period and checkingnextArgs
. It finds thatnextArgs
contains arguments from the third call and executesthrottledLogMessage("Third call - 2s later")
. However, since we deliberately placed the fourth call outside of the throttled period (2.5 seconds later), it becomes the pending arguments (not the third call). -
The call with "Fourth call - 2.5s later" is then executed, and a new throttle period starts.
After all these calls, the printed messages to the console will be:
1First call - Immediate 2Fourth call - 2.5s later
This example demonstrates how the solution makes use of closures, state variables (pending
, nextArgs
), and the setTimeout
function to throttle calls, ensuring the function execution is spaced out by at least 2 seconds and that only the most recent call's arguments are used.
Solution Implementation
1from typing import Callable, Any, List
2import threading
3import time
4
5# Type definition for a function that accepts any number of arguments of any type.
6FunctionWithAnyArgs = Callable[..., None]
7
8def throttle(fn: FunctionWithAnyArgs, delay: float) -> FunctionWithAnyArgs:
9 """
10 Creates a throttled function that only invokes the provided function at most once per every `delay` seconds.
11
12 :param fn: The function to throttle.
13 :param delay: The number of seconds to throttle invocations to.
14 :returns: A new throttled version of the provided function.
15 """
16 # Flag to indicate if there is a pending function execution.
17 is_pending = False
18 # An array to store the latest arguments with which to call the function when it becomes available.
19 next_args: List[Any] = []
20 # Lock to synchronize access to shared data.
21 lock = threading.Lock()
22
23 def reset_pending():
24 nonlocal is_pending, next_args
25 with lock:
26 is_pending = False
27 if next_args:
28 # If there are pending arguments, invoke the wrapper function with them.
29 throttled_wrapper(*next_args)
30 # Clear the arguments once they've been used.
31 next_args = []
32
33 def throttled_wrapper(*args: Any) -> None:
34 nonlocal is_pending, next_args
35 with lock:
36 next_args = args # Store the latest arguments.
37 if not is_pending: # If there is no pending execution, proceed.
38 fn(*args) # Call the original function immediately with the provided arguments.
39 is_pending = True # Set the flag to True to prevent immediate succeeding calls.
40 # Start a timer that will reset the flag and call the wrapper if there are pending arguments.
41 threading.Timer(delay, reset_pending).start()
42
43 return throttled_wrapper # Return the throttled version of the function.
44
45# Usage example:
46# def print_log(message):
47# print(message)
48#
49# throttled_log = throttle(print_log, 0.1)
50# throttled_log("log") # This log statement is executed immediately.
51# time.sleep(0.05)
52# throttled_log("log") # This log statement will be executed after the delay (t=0.1s) due to throttling.
53
1import java.util.Timer;
2import java.util.TimerTask;
3
4// Interface to represent any function that can take any number of arguments.
5interface FunctionWithAnyArgs {
6 void call(Object... args);
7}
8
9public class Throttler {
10 /**
11 * Creates a throttled function that only invokes the provided function
12 * at most once per every 'delay' milliseconds.
13 *
14 * @param fn The function to throttle.
15 * @param delay The number of milliseconds to throttle invocations to.
16 * @return A new throttled version of the provided function.
17 */
18 public static FunctionWithAnyArgs throttle(FunctionWithAnyArgs fn, long delay) {
19 // Object to hold the state of the throttle mechanism.
20 final Object state = new Object() {
21 boolean isPending = false;
22 Object[] nextArgs = null;
23 Timer timer = new Timer();
24 };
25
26 // The wrapper function that manages the invocation of the original function with throttling.
27 return (Object... args) -> {
28 synchronized (state) {
29 state.nextArgs = args; // Store the latest arguments.
30 if (!state.isPending) { // If there is no pending execution, proceed.
31 fn.call(args); // Call the original function immediately with the provided arguments.
32 state.isPending = true; // Set the flag to true to prevent immediate succeeding calls.
33 state.nextArgs = null; // Clear the arguments since the function has been called.
34
35 // After `delay` milliseconds, reset the flag and call the wrapper if there are pending arguments.
36 state.timer.schedule(new TimerTask() {
37 @Override
38 public void run() {
39 synchronized (state) {
40 state.isPending = false;
41 if (state.nextArgs != null) { // If there are pending arguments, invoke the wrapper function with them.
42 fn.call(state.nextArgs);
43 state.nextArgs = null; // Clear nextArgs after the invocation.
44 }
45 }
46 }
47 }, delay);
48 }
49 }
50 };
51 }
52
53 // Usage example within a main method or any other method:
54 public static void main(String[] args) {
55 FunctionWithAnyArgs throttledLog = throttle((Object... logArgs) -> {
56 // Assume we're printing the first argument for simplicity, real-world use might differ
57 if (logArgs.length > 0) {
58 System.out.println(logArgs[0]);
59 }
60 }, 100);
61
62 // This log statement is executed immediately.
63 throttledLog.call("log1");
64 // The following log statement will be rescheduled to execute after the throttling delay.
65 new Timer().schedule(new TimerTask() {
66 @Override
67 public void run() {
68 throttledLog.call("log2");
69 }
70 }, 50);
71 }
72}
73
1#include <functional>
2#include <chrono>
3#include <thread>
4#include <vector>
5#include <mutex>
6
7// Type for a function that accepts any number of arguments of any type.
8using FunctionWithAnyArgs = std::function<void()>;
9
10class Throttler {
11private:
12 FunctionWithAnyArgs fn;
13 int delay;
14 bool isPending;
15 std::mutex mtx;
16
17public:
18 Throttler(const FunctionWithAnyArgs& fn, int delay)
19 : fn(fn), delay(delay), isPending(false) {}
20
21 // Wrapper function that manages the invocation of the original function with throttling.
22 template<typename... Args>
23 void operator()(Args... args) {
24 std::unique_lock<std::mutex> lock(mtx);
25 if (!isPending) { // If there is no pending execution, proceed.
26 fn(); // Call the original function immediately with the provided arguments.
27 isPending = true; // Set the flag to true to prevent immediate succeeding calls.
28 lock.unlock(); // Unlock the mutex before sleeping the thread.
29
30 std::thread([this](){
31 std::this_thread::sleep_for(std::chrono::milliseconds(delay));
32
33 std::lock_guard<std::mutex> guard(this->mtx);
34 this->isPending = false; // After `delay` milliseconds, reset the flag.
35 }).detach();
36 }
37 }
38};
39
40// Usage example:
41int main() {
42 // Creates a throttled function that prints the argument to console.
43 Throttler throttledPrint([]() {
44 std::cout << "Print function called." << std::endl;
45 }, 100);
46
47 throttledPrint(); // This print function is executed immediately.
48
49 // Simulate a call to the function after a short delay.
50 std::this_thread::sleep_for(std::chrono::milliseconds(50));
51 throttledPrint(); // Due to throttling, this call doesn't do anything.
52
53 // Wait some extra time to see the effects.
54 std::this_thread::sleep_for(std::chrono::milliseconds(200));
55
56 return 0;
57}
58
1type FunctionWithAnyArgs = (...args: any[]) => void; // Type for a function that accepts any number of arguments of any type.
2
3/**
4 * Creates a throttled function that only invokes the provided function at most once per every `delay` milliseconds.
5 *
6 * @param fn - The function to throttle.
7 * @param delay - The number of milliseconds to throttle invocations to.
8 * @returns A new throttled version of the provided function.
9 */
10const throttle = (fn: FunctionWithAnyArgs, delay: number): FunctionWithAnyArgs => {
11 // Flag to indicate if there is a pending function execution.
12 let isPending = false;
13 // An array to store the latest arguments with which to call the function when it becomes available.
14 let nextArgs: any[] | undefined;
15
16 /**
17 * The wrapper function that manages the invocation of the original function with throttling.
18 *
19 * @param args - Arguments with which the function is expected to be called.
20 */
21 const throttledWrapper = (...args: any[]): void => {
22 nextArgs = args; // Store the latest arguments.
23 if (!isPending) { // If there is no pending execution, proceed.
24 fn(...args); // Call the original function immediately with the provided arguments.
25 isPending = true; // Set the flag to true to prevent immediate succeeding calls.
26 nextArgs = undefined; // Clear the arguments since the function has been called.
27 setTimeout(() => { // After `delay` milliseconds, reset the flag and call the wrapper if there are pending arguments.
28 isPending = false;
29 if (nextArgs) throttledWrapper(...nextArgs); // If there are pending arguments, invoke the wrapper function with them.
30 }, delay);
31 }
32 };
33
34 return throttledWrapper; // Return the throttled version of the function.
35};
36
37// Usage example:
38// const throttledLog = throttle(console.log, 100);
39// throttledLog("log"); // This log statement is executed immediately.
40// setTimeout(() => throttledLog("log"), 50); // This log statement will be executed at t=100ms (due to throttling).
41
Time and Space Complexity
The time complexity of the throttle
function is O(1)
for each call, regardless of the value of t
. This is because each function call involves only a constant number of operations: setting variables, checking conditions, and possibly scheduling a setTimeout
. The actual throttled function fn
is called at most once every t
milliseconds; however, the complexity of fn
itself does not affect the throttling mechanism.
The space complexity of the throttle
function is O(1)
. This is because there are a fixed number of variables used (pending
, nextArgs
, and wrapper
), and their sizes do not depend on the number of times wrapper
is called or the size of the input to fn
. However, be aware that if the fn
function being throttled captures a large scope or requires significant memory, that would affect the overall space complexity of the system using the throttle, but not the throttle implementation itself.
Which data structure is used in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.