2715. Timeout Cancellation
Problem Description
In this problem, you are given a function fn
, an array of arguments args
, and a timeout value t
. Your task is to implement a function cancellable
that, upon invocation, begins a timer countdown of t
milliseconds. If this timer reaches zero without interruption, fn
is called with args
. However, cancellable
also needs to return a cancelFn
function. If cancelFn
is called before t
milliseconds have elapsed, the timer is to be cancelled and fn
should never be called.
Simply put, you need to schedule a future action (fn
being called with args
) to occur after a specified delay (t
ms), but with the ability to cancel that scheduled action within the delay window.
Intuition
The intuitive solution to this problem leverages JavaScript's built-in setTimeout
function, which allows you to execute a callback function after a specified delay. Additionally, setTimeout
returns a unique identifier for the timer it sets up, which can later be used with clearTimeout
to cancel the timer before it triggers execution of the callback.
Here's the thought process for arriving at the solution:
- Use
setTimeout
to schedule the execution offn
withargs
after a delay oft
milliseconds. - Capture the returned timer identifier in a variable, which is required to cancel the timer.
- Define
cancelFn
as a function that callsclearTimeout
with the timer identifier, which will cancel the scheduled execution if it is called beforet
ms have passed. - Ensure that
cancelFn
is returned fromcancellable
function so it can be called externally to cancel the scheduled action.
Effectively, cancelFn
provides an external control to cancel the timer, and if it's not used within t
ms, fn
will execute with the given args
.
Solution Approach
To solve this problem, we mainly use two functions provided by JavaScript: setTimeout
and clearTimeout
. Here is the step-by-step method for the implementation:
- Invoke
setTimeout
with thefn
function and the delayt
. ThesetTimeout
function will accept a callback—in our case, it's an arrow function that spreads theargs
array as arguments tofn
—and a time in milliseconds which tells the JavaScript engine to run the callback after that time has passed.
1const timer = setTimeout(() => fn(...args), t);
-
The
setTimeout
method returns a timer identifier. This identifier is used to refer to the timer so that it can be cancelled if necessary. That's why we store it in a variable namedtimer
. -
Define the
cancelFn
function, which is a simple closure containing theclearTimeout
function. This function takes the timer identifier as an argument and cancels the timer if it's still pending.
1return () => {
2 clearTimeout(timer);
3};
- By returning
cancelFn
, we now give the caller the ability to stopfn
from being called if they invokecancelFn
before the timet
has elapsed.
The concepts used here include:
- Closures: The
cancelFn
function is a closure that has access to thetimer
variable from its outer scope, which is the key to being able to cancel the timer later. - Timeout functions:
setTimeout
is used to delay code execution, andclearTimeout
is used to cancel that delayed execution. - Spread operator: Since
args
is an array and we need to pass its elements as separate arguments tofn
, we use the spread operator (...).
This solution leverages the event loop in JavaScript, which manages the execution of timers and callbacks at specified intervals or after a delay. It's a straightforward and effective pattern for tasks that require delayed execution with the option to cancel if conditions change before the delay is over.
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. Assume we have a function named sayHello
that takes one argument - a string of someone's name - and logs a greeting to the console. We also have an array of arguments ["John"]
, which is the name we want to pass to sayHello
. Our timeout value t
is 3000 milliseconds (3 seconds).
The desired behavior is to schedule sayHello
to be called with "John" after 3 seconds. However, we also want the ability to cancel this scheduled action if we decide that we no longer want to greet John within that 3-second window.
Here's how we would write our cancellable
function based on the solution approach, and demonstrate the process with this example:
1function sayHello(name) {
2 console.log(`Hello, ${name}!`);
3}
4
5const args = ["John"]; // Array of arguments for our function
6const t = 3000; // Timeout value
7
8function cancellable(fn, args, t) {
9 const timer = setTimeout(() => fn(...args), t);
10
11 return () => {
12 clearTimeout(timer);
13 };
14}
15
16// Use case:
17// We want to schedule `sayHello` to be called with "John" after 3 seconds
18const cancelFn = cancellable(sayHello, args, t);
19
20// Let's assume after 1 second, we decide we no longer want to greet John
21// This means we need to cancel the scheduled `sayHello` call
22setTimeout(() => {
23 cancelFn(); // It logs nothing and cancels the scheduled greeting
24 console.log("The greeting was cancelled.");
25}, 1000);
26
In this example, the cancellable
function is invoked with sayHello
, args
, and t
. It schedules sayHello
to be called after 3 seconds. We store the cancellation function cancelFn
, which is capable of stopping the sayHello
call.
After 1 second, we invoke cancelFn
to cancel the scheduled greeting. Because the cancellation function is called before the 3-second timeout completes, sayHello
is never called, and therefore "Hello, John!" is never logged to the console. However, we do see the log "The greeting was cancelled" indicating that the cancellation function worked as expected.
This example demonstrates the basic usage and manipulation of timeouts in JavaScript, providing a clear illustration of how the solution approach works in practice.
Solution Implementation
1import time
2from threading import Timer
3
4# Define a function `make_cancellable` that returns a cancellation function.
5# `fn` is the function to execute after a delay `delay`, and `args` are the arguments to pass to `fn`.
6def make_cancellable(fn, args, delay):
7 # Set a timer to invoke `fn` with provided arguments and delay `delay`.
8 timer = Timer(delay, fn, args)
9
10 # Start the timer.
11 timer.start()
12
13 # Return a function that can be called to cancel the scheduled execution of `fn`.
14 def cancel():
15 timer.cancel()
16
17 return cancel
18
19# Define an array `results` to hold logs of execution time and results.
20results = []
21
22# Define a function `multiply_by_five` which multiplies input by 5.
23def multiply_by_five(x):
24 return x * 5
25
26# Define an array `args` with values to be used as arguments for the target function.
27args = [2]
28# Define values for schedule delay `delay` and cancellation timing `cancel_delay`.
29delay = 0.02 # Delay is in seconds, 20ms converted to seconds
30cancel_delay = 0.05 # 50ms converted to seconds
31
32# Record the start time in milliseconds
33start = int(round(time.time() * 1000))
34
35# Define a logging function `log_results` to track the execution and capture results.
36def log_results(*args_list):
37 # Calculate the time difference from the start in milliseconds.
38 diff = int(round(time.time() * 1000)) - start
39 # Push the `time` and `returned` value to the results list.
40 results.append({'time': diff, 'returned': multiply_by_five(*args_list)})
41
42# Create a cancellable scheduled log call and get the cancellation function.
43cancel = make_cancellable(log_results, args, delay)
44
45# Calculate the maximum timeout needed in milliseconds.
46max_delay = max(delay, cancel_delay)
47
48# Schedule a cancellation of the logging after delay `cancel_delay`.
49Timer(cancel_delay, cancel).start()
50
51# Function to print the results after all actions have completed
52def print_results():
53 print(results)
54
55# Schedule the printing of the results array after delay `max_delay` plus an additional 0.015 seconds to ensure all actions have completed.
56Timer(max_delay + 0.015, print_results).start()
57
1import java.util.ArrayList;
2import java.util.List;
3import java.util.Timer;
4import java.util.TimerTask;
5
6// A class to store the result of the operation.
7class Result {
8 long time;
9 int returned;
10
11 public Result(long time, int returned) {
12 this.time = time;
13 this.returned = returned;
14 }
15}
16
17public class CancellableTaskExample {
18
19 // Define a method `cancellable` that returns a cancellation function.
20 public static Runnable cancellable(TimerTask task, long delay) {
21 Timer timer = new Timer();
22 // Schedule the task for future execution after a delay.
23 timer.schedule(task, delay);
24
25 // Return a function that can cancel the scheduled task.
26 return () -> timer.cancel();
27 }
28
29 // Function to multiply a number by 5.
30 public static int multiplyByFive(int x) {
31 return x * 5;
32 }
33
34 public static void main(String[] args) {
35 List<Result> results = new ArrayList<>(); // Store logs of execution time and results.
36
37 // Record start time of the program execution.
38 final long start = System.currentTimeMillis();
39
40 // TimerTask that encapsulates the multiplyByFive function call.
41 TimerTask task = new TimerTask() {
42 @Override
43 public void run() {
44 int resultValue = multiplyByFive(2); // Use 2 as an argument for multiplication.
45 results.add(new Result(System.currentTimeMillis() - start, resultValue));
46 }
47 };
48
49 long delay = 20; // Execution delay for the task.
50 long cancelDelay = 50; // Delay after which the task will be cancelled.
51
52 // Create a cancellable task and retrieve the cancellation function.
53 Runnable cancelFunction = cancellable(task, delay);
54
55 // Schedule a task to cancel the previous task after a specified delay.
56 new Timer().schedule(new TimerTask() {
57 @Override
58 public void run() {
59 cancelFunction.run(); // Cancel the scheduled task.
60 }
61 }, cancelDelay);
62
63 // Calculate the maximum timeout period.
64 long maxDelay = Math.max(delay, cancelDelay);
65
66 // Schedule a task to log the results after both other tasks have had time to either run or be cancelled.
67 new Timer().schedule(new TimerTask() {
68 @Override
69 public void run() {
70 for (Result result : results) {
71 System.out.println(String.format("Time: %dms, Returned: %d", result.time, result.returned));
72 }
73 }
74 }, maxDelay + 15);
75 }
76}
77
1#include <iostream>
2#include <vector>
3#include <functional>
4#include <chrono>
5#include <thread>
6
7// Define a function `Cancellable` that returns a cancellation function.
8// `fn` is the function to execute after a delay `t`, and `args` are the arguments to pass to `fn`.
9template<typename Function, typename... Args>
10std::function<void()> Cancellable(Function fn, std::tuple<Args...> args, int t) {
11 // Set a timer to invoke `fn` with provided arguments after delay `t`.
12 auto timer_thread = std::make_shared<std::thread>([=]() {
13 std::this_thread::sleep_for(std::chrono::milliseconds(t));
14 std::apply(fn, args);
15 });
16
17 // Return a function that can be called to cancel the scheduled execution of `fn`.
18 return [=]() {
19 if (timer_thread->joinable()) {
20 timer_thread->detach(); // Cancel the scheduled function by not joining the thread.
21 }
22 };
23}
24
25// Define a record type to hold logs of execution time and results.
26struct ResultRecord {
27 int time; // Execution time
28 int returned; // Result of the function
29};
30
31// Define a function `MultiplyByFive` which multiplies input by 5.
32int MultiplyByFive(int x) {
33 return x * 5;
34}
35
36// Example usage:
37int main() {
38 // Define a vector `result` to hold logs of execution time and results.
39 std::vector<ResultRecord> result;
40
41 // Record the start performance time.
42 auto start = std::chrono::high_resolution_clock::now();
43
44 // Define a logging function `Log` to track the execution and capture results.
45 auto Log = [&](int arg) {
46 // Calculate the time difference from the start.
47 auto diff = std::chrono::duration_cast<std::chrono::milliseconds>(
48 std::chrono::high_resolution_clock::now() - start)
49 .count();
50 // Push the `time` and `returned` value to the result vector.
51 result.push_back({static_cast<int>(diff), MultiplyByFive(arg)});
52 };
53
54 // Define values for the argument, schedule delay `t`, and cancellation timing `cancelT`.
55 int arg = 2;
56 int delayT = 20;
57 int cancelT = 50;
58
59 // Create a cancellable scheduled log call and get the cancellation function.
60 auto cancel = Cancellable(Log, std::make_tuple(arg), delayT);
61
62 // Schedule a cancellation of the logging after delay `cancelT`.
63 std::thread cancel_thread([=]() {
64 std::this_thread::sleep_for(std::chrono::milliseconds(cancelT));
65 cancel(); // This will cancel the scheduled logging if it hasn't executed yet.
66 });
67
68 // Calculate the maximum timeout needed.
69 int maxT = std::max(delayT, cancelT);
70
71 // Schedule the console log of the result vector after delay `maxT` plus an additional buffer time.
72 std::this_thread::sleep_for(std::chrono::milliseconds(maxT + 15));
73
74 // Output the results.
75 for (auto &record : result) {
76 std::cout << "[{\"time\": " << record.time << ", \"returned\": " << record.returned << "}]" << std::endl;
77 }
78
79 // Join threads if they are still running.
80 if (cancel_thread.joinable())
81 cancel_thread.join();
82
83 return 0;
84}
85
1// Define a function `cancellable` that returns a cancellation function.
2// `fn` is the function to execute after a delay `t`, and `args` are the arguments to pass to `fn`.
3function cancellable(fn: (...args: any[]) => void, args: any[], t: number): () => void {
4 // Set a timeout to invoke `fn` with provided arguments and delay `t`.
5 const timerId = setTimeout(() => fn(...args), t);
6
7 // Return a function that can be called to cancel the scheduled execution of `fn`.
8 return () => {
9 clearTimeout(timerId);
10 };
11}
12
13// Example usage:
14// Define an array `result` to hold logs of execution time and results.
15const result: { time: number; returned: number }[] = [];
16
17// Define a function `multiplyByFive` which multiplies input by 5.
18const multiplyByFive = (x: number): number => x * 5;
19
20// Define an array `args` with values to be used as arguments for the target function.
21const args: number[] = [2];
22// Define values for schedule delay `t` and cancellation timing `cancelT`.
23const t: number = 20;
24const cancelT: number = 50;
25
26// Record the start performance time.
27const start: number = performance.now();
28
29// Define a logging function `log` to track the execution and capture results.
30const log = (...argsArr: number[]): void => {
31 // Calculate the time difference from the start.
32 const diff: number = Math.floor(performance.now() - start);
33 // Push the `time` and `returned` value to the result array.
34 result.push({ time: diff, returned: multiplyByFive(...argsArr) });
35};
36
37// Create a cancellable scheduled log call and get the cancellation function.
38const cancel = cancellable(log, args, t);
39
40// Calculate the maximum timeout needed.
41const maxT: number = Math.max(t, cancelT);
42
43// Schedule a cancellation of the logging after delay `cancelT`.
44setTimeout(() => {
45 cancel(); // This will cancel the scheduled logging if it hasn't executed yet.
46}, cancelT);
47
48// Schedule the console log of the result array after delay `maxT` plus an additional 15ms to ensure all actions have completed.
49setTimeout(() => {
50 console.log(result); // Should show [{"time": 20, "returned": 10}] if cancel was not called before the log.
51}, maxT + 15);
52
Time and Space Complexity
The time complexity of the function cancellable
mainly depends on the time complexity of the function fn
that is passed as an argument, because the setTimeout
itself is a non-blocking operation and does not add to the time complexity. If we assume that fn
has a time complexity of O(f)
, where f
is a function of the input args
. Then, the time complexity of the cancellable
function would be O(f)
.
The space complexity of the cancellable
function is O(1)
, as it only uses a constant amount of extra space for the timer
variable and the closure returned, which does not depend on the input size or the function fn
.
However, the presented use case where cancellable(log, args, t)
is called sets a timeout which is cleared later on. This operation is constant in time since it schedules a task to be run in the future and then cancels it, there's no iteration or recursion based on the size of an input. Therefore, for this specific case, the time complexity of scheduling and canceling the timeout is O(1)
.
Similarly, the space complexity of this action is O(1)
, as it does not allocate memory in proportion to the input size. It only holds the timeout identifier and the function reference.
What's the relationship between a tree and a graph?
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