2725. Interval Cancellation

Easy

Problem Description

The challenge is to implement a function that allows repeated invocation of another function (fn) at regular intervals (t milliseconds), and also provides a mechanism to stop these repeated invocations. The function fn will be called with a list of arguments (args) provided to the implemented function. Specifically, fn should be called with args immediately when the implemented function is invoked and then repeatedly every t milliseconds, until a generated cancellation function (cancelFn) is called.

To summarize, the objectives are:

Call the provided function fn with the arguments args right away.
Continue calling fn with args every t milliseconds.
Provide a cancelFn that, when called, will stop further invocations of fn.

The implementation requires tracking these invocations and the mechanism to stop them, which introduces two main aspects to handle – initiating a repetitive action and cancelling that action.

Intuition

The intuition behind the solution uses Javascript's setTimeout and setInterval functions. Here's a step-by-step breakdown of the approach:

Immediate Invocation: Call the function fn with the provided arguments args immediately. This ensures that fn is executed at least once without delay.
Repetitive Invocation: Set up an interval (using setInterval) that repeatedly calls fn with args every t milliseconds. setInterval is the natural choice since it allows us to specify an action to be performed repeatedly at fixed time-intervals.
Cancellation Mechanism: Keep track of the interval ID returned by setInterval. This ID can be used to cancel the interval later. Return a cancellation function (cancelFn) that, when called, uses clearInterval along with the stored ID to cancel further invocations of fn. This cancellation function is essential for stopping the repetitive calls when no longer needed.

By incorporating these steps, we ensure that the function fn will be called at the specified interval t, and we give control to the user to cancel these calls using the cancellation function provided. The result is a flexible mechanism that allows scheduling a function's execution and offers the ability to terminate that schedule.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

TrueFalse

I don’t know

Solution Approach

The implementation of the solution can be broken down into the following key steps:

Immediate Execution: The function fn is called immediately with the provided arguments args. This is straightforward and does not require any complex data structure or pattern. It's a simple invocation using the spread operator (...) to pass all the arguments to the function.
```
1fn(...args);
```
Setting up the Interval: We then set up a recurring interval using setInterval, which is native to JavaScript’s timing events API. It takes two parameters: a function to execute and a time interval t in milliseconds. It returns an interval ID which can be used to reference the interval, so it's important to store this ID. We use the spread operator again to call fn with args within the interval callback function.
```
1const time = setInterval(() => fn(...args), t);
```
Creating the Cancellation Function: To be able to cancel the repetitive invocations set up by setInterval, we require a mechanism that can be called externally. This is done by returning a new function that, when called, uses clearInterval with the previously stored interval ID.
```
1return () => clearInterval(time);
```
Data Structure: The data structure used here is quite simple; the interval ID is stored in a constant called time. This variable holds the reference to the interval which is crucial for controlling it.

By using these steps, we can encapsulate the entire functionality needed for repetitive invocations and cancellation in a concise and easily understandable manner. The use of timing events (setInterval and clearInterval) makes this approach well-suited for scenarios where function invocations need to be made at regular intervals until explicitly cancelled.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's consider a simple scenario to illustrate the solution approach. Suppose we have a function printMessage that takes a single argument, a string message, and we want to print this message to the console every 2 seconds. However, we also want to have the ability to stop printing at some point.

Here is our printMessage function:

1function printMessage(message) {
2    console.log(message);
3}

Now, we will use the described approach to invoke this function at regular intervals and also be able to cancel it. Here are the steps:

Immediate Execution: We want to print the message immediately. Following the solution approach, we call printMessage with the message 'Hello, World!' as soon as our interval setup function is called.

1printMessage('Hello, World!'); // This will output 'Hello, World!' to the console right away.

Setting up the Interval: We will now set up an interval that calls printMessage every 2 seconds with the same message. We need to store the interval ID in a variable.

1const intervalId = setInterval(() => printMessage('Hello, World!'), 2000);
2// This will output 'Hello, World!' to the console every 2 seconds.

