Timeout Cancellation

Easy

Timeout Cancellation

Easy

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the timeout value (e.g., integer, float)? What are the minimum and maximum possible values for the timeout?
What should happen if the operation being timed out completes successfully before the timeout is reached? Do I still need to cancel the timeout or return any specific value?
Is the operation being timed out synchronous or asynchronous? How will I be notified when the operation either completes or is cancelled due to the timeout?
What mechanism should I use for setting and cancelling the timeout (e.g., a specific library or function)? Are there any restrictions on which mechanisms I can use?
If the cancellation fails (e.g., due to an unexpected error), should I throw an exception, return a specific error code, or log the error and continue?

Brute Force Solution

Approach

The brute force approach to timeout cancellation involves meticulously tracking every timeout that is set. When a cancellation is requested, we go through the entire list of timeouts to find the matching one. If found, we stop that specific timeout from running.

Here's how the algorithm would work step-by-step:

Every time a timeout is created, we write it down in a list.
When we want to cancel a timeout, we go through the entire list of timeouts we wrote down, one by one.
For each timeout in the list, we check if it's the one we want to cancel.
If it's the right timeout, we prevent it from executing its task.
If we go through the entire list without finding a match, it means there is nothing to cancel.

Code Implementation

import time

class TimeoutManager:
    def __init__(self):
        self.active_timeouts = []

    def set_timeout(self, function_to_run, delay_seconds):
        timeout_entry = {
            'function': function_to_run,
            'delay': delay_seconds,
            'scheduled_time': time.time() + delay_seconds,
            'cancelled': False
        }

        self.active_timeouts.append(timeout_entry)
        return timeout_entry

    def cancel_timeout(self, timeout_entry):
        # Iterate through all timeouts to find the one to cancel.
        for existing_timeout in self.active_timeouts:
            if existing_timeout == timeout_entry:
                # Mark the timeout as cancelled to prevent execution.
                existing_timeout['cancelled'] = True
                return

    def run_pending_timeouts(self):
        current_time = time.time()
        timeouts_to_remove = []

        for timeout_entry in self.active_timeouts:
            if timeout_entry['scheduled_time'] <= current_time and not timeout_entry['cancelled']:
                # This timeout is due and hasn't been cancelled, run it
                timeout_entry['function']()
                timeouts_to_remove.append(timeout_entry)

        # Clean up executed timeouts.
        for timeout_entry in timeouts_to_remove:
            self.active_timeouts.remove(timeout_entry)

if __name__ == '__main__':
    def my_function():
        print("Function executed after timeout!")

    manager = TimeoutManager()

    timeout1 = manager.set_timeout(my_function, 2)
    timeout2 = manager.set_timeout(lambda: print("Another timeout"), 5)

    time.sleep(1)
    # Cancel the first timeout.
    manager.cancel_timeout(timeout1)

    time.sleep(6)
    # Execute all pending timeouts to demonstrate the cancellation
    manager.run_pending_timeouts()

Big(O) Analysis

Time Complexity

O(n) – The brute force approach involves maintaining a list of timeouts. When a cancellation is requested, the algorithm iterates through this list to find the timeout to cancel. The size of this list is directly proportional to the number of timeouts created, which we denote as 'n'. Therefore, in the worst-case scenario, the algorithm needs to iterate through all 'n' timeouts to find the one to cancel. Hence the time complexity is O(n).

Space Complexity

O(N) – The described brute force approach involves storing every timeout that is created in a list. In the worst case, we might have N timeouts created, where N is the number of timeouts set before any cancellation. Therefore, we require a list of size N to keep track of these timeouts. This implies that the auxiliary space used grows linearly with the number of timeouts, leading to a space complexity of O(N).

Optimal Solution

Approach

The goal is to create a system that starts a task and allows you to stop it before it finishes if it takes too long. We will use a timer to keep track of how long the task has been running and a mechanism to signal that the task should stop.

Here's how the algorithm would work step-by-step:

First, start the timer when you begin the task.
While the task is running, keep checking if the timer has exceeded the allowed time.
If the time limit is reached, send a signal to stop the task. This is the 'cancellation'.
The task, upon receiving the stop signal, should halt what it's doing and clean up any resources it's using.
If the task finishes before the timer runs out, make sure to stop the timer to prevent it from triggering the cancellation signal unnecessarily.

Code Implementation

import time
import threading

class TimeoutCancellation:
    def __init__(self, timeout_duration):
        self.timeout_duration = timeout_duration
        self.task_thread = None
        self.stop_event = threading.Event()

    def start_task(self, task):
        self.stop_event.clear()
        self.task_thread = threading.Thread(target=self._run_with_timeout, args=(task,))
        self.task_thread.start()

    def _run_with_timeout(self, task):
        timer = threading.Timer(self.timeout_duration, self._signal_timeout)
        timer.start()

        try:
            task(self.stop_event)
            timer.cancel()
        except Exception as exception:
            print(f"Task raised an exception: {exception}")
        finally:
            timer.cancel()

    def _signal_timeout(self):
        # Set the stop event to signal the task to stop.
        self.stop_event.set()

class MyTask:
    def __call__(self, stop_event):
        # Simulate a task that might take a long time.
        for i in range(10):
            if stop_event.is_set():
                print("Task cancelled.")
                return
            print(f"Task running: {i}")
            time.sleep(1)
        print("Task completed.")

if __name__ == '__main__':
    timeout_duration_seconds = 3
    timeout_cancellation = TimeoutCancellation(timeout_duration_seconds)
    my_task = MyTask()
    print("Starting task...")
    timeout_cancellation.start_task(my_task)
    timeout_cancellation.task_thread.join()
    print("Task finished.")

Big(O) Analysis

Time Complexity

O(1) – The provided system primarily involves starting a timer, checking if a time limit has been reached, and signaling to stop a task. The timer operations (start, check, stop) and the signal sending are all constant time operations. The task itself, upon receiving the signal, should halt, but that halting process's complexity is not part of this analysis as it depends entirely on the nature of the specific task. Therefore, the operations directly related to the timeout cancellation mechanism have a time complexity of O(1).

Space Complexity

O(1) – The algorithm primarily uses a timer and a cancellation signal. The timer requires constant space to store the elapsed time. The cancellation signal also occupies constant space, whether it's a boolean flag or a similar mechanism. Since the space needed for the timer and cancellation signal remains constant regardless of the task's size or duration, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Timeout duration is zero or negative	Treat zero as execute immediately and negative as invalid, throw an error, or use a default positive timeout.
Callback function is null or undefined	Throw an IllegalArgumentException or TypeError immediately to prevent a NullPointerException later.
Calling clearTimeout with an invalid or already cleared timeout ID	Ignore the clearTimeout call or handle with grace by adding a simple check if the timeoutID exists, since this is a no-op.
Multiple timeouts created with the same callback	Each timeout needs a separate, unique ID and to be managed independently.
Timeout firing while the callback is already executing (re-entrancy)	Avoid re-entrancy by disabling or ignoring future timeout events until the callback completes.
System clock changes during timeout execution	Use a monotonic clock if available; otherwise be aware that time drift might cause unexpected timing.
Integer overflow when calculating the timeout expiration time	Use a data type capable of holding large time values, like long, and check for overflow during addition operations.
The process is paused or suspended during the timeout.	The timeout might not trigger when expected, consider using system calls that are robust against suspension and resume behavior.