Problem Description

This problem asks you to create a function that can schedule another function to run after a delay, but with the ability to cancel that scheduled execution.

You need to implement a function cancellable that takes three parameters:

• fn: A function to be executed
• args: An array of arguments to pass to fn
• t: A delay in milliseconds before fn should be executed

The cancellable function should return a cancel function (cancelFn). Here's how it works:

1. When cancellable is called, it schedules fn to be executed with the provided args after t milliseconds
2. The returned cancelFn can be called to cancel the scheduled execution
3. If cancelFn is called before the delay t expires, the execution of fn is cancelled and fn never runs
4. If cancelFn is not called within the delay t, then fn executes normally with the provided arguments

For example, if you schedule a function to run after 20ms but call the cancel function after 10ms, the original function never executes. However, if you schedule a function to run after 20ms and call the cancel function after 50ms, the original function will have already executed at the 20ms mark.

The solution uses JavaScript's setTimeout to schedule the delayed execution and clearTimeout to cancel it if needed. When cancellable is called, it creates a timer that will execute fn(...args) after t milliseconds and returns a function that, when called, clears this timer using clearTimeout(timer).

Intuition

The key insight here is recognizing that JavaScript provides built-in timer functions that perfectly match our requirements. When we need to delay execution of a function, setTimeout is the natural choice - it schedules a function to run after a specified delay and returns a timer ID.

The challenge is creating a cancellation mechanism. Fortunately, JavaScript's clearTimeout function allows us to cancel a scheduled timer using its ID. This creates a clean pattern: store the timer ID when scheduling the function, then provide a way to call clearTimeout with that ID.

The solution emerges from understanding closures in JavaScript. When we create the cancel function inside cancellable, it has access to the timer variable even after cancellable returns. This is crucial because:

1. We need to schedule the function immediately when cancellable is called
2. We need to return a cancel function that can be invoked later
3. That cancel function needs to know which timer to cancel

By storing the timer ID in a variable and returning a function that references it, we create a closure that preserves the connection between the scheduled execution and its cancellation mechanism. The returned function simply calls clearTimeout(timer) when invoked, which either cancels the pending execution (if called before t milliseconds) or does nothing (if the function has already executed).

This approach is elegant because it leverages JavaScript's event loop and timer system rather than trying to implement custom timing logic. The entire cancellation mechanism is just two lines: creating the timer with setTimeout and returning a function that clears it.

Solution Approach

The implementation is straightforward and leverages JavaScript's timer API:

1. Create a Timer: When cancellable is called, we immediately create a timer using setTimeout:

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

   This schedules the function fn to be executed with the spread arguments ...args after t milliseconds. The setTimeout function returns a timer ID that we store in the timer variable.

2. Return a Cancel Function: We return an arrow function that can cancel the scheduled execution:

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

   This returned function captures the timer variable through closure. When called, it invokes clearTimeout(timer) to cancel the scheduled execution.

The solution uses the following key patterns:

• Closure Pattern: The returned cancel function maintains access to the timer variable even after cancellable finishes executing. This allows the cancel function to reference the correct timer ID when it's called later.

• Arrow Function with Spread Operator: The expression () => fn(...args) creates a function that, when executed by the timer, calls fn with all the arguments from the args array spread out as individual parameters.

• Timer Management: The solution relies on the browser/Node.js event loop to handle the timing. setTimeout adds the function execution to the event queue after the specified delay, while clearTimeout removes it from the queue if it hasn't executed yet.

The beauty of this solution is its simplicity - it directly maps the problem requirements to JavaScript's built-in timer functions without any additional complexity. If clearTimeout is called before the timer expires, the scheduled function never runs. If the timer has already expired and the function has executed, calling clearTimeout has no effect (it's a no-op for expired or invalid timer IDs).

Example Walkthrough

Let's walk through a concrete example to understand how the solution works:

Scenario: We want to log a message after 100ms, but we might need to cancel it.

// Define our function to be delayed
const logMessage = (name, age) => {
    console.log(`${name} is ${age} years old`);
};

// Schedule the function to run after 100ms
const cancelFn = cancellable(logMessage, ["Alice", 25], 100);

What happens internally:

1. cancellable is called with our function, arguments, and delay
2. Inside cancellable, a timer is created:

   const timer = setTimeout(() => logMessage("Alice", 25), 100);
   // timer might be assigned ID: 123

3. A cancel function is returned that knows about timer ID 123

Case 1: Cancelling before execution (at 50ms)

// After 50ms, we decide to cancel
setTimeout(() => {
    cancelFn();  // Calls clearTimeout(123)
}, 50);

• At 50ms: cancelFn() executes, calling clearTimeout(123)
• The scheduled function is removed from the event queue
• At 100ms: Nothing happens - the message is never logged

