LeetCode 2650 - Design Cancellable Function

The problem asks us to implement a mechanism to run a generator that yields promises, with the additional ability to cancel the execution at any time.

leetcodehard

LeetCode Problem 2650

Difficulty: 🔴 Hard
Topics: —

Solution

Problem Understanding

The problem asks us to implement a mechanism to run a generator that yields promises, with the additional ability to cancel the execution at any time. The key task is to manage the generator’s asynchronous execution in a way that each yielded promise is awaited and its result sent back into the generator. If any promise rejects, the error must be thrown back into the generator, which can optionally handle it.

The function cancellable returns a tuple: a cancel function and a promise. The cancel function, when invoked, should inject a "Cancelled" error into the generator. If the generator catches it, execution may continue; if uncaught, the returned promise rejects immediately. The promise returned by cancellable resolves with the generator’s return value or rejects with the first uncaught error thrown by the generator, including a cancellation.

Inputs are always generator objects that yield promises. The generator may immediately return, yield multiple promises sequentially, or throw errors. The generator may also catch errors internally, allowing partial results to be returned upon cancellation. The constraints ensure we only need to handle generators yielding promises, and cancellations occur within a reasonable timeframe (0 ≤ cancelledAt ≤ 1000).

Important edge cases include: generators that immediately return, generators that throw immediately, cancellation happening mid-promise, and errors caught within the generator versus uncaught.

Approaches

The brute-force approach would be to sequentially consume the generator manually using .next() and .throw(), awaiting each promise before continuing. On cancellation, we could throw the "Cancelled" error directly. While this would work functionally, managing asynchronous sequencing manually can become verbose and error-prone. This approach essentially mimics what async/await already does, but without a clean abstraction.

The optimal approach uses a recursive nextStep function that handles each promise resolution or rejection and propagates the result into the generator. We maintain a flag for cancellation, so if cancel() is invoked, we immediately throw the cancellation error into the generator. This approach guarantees correct handling of promise resolution, rejections, and caught exceptions without extra bookkeeping beyond a simple flag.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Sequentially iterate generator and manually handle promise resolution
Optimal O(n) O(1) Recursively handle yielded promises with cancellation flag and propagate errors correctly

Algorithm Walkthrough

  1. Initialize a cancelled flag to false to track whether the cancel function has been invoked.
  2. Define a cancel function that sets cancelled = true.
  3. Define an asynchronous function nextStep(value, isError) which takes the next value to send into the generator and a flag indicating whether it should be thrown as an error.
  4. Inside nextStep, call either generator.next(value) or generator.throw(value) depending on isError.
  5. If the generator is done, resolve the outer promise with its return value.
  6. If the generator yields a promise, attach .then() and .catch() handlers:
  • On .then(), recursively call nextStep with the resolved value.
  • On .catch(), recursively call nextStep with the error and isError=true.
  1. Before resuming, check the cancelled flag. If set, call nextStep("Cancelled", true). If the generator catches it, continue; otherwise, reject the promise.
  2. Return a tuple [cancel, promise], where promise wraps the first call to nextStep() and resolves/rejects appropriately.

Why it works: At any time, the generator only processes one promise at a time. Errors, including cancellation, propagate correctly either as exceptions or resolved values depending on whether the generator handles them. This guarantees that the final returned promise always reflects the correct final state.

Python Solution

from typing import Any, Tuple, Callable, Generator
import asyncio

def cancellable(generator: Generator) -> Tuple[Callable[[], None], asyncio.Future]:
    cancelled = False
    loop = asyncio.get_event_loop()
    result_future = loop.create_future()

    def cancel():
        nonlocal cancelled
        cancelled = True

    async def next_step(value: Any = None, is_error: bool = False):
        nonlocal cancelled
        try:
            if is_error:
                yielded = generator.throw(value)
            else:
                yielded = generator.send(value) if value is not None else next(generator)
        except StopIteration as e:
            if not result_future.done():
                result_future.set_result(e.value)
            return
        except Exception as e:
            if not result_future.done():
                result_future.set_exception(e)
            return

        if cancelled:
            await next_step("Cancelled", True)
            return

        try:
            result = await yielded
            await next_step(result, False)
        except Exception as e:
            await next_step(e, True)

    asyncio.ensure_future(next_step())
    return cancel, result_future