Creating the Cancellation Function: To stop the messages from printing, we provide a cancellation function (or cancelFn) that, when invoked, will clear the interval using the stored intervalId.
```
1const cancelFn = () => clearInterval(intervalId);
```

With our cancellation function in place, we can now control when to stop printing the message to the console. Here's how we could use it in practice:

1// Set up the message to print every 2 seconds.
2const cancelPrintMessage = setupPrintInterval('Hello, World!', 2000);
3
4// Let's say we want to stop printing after 10 seconds.
5setTimeout(() => {
6    cancelPrintMessage();
7    console.log('Message printing cancelled.');
8}, 10000);

In the script above:

We pretend there's a function setupPrintInterval that implements our interval setup logic.
It is initially set to print 'Hello, World!' every 2 seconds.
After setting a timeout for 10 seconds, we call cancelPrintMessage, which stops the interval.
We then print 'Message printing cancelled.' to confirm the action.

This example illustrates how the described solution can be used to set up and cancel repeated invocations of a function at regular time intervals.

Solution Implementation

1from typing import Callable, List, Any
2import time
3import threading
4
5
6def cancellable(fn: Callable, args: List[Any], interval: float) -> Callable:
7    """
8    Creates a cancellable function that executes repetitively at a specified interval.
9
10    :param fn: The function to be executed.
11    :param args: The arguments to be passed to the function.
12    :param interval: The time interval in seconds at which the function is to be executed.
13    :return: A cancel function that, when invoked, stops the repeated execution.
14    """
15    # Execute the function with the provided arguments immediately.
16    fn(*args)
17
18    # Function to stop the timer
19    def stop_timer(timer: threading.Timer):
20        timer.cancel()
21
22    # Set up a function that is repeatedly called at the given time interval.
23    def schedule_repeated_execution():
24        fn(*args)
25        timer = threading.Timer(interval, schedule_repeated_execution)
26        timer.start()
27        # Store the timer in the closure to allow cancellation.
28        schedule_repeated_execution.timer = timer
29
30    # Start the initial timer
31    schedule_repeated_execution()
32
33    # Return a function that will cancel the timer, thus stopping the execution
34    return lambda: stop_timer(schedule_repeated_execution.timer)
35
36
37# Example usage:
38
39# Output list to capture the results of the function calls.
40result = []
41
42# The function to be repeatedly invoked, here to multiply its first argument by 2.
43def multiply(x: float) -> float:
44    return x * 2
45
46# Arguments to the function, the interval between function calls, and time after which to cancel.
47args = [4]
48interval = 0.02  # 20 milliseconds in seconds
49cancel_time = 0.11  # 110 milliseconds in seconds
50
51# Wrapped logging function that stores the time and result of each function call.
52def log(*args_arr: Any):
53    elapsed_time = time.time() - start_time  # Calculate elapsed time in seconds.
54    returned_value = multiply(*args_arr)
55    result.append({"time": elapsed_time, "returned": returned_value})  # Store time and returned value.
56
57# Record the start time of the operation.
58start_time = time.time()
59
60# Use the cancellable wrapper
61cancel = cancellable(log, args, interval)
62
63# Set up cancellation to stop the function calls after a certain time.
64cancel_timer = threading.Timer(cancel_time, cancel)
65cancel_timer.start()
66

