Execute Asynchronous Functions in Parallel

#1641 Most AskedMedium

Execute Asynchronous Functions in Parallel #1641 Most Asked

Medium

3 views

Topics:

Arrays

Given an array of asynchronous functions functions, return a new promise promise. Each function in the array accepts no arguments and returns a promise. All the promises should be executed in parallel.

promise resolves:

When all the promises returned from functions were resolved successfully in parallel. The resolved value of promise should be an array of all the resolved values of promises in the same order as they were in the functions. The promise should resolve when all the asynchronous functions in the array have completed execution in parallel.

promise rejects:

When any of the promises returned from functions were rejected. promise should also reject with the reason of the first rejection.

Please solve it without using the built-in Promise.all function.

Example 1:

Input: functions = [
  () => new Promise(resolve => setTimeout(() => resolve(5), 200))
]
Output: {"t": 200, "resolved": [5]}
Explanation: 
promiseAll(functions).then(console.log); // [5]

The single function was resolved at 200ms with a value of 5.

Example 2:

Input: functions = [
    () => new Promise(resolve => setTimeout(() => resolve(1), 200)), 
    () => new Promise((resolve, reject) => setTimeout(() => reject("Error"), 100))
]
Output: {"t": 100, "rejected": "Error"}
Explanation: Since one of the promises rejected, the returned promise also rejected with the same error at the same time.

Example 3:

Input: functions = [
    () => new Promise(resolve => setTimeout(() => resolve(4), 50)), 
    () => new Promise(resolve => setTimeout(() => resolve(10), 150)), 
    () => new Promise(resolve => setTimeout(() => resolve(16), 100))
]
Output: {"t": 150, "resolved": [4, 10, 16]}
Explanation: All the promises resolved with a value. The returned promise resolved when the last promise resolved.

Constraints:

functions is an array of functions that returns promises
1 <= functions.length <= 10

Try coding it in LeetCode

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 are the possible return types and value ranges for the asynchronous functions?
What should happen if one or more of the asynchronous functions throws an error? Should I stop execution and return an error, or should I continue executing the other functions and aggregate the results/errors?
In what environment will these functions be executed (e.g., Node.js, browser)? This might affect available APIs.
Is there a maximum number of concurrent asynchronous operations I should be mindful of, or should I execute all functions at once?
What is the desired return value of the overall function? Should it be a list of the results of each asynchronous function, or something else?

Brute Force Solution

Approach

Imagine you have a group of tasks that can be done at the same time. The most basic way to handle them is to wait for each one, one after the other. It's like doing your chores by finishing one completely before even starting the next.

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

Start with the first task on your list.
Wait for it to finish completely before you do anything else.
Once it's done, move to the next task.
Again, wait for this task to be totally done.
Keep going through the list, finishing each task before starting the next one in order.
Do this until you have waited for and finished every single task.

Code Implementation

import asyncio

async def execute_asynchronous_functions_serially(asynchronous_functions):
    results = []

    # Iterate through each asynchronous function.
    for asynchronous_function in asynchronous_functions:
        # Wait for the completion of current asynchronous function before proceeding.
        result = await asynchronous_function()

        # Store the result after its completion.
        results.append(result)

    return results

Big(O) Analysis

Time Complexity

O(n) – The provided strategy describes sequential execution of asynchronous tasks. This means each of the 'n' tasks is executed one after the other. We wait for one task to complete before starting the next. Therefore, the time complexity is directly proportional to the number of tasks, 'n', resulting in O(n) time complexity, assuming each asynchronous function takes a constant amount of time to execute.

Space Complexity

O(1) – The provided description involves iterating through a list of tasks sequentially, waiting for each task to complete before moving on to the next. No auxiliary data structures like temporary lists, hash maps, or recursion are used. The space required is therefore constant, as it only involves managing the current task being processed, irrespective of the total number of tasks, N.

Optimal Solution

Approach

To run multiple tasks at the same time efficiently, we'll use a way to track when each task finishes. We will start all the tasks at once and then use a 'promise' which is like a placeholder that tells us when each is done, allowing us to know when *all* tasks are complete.

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