This implementation first defines a cancel function that sets a flag. The next_step function manages sending values or throwing errors into the generator. Each yielded promise is awaited. If cancellation occurs, "Cancelled" is thrown into the generator. The outer Future is resolved or rejected once the generator finishes or throws an uncaught exception.

Go Solution

package main

import (
    "errors"
    "sync"
)

type Generator interface {
    Next(interface{}) (interface{}, bool, error)
    Throw(error) (interface{}, bool, error)
}

func Cancellable(generator Generator) (func(), chan interface{}) {
    cancelled := false
    var mu sync.Mutex
    done := make(chan interface{}, 1)

    cancel := func() {
        mu.Lock()
        cancelled = true
        mu.Unlock()
    }

    go func() {
        var value interface{}
        var isErr bool
        for {
            mu.Lock()
            if cancelled {
                value, isErr, _ = generator.Throw(errors.New("Cancelled"))
                cancelled = false
            } else if isErr {
                value, isErr, _ = generator.Throw(value.(error))
            } else {
                value, isErr, _ = generator.Next(value)
            }
            mu.Unlock()

            if !isErr {
                done <- value
                return
            }
        }
    }()

    return cancel, done
}

In Go, we use a Generator interface with Next and Throw methods. A goroutine sequentially handles yielded values and errors. A mutex ensures safe access to the cancelled flag. The done channel carries the final resolved value.

Worked Examples

Example 3: Cancellation mid-promise

Time Operation Generator State Notes
0ms Start generator Yield promise for 200ms Execution suspended
100ms cancel() called cancelled=True next_step throws "Cancelled"
100ms next_step called Generator receives "Cancelled" If uncaught, promise rejects
200ms Original promise resolves Ignored, generator already cancelled Final promise rejected

Example 5: Cancellation caught

Time Operation Generator State Result
0-100ms Yield sleep promise Execution continues result=0
100ms Yield res(1) result+=1 result=1
150ms cancel() called Generator catches "Cancelled" Returns result=1
150ms+ Final promise resolves 1 Promise resolves with partial computation

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each yielded promise is awaited exactly once; n = number of yields
Space O(1) No extra structures besides cancellation flag and async stack

The complexity is linear in the number of yields, since we await each promise exactly once, and we use constant extra space aside from the call stack of async calls.

Test Cases

import asyncio

# Example 1
gen1 = (i for i in [42])
cancel1, promise1 = cancellable(gen1)
asyncio.run(promise1)  # resolves 42

# Example 3
async def tasks3():
    yield asyncio.sleep(0.2)
    return "Success"
gen3 = tasks3()
cancel3, promise3 = cancellable(gen3)
asyncio.get_event_loop().call_later(0.1, cancel3)
try:
    asyncio.run(promise3)
except Exception as e:
    assert str(e) == "Cancelled"  # cancelled mid-promise

# Example 5
async def tasks5():
    result = 0
    try:
        await asyncio.sleep(0.1)
        result += 1
        await asyncio.sleep(0.1)
        result += 1
    except Exception:
        return result
    return result

gen5 = tasks5()
cancel5, promise5 = cancellable(gen5)
asyncio.get_event_loop().call_later(0.15, cancel5)
assert asyncio.run(promise5) == 1
Test Why
Immediate return Ensures generator resolving immediately works
Cancellation mid-promise Validates "Cancelled" error propagation
Cancellation caught Checks partial result resolution

Edge Cases

One edge case is a generator that yields a promise which immediately rejects. Our implementation correctly propagates this error back into the generator using generator.throw() so that any try/catch