1import java.util.ArrayList;
2import java.util.List;
3import java.util.Timer;
4import java.util.TimerTask;
5
6/**
7 * Creates a cancellable function that executes repetitively at a specified interval.
8 * @param task - The function (Runnable) to be executed.
9 * @param interval - The time interval in milliseconds at which the function is to be executed.
10 * @return A Runnable that, when run, stops the repeated execution.
11 */
12public Runnable createCancellableFunction(Runnable task, long interval) {
13    // Set up a timer that will execute the task repeatedly.
14    Timer timer = new Timer(true);
15
16    // Schedule the task for repeated fixed-delay execution, beginning after the specified delay.
17    timer.scheduleAtFixedRate(new TimerTask() {
18        @Override
19        public void run() {
20            task.run();
21        }
22    }, 0, interval);
23
24    // Return a Runnable that can be used to cancel the Timer and stop the task from continuing.
25    return () -> timer.cancel();
26}
27
28// Example usage:
29
30public static void main(String[] args) {
31    // Setup the output list to capture the results of the function calls.
32    List<Result> results = new ArrayList<>();
33
34    // Create a task that should be repeatedly invoked; in this case, it multiplies its input by 2.
35    Runnable task = new MultiplyTask(4, results);
36
37    // Interval between function calls in milliseconds and time after which to cancel in milliseconds.
38    final long interval = 20;
39    final long cancelTime = 110;
40
41    // Create the cancellable function.
42    CancellableFunctionExample example = new CancellableFunctionExample();
43    Runnable cancel = example.createCancellableFunction(task, interval);
44
45    // Set up cancellation to stop the function calls after a specified time.
46    new Timer().schedule(new TimerTask() {
47        @Override
48        public void run() {
49            cancel.run(); // Stop the repeated task execution.
50            // Output the results stored in the list.
51            for (Result result : results) {
52                System.out.println(result);
53            }
54        }
55    }, cancelTime);
56}
57
58// Class to represent individual results with time and value.
59class Result {
60    final long time;
61    final int returned;
62
63    Result(long time, int returned) {
64        this.time = time;
65        this.returned = returned;
66    }
67
68    @Override
69    public String toString() {
70        return "{ time: " + time + ", returned: " + returned + " }";
71    }
72}
73
74// The actual task class.
75class MultiplyTask implements Runnable {
76    private final int number;
77    private final List<Result> results;
78    private final long startTime;
79
80    MultiplyTask(int number, List<Result> results) {
81        this.number = number;
82        this.results = results;
83        this.startTime = System.currentTimeMillis();
84    }
85
86    @Override
87    public void run() {
88        // Calculate elapsed time.
89        long time = System.currentTimeMillis() - startTime;
90        // Perform the multiplication operation.
91        int returned = number * 2;
92        // Store the time and returned value in results.
93        results.add(new Result(time, returned));
94    }
95}
96
97class CancellableFunctionExample {
98  // Create a method similar to the JavaScript code provided
99}
100

1#include <chrono>
2#include <thread>
3#include <vector>
4#include <functional>
5#include <iostream>
6
7/**
8 * Creates a cancellable function that executes repetitively at a specified interval.
9 * @param fn - The function to be executed.
10 * @param args - The arguments to be passed to the function.
11 * @param interval - The time interval in milliseconds at which the function is to be executed.
12 * @return A function that, when invoked, stops the repeated execution.
13 */
14std::function<void()> cancellable(const std::function<void(int)>& fn, int arg, int interval) {
15    // Call the function with the provided argument immediately.
16    fn(arg);
17  
18    // Create a shared flag to control the cancellation from multiple contexts.
19    auto isCancelled = std::make_shared<bool>(false);
20  
21    // Set up a thread to call the function repeatedly at the given time interval.
22    std::thread t([fn, arg, interval, isCancelled]() {
23        while (!(*isCancelled)) {
24            std::this_thread::sleep_for(std::chrono::milliseconds(interval));
25            if (!(*isCancelled)) fn(arg);
26        }
27    });
28  
29    // Detach the thread to allow it to run independently.
30    t.detach();
31  
32    // Return a function that can be used to set the shared flag to stop the thread.
33    return [isCancelled]() { *isCancelled = true; };
34}
35
36int main() {
37    // Output vector to capture the results of the function calls.
38    std::vector<std::pair<long long, int>> result;
39
40    // The function to be repeatedly invoked, here to multiply its first argument by 2.
41    auto multiply = [](int x) -> int { return x * 2; };
42
43    // Arguments to the function, interval between function calls, and time after which to cancel.
44    int args = 4;
45    int interval = 20;
46    int cancelTime = 110;
47
48    // Record the start time of the operation.
49    auto startTime = std::chrono::steady_clock::now();
50
51    // A wrapped logging function that stores the time and result of each function call.
52    auto log = [&startTime, &result, &multiply](int arg) {
53        auto time = std::chrono::duration_cast<std::chrono::milliseconds>(
54            std::chrono::steady_clock::now() - startTime).count();
55        int returned = multiply(arg);
56        result.push_back({time, returned});
57    };
58
59    // Use the cancellable wrapper
60    auto cancel = cancellable(log, args, interval);
61
62    // Sleep to simulate the interval before cancelling the repeated function calls.
63    std::this_thread::sleep_for(std::chrono::milliseconds(cancelTime));
64
65    // Stop the repeated function execution.
66    cancel();
67
68    // Log the results stored in the output vector.
69    for (const auto& entry : result) {
70        std::cout << "Time: " << entry.first << " ms, Returned: " << entry.second << std::endl;
71    }
72
73    return 0;
74}
75

