2715. Timeout Cancellation

Easy
Leetcode Link

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:

  1. Use setTimeout to schedule the execution of fn with args after a delay of t milliseconds.
  2. Capture the returned timer identifier in a variable, which is required to cancel the timer.
  3. Define cancelFn as a function that calls clearTimeout with the timer identifier, which will cancel the scheduled execution if it is called before t ms have passed.
  4. Ensure that cancelFn is returned from cancellable 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:

  1. Invoke setTimeout with the fn function and the delay t. The setTimeout function will accept a callback—in our case, it's an arrow function that spreads the args array as arguments to fn—and a time in milliseconds which tells the JavaScript engine to run the callback after that time has passed.
const timer = setTimeout(() => fn(...args), t);

  1. 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 named timer.

  2. Define the cancelFn function, which is a simple closure containing the clearTimeout function. This function takes the timer identifier as an argument and cancels the timer if it's still pending.

return () => {
    clearTimeout(timer);
};
  1. By returning cancelFn, we now give the caller the ability to stop fn from being called if they invoke cancelFn before the time t has elapsed.

The concepts used here include:

  • Closures: The cancelFn function is a closure that has access to the timer 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, and clearTimeout is used to cancel that delayed execution.
  • Spread operator: Since args is an array and we need to pass its elements as separate arguments to fn, 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 Evaluator

Example 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:

function sayHello(name) {
    console.log(`Hello, ${name}!`);
}

const args = ["John"]; // Array of arguments for our function
const t = 3000; // Timeout value

function cancellable(fn, args, t) {
    const timer = setTimeout(() => fn(...args), t);

    return () => {
        clearTimeout(timer);
    };
}

// Use case:
// We want to schedule `sayHello` to be called with "John" after 3 seconds
const cancelFn = cancellable(sayHello, args, t);

// Let's assume after 1 second, we decide we no longer want to greet John
// This means we need to cancel the scheduled `sayHello` call
setTimeout(() => {
    cancelFn(); // It logs nothing and cancels the scheduled greeting
    console.log("The greeting was cancelled.");
}, 1000);

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

LeetCode Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

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 Review

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 to Algo Cheat Sheet

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More