First, kick off all the asynchronous functions together. Think of this as starting all the racers in a race at the same time.
Then, create a list of 'promises', one for each of the functions. Each promise is essentially a pledge that a function will eventually finish.
Use a special command that waits for all of the promises to be resolved. This command will pause until every single asynchronous function has completed its work.
Once all the functions are done, the command returns with all of their results neatly packaged together, ready for you to use.
This ensures that you only proceed to the next step in your program after all the tasks have finished their work in the background.

Code Implementation

import asyncio

async def execute_async_functions_in_parallel(async_functions):
    # Create a list to hold the task objects
    tasks = []
    for async_function in async_functions:
        # Schedule each function to run concurrently
        task = asyncio.create_task(async_function())
        tasks.append(task)

    # Await all tasks to complete and gather the results
    # This ensures all functions finish before proceeding
    results = await asyncio.gather(*tasks)

    return results

async def main():
    async def async_function_one():
        await asyncio.sleep(1)
        return "Function One Result"

    async def async_function_two():
        await asyncio.sleep(2)
        return "Function Two Result"

    async def async_function_three():
        await asyncio.sleep(0.5)
        return "Function Three Result"

    async_functions_list = [async_function_one, async_function_two, async_function_three]

    # Run the asynchronous functions in parallel
    # This call triggers the concurrent execution
    results = await execute_async_functions_in_parallel(async_functions_list)

    print(results)

if __name__ == "__main__":
    # Run the main function using asyncio
    asyncio.run(main())

Big(O) Analysis

Time Complexity

O(n) – The algorithm initiates n asynchronous functions concurrently. Waiting for all n promises to resolve involves checking each promise's status once. Therefore, the time complexity is directly proportional to the number of functions (n), resulting in a linear time complexity of O(n). The key here is that the functions are executing in parallel, and we are only waiting for their completion, not iterating through them multiple times.

Space Complexity

O(N) – The algorithm creates a list of promises, where N is the number of asynchronous functions to be executed. This list stores a promise object for each function, requiring space proportional to N. After all functions complete, the command returns all of their results in a neatly packaged format; although the problem description mentions this, it isn't technically auxiliary space since those results are the output. Therefore, the dominant factor for space complexity is the list of promises with length N, which gives a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty array of functions	Return immediately, resolving the promise with an empty array since there's nothing to execute.
Array containing null or undefined functions	Filter out null or undefined elements to prevent errors during execution, or throw an error if null/undefined functions are not expected.
Functions that throw exceptions	Catch exceptions from individual functions, reject the main promise immediately, and log the error or continue executing other functions depending on requirements.
Functions that never resolve or reject (infinite loop)	Implement a timeout mechanism to reject promises that take too long, preventing the entire program from hanging indefinitely.
Maximum number of concurrent promises exceeding system limits	Utilize a concurrency limiter (e.g., a semaphore) to control the maximum number of promises running simultaneously.
Functions with different return types.	Ensure the return type is compatible or perform necessary type conversions before returning the aggregated results.
Functions with dependencies on each other.	This implementation assumes independent functions, and a dependency graph should be supported in a more complex version to execute in the correct order.
Large number of functions causing stack overflow if using recursion.	Avoid recursion by using iterative methods like for loops and/or manage the stack using a queue or other iterative approach.

Empty array of functions

How to Handle:

Return immediately, resolving the promise with an empty array since there's nothing to execute.

Array containing null or undefined functions

How to Handle:

Filter out null or undefined elements to prevent errors during execution, or throw an error if null/undefined functions are not expected.

Functions that throw exceptions

How to Handle:

Catch exceptions from individual functions, reject the main promise immediately, and log the error or continue executing other functions depending on requirements.

Functions that never resolve or reject (infinite loop)

How to Handle:

Implement a timeout mechanism to reject promises that take too long, preventing the entire program from hanging indefinitely.

Maximum number of concurrent promises exceeding system limits

How to Handle:

Utilize a concurrency limiter (e.g., a semaphore) to control the maximum number of promises running simultaneously.

Functions with different return types.

How to Handle:

Ensure the return type is compatible or perform necessary type conversions before returning the aggregated results.

Functions with dependencies on each other.

How to Handle:

This implementation assumes independent functions, and a dependency graph should be supported in a more complex version to execute in the correct order.

Large number of functions causing stack overflow if using recursion.

How to Handle:

Avoid recursion by using iterative methods like for loops and/or manage the stack using a queue or other iterative approach.