LeetCode 2725 - Interval Cancellation

This problem asks us to implement a function cancellable that repeatedly calls a given function fn with a set of arguments args at a fixed interval t milliseconds and allows this repeated execution to be stopped by a cancel function cancelFn.

leetcodeeasy

LeetCode Problem 2725

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to implement a function cancellable that repeatedly calls a given function fn with a set of arguments args at a fixed interval t milliseconds and allows this repeated execution to be stopped by a cancel function cancelFn. The first call to fn happens immediately (at time 0), and subsequent calls occur every t milliseconds. After a specified time, cancelTimeMs, the returned cancelFn is invoked, which stops further calls to fn.

The inputs are:

  • fn: a function that can accept 1 to 10 arguments. It is the function to be invoked repeatedly.
  • args: an array of arguments to pass to fn on each call.
  • t: the interval in milliseconds between successive function calls.

The output is a function cancelFn that stops the interval when invoked. The problem focuses on simulating interval behavior, ensuring the timing is correct, and guaranteeing that no calls happen after cancellation.

Constraints give us a bounded range for t and cancelTimeMs, meaning we do not need to handle extremely high frequencies or durations. Edge cases that could trip up a naive implementation include cancelling immediately, having cancelTimeMs that is not a multiple of t, and functions with multiple arguments.

Approaches

Brute Force Approach

A brute force implementation would repeatedly call fn using a setInterval in JavaScript or a loop with sleep in other languages until the time elapsed reaches cancelTimeMs. This works because you can manually track elapsed time and stop the interval after the cancel time. However, this approach is inefficient for languages that do not handle accurate timing in tight loops and could be error-prone if timing drift occurs.

Optimal Approach

The key insight is that JavaScript (or equivalent environments) already provides a native mechanism to handle repeated function calls (setInterval) and cancellation (clearInterval). By using setInterval for periodic execution and returning a function that calls clearInterval, we get a clean and accurate implementation. The first call is executed immediately before starting the interval.

Approach Time Complexity Space Complexity Notes
Brute Force O(cancelTimeMs / t) O(1) Manually track elapsed time and call fn repeatedly until cancel
Optimal O(cancelTimeMs / t) O(1) Use setInterval and clearInterval to handle timing and cancellation

Algorithm Walkthrough

  1. Define the function cancellable with parameters fn, args, and t.
  2. Call fn immediately with the given arguments and store the returned value if needed.
  3. Use setInterval to schedule repeated execution of fn every t milliseconds.
  4. Inside the interval callback, call fn with the provided arguments.
  5. Return a cancelFn function that calls clearInterval on the interval to stop further calls.
  6. When cancelFn is invoked (via setTimeout or manually), the repeated execution halts.

Why it works: The invariant is that fn is always called immediately and then periodically every t milliseconds. Using setInterval ensures the timing is consistent, and returning a function that calls clearInterval guarantees we can cancel at any moment.

Python Solution

from typing import Any, Callable

def cancellable(fn: Callable[..., Any], args: list[Any], t: int) -> Callable[[], None]:
    import threading

    # Call fn immediately
    fn(*args)

    # Create an event to signal cancellation
    stop_event = threading.Event()

    def interval_runner():
        while not stop_event.is_set():
            threading.Event().wait(t / 1000)  # convert ms to seconds
            if stop_event.is_set():
                break
            fn(*args)

    # Start the interval in a separate thread
    thread = threading.Thread(target=interval_runner)
    thread.daemon = True
    thread.start()

    # Return the cancel function
    def cancel_fn():
        stop_event.set()
        thread.join()  # ensure the thread finishes cleanly

    return cancel_fn

The Python implementation uses a background thread to simulate setInterval behavior. The first call happens immediately. A threading.Event is used to signal cancellation safely. The cancel_fn stops the loop and joins the thread to clean up resources.

Go Solution

package main

import (
    "time"
)

func Cancellable(fn func(...interface{}), args []interface{}, t int) func() {
    ticker := time.NewTicker(time.Duration(t) * time.Millisecond)
    done := make(chan struct{})

    // Call fn immediately
    fn(args...)

    // Start a goroutine to handle periodic calls
    go func() {
        for {
            select {
            case <-ticker.C:
                fn(args...)
            case <-done:
                ticker.Stop()
                return
            }
        }
    }()

    // Return the cancel function
    return func() {
        close(done)
    }
}

The Go implementation uses a time.Ticker to schedule periodic execution and a channel to signal cancellation. Calling the returned function closes the channel, which stops the goroutine and halts the ticker.

Worked Examples

Example 1

fn = (x) => x * 2
args = [4]
t = 35
cancelTimeMs = 190
Time (ms) Action Result
0 Call fn(4) 8
35 Call fn(4) 8
70 Call fn(4) 8
105 Call fn(4) 8
140 Call fn(4) 8
175 Call fn(4) 8
190 Cancel interval stop

The function is called immediately and then every 35ms until cancellation.

Example 2

fn = (x1, x2) => x1 * x2
args = [2, 5]
t = 30
cancelTimeMs = 165
Time (ms) Action Result
0 Call fn(2, 5) 10
30 Call fn(2, 5) 10
60 Call fn(2, 5) 10
90 Call fn(2, 5) 10
120 Call fn(2, 5) 10
150 Call fn(2, 5) 10
165 Cancel interval stop

Complexity Analysis

Measure Complexity Explanation
Time O(cancelTimeMs / t) The function is called once immediately and then approximately cancelTimeMs / t times
Space O(1) Only a small amount of state is stored for interval/cancellation

The complexity is proportional to the number of times the function is executed. Memory usage is constant outside of system-managed threads or goroutines.

Test Cases

# Example 1
cancel = cancellable(lambda x: x*2, [4], 35)
import time
time.sleep(0.19)  # 190ms
cancel()  # cancel the interval

# Example 2
cancel = cancellable(lambda x1, x2: x1*x2, [2,5], 30)
time.sleep(0.165)
cancel()

# Example 3
cancel = cancellable(lambda x1, x2, x3: x1+x2+x3, [5,1,3], 50)
time.sleep(0.18)
cancel()

# Edge case: cancel immediately
cancel = cancellable(lambda x: x, [10], 50)
cancel()
Test Why
Example 1 Validates repeated calls and cancellation timing
Example 2 Checks multiple arguments
Example 3 Checks non-multiples of t vs cancelTimeMs
Immediate cancel Ensures no extra calls occur

Edge Cases

One important edge case is immediate cancellation. If cancelFn is invoked right after creation, the function should not execute more than the initial immediate call. This is handled by checking the stop condition before each subsequent interval execution.

Another edge case is when cancelTimeMs is not a multiple of t. The last call to fn before cancellation should still occur. Both implementations account for this by letting the interval continue until cancelFn is called.

Finally, functions with the maximum number of arguments (10) must be handled. The implementations support this via variadic argument unpacking in Python and Go. This ensures correctness regardless of the number of arguments.