1/**
2 * Creates a cancellable function that executes repetitively at a specified interval.
3 * @param fn - The function to be executed.
4 * @param args - The arguments to be passed to the function.
5 * @param interval - The time interval in milliseconds at which the function is to be executed.
6 * @returns A cancel function that, when invoked, stops the repeated execution.
7 */
8function cancellable(fn: (...args: any[]) => void, args: any[], interval: number): () => void {
9    // Call the function with the provided arguments immediately.
10    fn(...args);
11
12    // Set up an interval to call the function repeatedly at the given time interval.
13    const timerId = setInterval(() => fn(...args), interval);
14
15    // Return a function that can be used to clear the interval and stop repeating the function.
16    return () => clearInterval(timerId);
17}
18
19// Example usage:
20
21// Output array to capture the results of the function calls.
22const result: Array<{ time: number; returned: number }> = [];
23
24// The function to be repeatedly invoked, here to multiply its first argument by 2.
25const multiply = (x: number) => x * 2;
26
27// Arguments to the function, interval between function calls, and time after which to cancel.
28const args = [4];
29const interval = 20;
30const cancelTime = 110;
31
32// A wrapped logging function that stores the time and result of each function call.
33const log = (...argsArr: any[]) => {
34    const time = Date.now() - startTime; // Calculate elapsed time.
35    const returned = multiply(...argsArr);
36    result.push({ time, returned }); // Store the time and returned value.
37};
38
39// Record the start time of the operation.
40const startTime = Date.now();
41
42// Use the cancellable wrapper
43const cancel = cancellable(log, args, interval);
44
45// Set up cancellation to stop the function calls after a certain time.
46setTimeout(() => {
47    cancel(); // Stop the repeated function execution.
48    console.log(result); // Log the results stored in the output array.
49}, cancelTime);
50

Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Combinatorial problemsRandom number generationTopological sortingMatrix multiplication

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the cancellable function mainly depends on the interval (setInterval) at which the provided function fn is repeatedly executed. Since fn is called every t milliseconds, and assuming that the function fn itself has a constant time complexity O(1), the total number of invocations of fn until the interval is cleared is approximately cancelT / t.

However, the complexity of setInterval cannot be considered in traditional time complexity terms because it's an asynchronous operation that depends on the runtime environment's event loop and task scheduling. If we consider the number of times fn is invoked as the measure of time complexity, then it can be expressed as O(cancelT / t).

In the example code, the setTimeout() callback just clears the interval and outputs the result, which operates in O(1) time since it's just cleanup and a single console.log operation.

Space Complexity

The space complexity of the function is O(1), as there is a fixed number of variables (time, fn, args, t) and no additional space that grows with the input size is allocated during the execution of the function. The space taken up by the interval ID, returned by setInterval, does not depend on the size of the input.

The console output or storing of results in an array, as shown in the example, will grow over time with O(cancelT / t) space complexity since it's adding a result every t milliseconds until cancelT milliseconds have passed. However, this isn't accounted for in the cancellable function itself, but rather in the external result array logic demonstrated in the example usage.

Note that the actual space complexity can be different if fn itself uses additional space from the args, but based on the given function (fn = (x) => x * 2) and execution in the example (which maintains constant space), we consider the cancellable function standalone without external side effects.

Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2725. Interval Cancellation

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings