LeetCode 2715 - Timeout Cancellation

LeetCode Problem 2715

Difficulty: 🟢 Easy
Topics: —

Solution

Problem Understanding

This problem asks us to implement a cancellable delayed function execution mechanism. Essentially, you are given a function fn, an array of arguments args, and a timeout t in milliseconds. Your task is to return a cancel function cancelFn that, when invoked, can prevent the execution of fn if it has not already occurred.

The function fn is initially scheduled to execute after a delay of t milliseconds. If cancelFn is called before that delay elapses, the execution of fn must be canceled. If cancelFn is called after fn has already executed, it should have no effect. The inputs guarantee that fn is a valid function and args is an array with 1 to 10 elements, while t and cancelTimeMs are within practical ranges, so the function will only need to handle small delays.

Important edge cases include calling cancelFn exactly at the moment of execution, or cancelFn being scheduled with a delay greater than or less than t. These cases test that the mechanism correctly handles timing without prematurely invoking fn or failing to cancel it.

The output is technically the result of executing fn at the proper time, or nothing if canceled. This can be represented by returning the cancel function and allowing external logic (like setTimeout) to invoke it.

Approaches

A brute-force approach would involve repeatedly checking the time to see if t has elapsed and whether cancelFn has been called. This could involve busy-waiting in a loop, checking timestamps continuously, and then executing fn if the cancel flag is not set. While it is correct in theory, it is inefficient and unreliable in practice due to CPU usage and timing inaccuracy.

The optimal approach leverages JavaScript or equivalent asynchronous scheduling mechanisms like setTimeout. The insight is that JavaScript already provides delayed execution through timers, so we can simply schedule fn to execute after t milliseconds and store the timeout handle. If cancelFn is called before the timeout fires, we clear the timer to prevent execution. This approach is precise, efficient, and leverages built-in event loop mechanics.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(t)	O(1)	Repeatedly check time until t or cancel, inefficient
Optimal	O(1)	O(1)	Use a timer to schedule fn, cancel via clear timeout

Algorithm Walkthrough

1. Define a function cancellable that takes fn, args, and t as inputs. This will return the cancel function.
2. Inside cancellable, schedule fn to execute after t milliseconds using a timer (setTimeout in JS, threading.Timer in Python, time.AfterFunc in Go).
3. Store the handle or reference to the timer. This allows us to cancel it later.
4. Define cancelFn as a function that clears the scheduled timer if it exists. If the timer has already fired, fn has already executed, so the cancellation does nothing.
5. Return cancelFn from cancellable so that external code can invoke it according to cancelTimeMs.

Why it works: The invariant is that the timer is only active until either t milliseconds elapse or cancelFn is invoked. By leveraging the timer abstraction, we guarantee that fn executes exactly once if not canceled and never executes if canceled in time.

Python Solution

import threading
from typing import Any, Callable

def cancellable(fn: Callable, args: list[Any], t: int) -> Callable[[], None]:
    # Schedule the function to execute after t milliseconds
    timer = threading.Timer(t / 1000, lambda: fn(*args))
    timer.start()

    # Define the cancel function
    def cancel_fn() -> None:
        timer.cancel()  # Cancel the timer if it hasn't executed yet

    return cancel_fn

This implementation creates a threading.Timer that executes fn after t / 1000 seconds (Python timers use seconds). cancel_fn calls timer.cancel() to prevent the scheduled execution if it is invoked before the timer fires.

Go Solution

package main

import (
    "time"
)

func Cancellable(fn func(...any), args []any, t int) func() {
    timer := time.AfterFunc(time.Duration(t)*time.Millisecond, func() {
        fn(args...)
    })

    cancelFn := func() {
        timer.Stop() // Stop the timer if it hasn't executed
    }

    return cancelFn
}

In Go, time.AfterFunc schedules the execution of fn after t milliseconds. The returned cancelFn calls timer.Stop(), which prevents execution if the timer has not yet fired. Go requires args to be expanded using ... when calling a variadic function.

Worked Examples

Example 1: fn = x => x * 5, args = [2], t = 20, cancelTimeMs = 50

Time (ms)	Action
0	Schedule fn(2) after 20ms
20	fn(2) executes, result = 10
50	cancelFn called, timer already fired, no effect

Example 2: fn = x => x**2, args = [2], t = 100, cancelTimeMs = 50

Time (ms)	Action
0	Schedule fn(2) after 100ms
50	cancelFn called, timer stopped
100	fn does not execute

Example 3: fn = (x1, x2) => x1 * x2, args = [2, 4], t = 30, cancelTimeMs = 100

Time (ms)	Action
0	Schedule fn(2,4) after 30ms
30	fn(2,4) executes, result = 8
100	cancelFn called, no effect

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Scheduling the timer and defining cancelFn is constant time
Space	O(1)	Only a single timer object and function closure are stored

The complexity is minimal because we leverage built-in timer mechanisms. There is no loop or additional data structure usage.

Test Cases

# Provided examples
cancel_fn1 = cancellable(lambda x: x*5, [2], 20)
threading.Timer(0.05, cancel_fn1).start()  # cancel after 50ms

cancel_fn2 = cancellable(lambda x: x**2, [2], 100)
threading.Timer(0.05, cancel_fn2).start()  # cancel after 50ms

cancel_fn3 = cancellable(lambda x1, x2: x1*x2, [2,4], 30)
threading.Timer(0.1, cancel_fn3).start()  # cancel after 100ms

# Boundary case: immediate cancel
cancel_fn4 = cancellable(lambda x: x+1, [5], 50)
cancel_fn4()  # should cancel immediately

# Edge case: no arguments
cancel_fn5 = cancellable(lambda: 42, [], 50)
threading.Timer(0.02, cancel_fn5).start()

Test	Why
Example 1	Cancel occurs after execution, fn runs
Example 2	Cancel occurs before execution, fn does not run
Example 3	Cancel occurs after execution, fn runs
Immediate cancel	Tests zero-delay cancellation
No arguments	Tests function without parameters

Edge Cases

1. Immediate cancellation: If cancelFn is called immediately after creation, fn must never execute. Using timer.cancel() ensures that any scheduled timer is cleared, so this case is handled.
2. Cancel exactly at execution time: If cancelFn is invoked at the exact moment fn is scheduled to execute, there is a potential race condition. The timer implementations in Python and Go guarantee that either the cancel will prevent execution if called slightly before the firing, or fn executes if the timer has already fired. This aligns with the problem requirements.
3. Multiple arguments: Functions with multiple arguments need correct expansion. In Python, we use *args; in Go, we use args.... This ensures the function is invoked with all arguments provided, preventing type or argument errors.

This implementation is robust for all scenarios within the provided constraints.