Case 2: Cancelling after execution (at 150ms)

// After 150ms, we try to cancel (too late)
setTimeout(() => {
    cancelFn();  // Calls clearTimeout(123) but timer already fired
}, 150);

• At 100ms: Timer expires, logMessage("Alice", 25) executes
• Console shows: "Alice is 25 years old"
• At 150ms: cancelFn() executes but has no effect (timer already completed)

The key insight is that the cancel function maintains a reference to the timer ID through closure, allowing it to cancel the exact timer that was created, even when called much later.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The cancellable function performs a constant number of operations:

• One call to setTimeout which schedules a function execution
• Returns an arrow function that contains a single clearTimeout call

All these operations execute in constant time regardless of input size. The setTimeout itself only schedules the function and doesn't execute it immediately, so its scheduling operation is O(1).

Space Complexity: O(1)

The space usage is constant:

• One timer ID stored in the timer variable
• One closure created for the returned cancel function that captures the timer variable
• The function reference and arguments are stored but not copied (they're passed by reference)

The space doesn't grow with the size of the input. Even though args could be an array of any size, the function only stores a reference to it rather than creating a copy, so the space complexity remains constant with respect to the function itself.

Common Pitfalls

1. Thread Safety and Race Conditions

The most significant pitfall in the Python implementation is the lack of thread safety when multiple threads might access shared resources. If the fn function modifies shared state or if multiple cancellable functions are created and managed simultaneously, race conditions can occur.

Problem Example:

shared_counter = 0

def increment():
    global shared_counter
    temp = shared_counter
    time.sleep(0.001)  # Simulate some processing
    shared_counter = temp + 1

# Creating multiple cancellable functions
cancels = []
for i in range(10):
    cancel = cancellable(increment, [], 10)
    cancels.append(cancel)

Solution: Use thread-safe mechanisms like locks when dealing with shared resources:

import threading

lock = threading.Lock()
shared_counter = 0

def increment():
    global shared_counter
    with lock:
        temp = shared_counter
        time.sleep(0.001)
        shared_counter = temp + 1

2. Timer Already Expired Before Cancel

Calling cancel() after the timer has already executed doesn't raise an error, but developers might incorrectly assume the function didn't execute. This silent failure can lead to unexpected behavior.

Problem Example:

def important_operation():
    print("Operation executed!")
    # Perform critical operation
  
cancel = cancellable(important_operation, [], 100)
time.sleep(0.2)  # Wait 200ms
cancel()  # This does nothing - operation already executed at 100ms

Solution: Track execution state and provide feedback:

def cancellable_with_status(fn, args, t):
    delay_seconds = t / 1000.0
    executed = {'status': False}
  
    def wrapper():
        executed['status'] = True
        fn(*args)
  
    timer = threading.Timer(delay_seconds, wrapper)
    timer.start()
  
    def cancel():
        success = timer.cancel()
        if not success and executed['status']:
            print("Warning: Function already executed")
        return success
  
    return cancel

3. Resource Cleanup and Memory Leaks

Creating many timers without proper cleanup can lead to resource leaks, especially in long-running applications. Even cancelled timers consume resources until they're garbage collected.

Problem Example:

# Creating thousands of timers in a loop
for i in range(10000):
    cancel = cancellable(lambda x: x * 2, [i], 60000)  # 60 second delay
    # Forgetting to cancel unused timers

Solution: Implement a context manager or ensure proper cleanup:

class CancellableManager:
    def __init__(self):
        self.active_timers = []
  
    def create_cancellable(self, fn, args, t):
        delay_seconds = t / 1000.0
        timer = threading.Timer(delay_seconds, fn, args)
        timer.start()
        self.active_timers.append(timer)
      
        def cancel():
            if timer in self.active_timers:
                timer.cancel()
                self.active_timers.remove(timer)
      
        return cancel
  
    def cleanup_all(self):
        for timer in self.active_timers:
            timer.cancel()
        self.active_timers.clear()

4. Precision Issues with Small Delays

Python's threading.Timer isn't designed for high-precision timing. For very small delays (< 10ms), the actual execution time might vary significantly from the requested delay.

Problem Example:

# Expecting precise 1ms delay
cancel = cancellable(print_time, [], 1)  # 1ms delay
# Actual execution might happen after 5-15ms due to thread scheduling

Solution: For high-precision timing requirements, consider using alternative approaches:

import asyncio

async def cancellable_async(fn, args, t):
    task = asyncio.create_task(delayed_execution(fn, args, t))
  
    async def delayed_execution(fn, args, t):
        await asyncio.sleep(t / 1000.0)
        fn(*args)
  
    def cancel():
        task.cancel()
  
    return cancel