2795. Parallel Execution of Promises for Individual Results Retrieval

Medium

Problem Description

In this problem, we're given an array called functions. Each element of this array is a function that, when called, returns a promise (fnPromise). These promises can either resolve successfully (fulfilled) or fail to resolve (rejected).

We need to write a function promiseAllSettled that receives the functions array as its input and returns a single promise (promise). This promise should ultimately resolve to an array of objects, with each object representing the outcome of one fnPromise. The array should maintain the same order as the input functions in the functions array.

The object for a fulfilled fnPromise should have a format:

status: "fulfilled"
value: result (where result is the resolved value of the fnPromise)

And the object for a rejected fnPromise should have a format:

status: "rejected"
reason: error (where error is the error message obtained when the fnPromise is rejected)

The challenge also specifically requests that we should not use the built-in Promise.allSettled() method to accomplish this task.

Intuition

The core idea of our solution is to treat each function (which returns a promise) independently and keep track of each promise's outcome. This involves mapping each function to a promise that will always resolve—regardless of whether the original promise resolves or rejects. We do this because our main goal is to capture the fulfillment status and value or the rejection reason for every individual promise.

We iterate over the functions array and for each function, we invoke it to get the fnPromise. Then, we attach both .then and .catch handlers to understand if the fnPromise has been fulfilled or rejected. Each of these handlers returns an object with the status and the corresponding value or reason. This aligns with the format required by our problem statement.

To construct the final array that the promise will resolve with, we keep an array res. We place the result object from either the .then or .catch handler into the res array at the same index position as the original function in the functions array. This ensures we maintain the order.

We also keep a count of how many promises have settled (either resolved or rejected). Once this count matches the length of the functions array, we know all fnPromises have been settled, and we can resolve the outermost promise with the res array as its value.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The implementation of promiseAllSettled function involves several steps. Let's break them down:

Initialization: We start by creating a new Promise object that will eventually be returned by the promiseAllSettled function. This outer promise resolves when all the individual fnPromises inside the functions array have settled.
Creating Result Array: We set up an array, res, that will accumulate the results of our promise settlements. It's crucial for this to be an array since we want to maintain the order of the results relative to the order of functions in the functions array.
Iteration: We use a for loop to iterate over the functions array, denoted by the loop variable i. It's important to note that we're using a for...in loop, which iterates over the enumerable properties of the array (in this case, the indices).
Executing Functions and Handling Promises: For each functions[i], we call it to obtain a fnPromise. We then attach a .then callback, which is used for a case where the fnPromise resolves successfully. The .then callback returns an object with status: 'fulfilled' and value as the resolved value of the promise.

Likewise, we attach a .catch callback for the case where the fnPromise rejects. The .catch handler returns an object with status: 'rejected' and reason as the error message. Since .catch is chained after .then, an error will bypass the .then and be caught by the .catch.
Storing Results: The result object obtained from either the .then or .catch is placed into the res array at the position matching the functions array. This step uses i, which represents the current index in the functions array, to ensure the result order is the same as the input function order.
Tracking Completion: We maintain a count of how many functions have settled. Each time a function settles (either resolved or rejected), we increment the count. When count matches the length of the functions array, we know all promises have settled and we can resolve the outer promise with the res array.

The use of .then and .catch chained properly ensures that even if a promise rejects, it's converted into a resolve for our outer promise, so that a single rejection doesn't cause the whole process to stop. Instead, it's treated as a regular outcome and managed accordingly.

By only resolving after all promises have settled, we emulate the behavior of Promise.allSettled without using it directly. This allows us to gather all results and understand whether each individual promise was fulfilled or rejected.

In summary, the algorithm capitalizes on the asynchronous nature of promises in JavaScript, handling them independently and aggregating their results in a way that maintains their original order.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which technique can we use to find the middle of a linked list?

Fast-slow pointersTwo pointers moving in opposite directionBinary searchDepth first search

I don’t know

Example Walkthrough

Let's consider an example where we have three functions in our functions array: fn1, fn2, and fn3. Function fn1 resolves immediately, fn2 rejects after a delay, and fn3 resolves after a delay.

1const fn1 = () => Promise.resolve('Result of fn1');
2const fn2 = () => new Promise((_, reject) => setTimeout(() => reject('Error in fn2'), 100));
3const fn3 = () => new Promise(resolve => setTimeout(() => resolve('Result of fn3'), 100));
4
5const functions = [fn1, fn2, fn3];

We call promiseAllSettled(functions) to process these functions. Let's walk through what happens step by step following the solution approach:

Initialization: A new Promise is created which will be returned by promiseAllSettled. This will resolve after all fnPromises from functions have settled.
Creating Result Array: An empty array res is created to accumulate results.
Iteration: A for loop (or similar iteration mechanism) iterates over the indices of functions.
Executing Functions and Handling Promises:
- fn1 is called, returning a promise that resolves immediately. The .then callback fires and creates a result object: {status: 'fulfilled', value: 'Result of fn1'}. The .catch is not invoked because there's no error.
- fn2 is called, producing a promise that will reject after 100ms. When it rejects, the .catch handler fires and creates a result object: {status: 'rejected', reason: 'Error in fn2'}.
- fn3 is called, returning a promise that resolves after 100ms. Once it resolves, the .then callback creates a result object: {status: 'fulfilled', value: 'Result of fn3'}.
Storing Results: The objects created in the last step are placed into the res array. After all callbacks have been executed, res looks like this:

1[
2    { status: 'fulfilled', value: 'Result of fn1' },
3    { status: 'rejected',  reason: 'Error in fn2' },
4    { status: 'fulfilled', value: 'Result of fn3' }
5]

Tracking Completion: We keep a count of settled functions. In our case, every function call will eventually trigger its respective .then or .catch handler, incrementing the count. Once count is equal to functions.length (3 in this case), we resolve the outer promise with the res array.

After waiting for all promises to settle, promiseAllSettled returns a promise that resolves to res, maintaining the order of functions. As such, the final result for promiseAllSettled(functions) would be:

1[
2    { status: 'fulfilled', value: 'Result of fn1' },
3    { status: 'rejected', reason: 'Error in fn2' },
4    { status: 'fulfilled', value: 'Result of fn3' }
5]

This example clearly illustrates how the solution approach operates. Even though fn2 fails, fn1 and fn3 still contribute their results, and we end up with an array describing the status of each promise as per the original order in the functions array.

Solution Implementation

1import asyncio
2
3# Define Python classes for both fulfilled and rejected promise outcomes.
4class FulfilledObj:
5    def __init__(self, value):
6        self.status = 'fulfilled'
7        self.value = value
8
9class RejectedObj:
10    def __init__(self, reason):
11        self.status = 'rejected'
12        self.reason = reason
13
14# Union type hint for a resolved promise outcome, which can be either fulfilled or rejected.
15Outcome = FulfilledObj | RejectedObj
16
17# Function that simulates promiseAllSettled for an array of coroutines.
18# It returns a list of objects indicating the outcome of each coroutine.
19async def promise_all_settled(functions):
20    # List to hold the outcomes of each coroutine.
21    results = [None] * len(functions)
22    # Control flow task for fulfilling all coroutines.
23    tasks = []
24
25    # Handle fulfilled coroutine.
26    async def handle_fulfilled(index, coro):
27        try:
28            value = await coro
29            results[index] = FulfilledObj(value)
30        except Exception as e: # Replace Exception by a more specific exception class if possible
31            results[index] = RejectedObj(e)
32
33    # Iterate through the coroutine list and schedule each coroutine.
34    for index, func in enumerate(functions):
35        task = asyncio.create_task(handle_fulfilled(index, func()))
36        tasks.append(task)
37
38    # Await all scheduled tasks to be finished.
39    await asyncio.gather(*tasks)
40    return results
41
42# Example usage of the `promise_all_settled` function.
43# Uncomment the following code to test the functionality.
44"""
45async def main():
46    functions = [
47        lambda: asyncio.sleep(0.1, result='Result')
48    ]
49
50    # A simple timer to measure elapsed time.
51    start_time = asyncio.get_event_loop().time()
52
53    results = await promise_all_settled(functions)
54
55    elapsed_time = asyncio.get_event_loop().time() - start_time
56    output = {'elapsed': elapsed_time, 'values': results}
57    print(output)  # Expected output with an elapsed time close to 0.1 and the 'Result'
58
59# Run the example
60asyncio.run(main())
61"""
62

1import java.util.concurrent.CompletableFuture;
2import java.util.concurrent.ExecutionException;
3import java.util.function.Supplier;
4import java.util.List;
5import java.util.ArrayList;
6
7// Java does not have type unions like TypeScript, so we use an interface with subclasses for fulfilled and rejected promise outcomes.
8interface ResultObj {}
9class FulfilledObj implements ResultObj {
10    String status;
11    Object value;
12  
13    public FulfilledObj(Object value) {
14        this.status = "fulfilled";
15        this.value = value;
16    }
17}
18class RejectedObj implements ResultObj {
19    String status;
20    Object reason;
21  
22    public RejectedObj(Object reason) {
23        this.status = "rejected";
24        this.reason = reason;
25    }
26}
27
28public class PromiseAllSettled {
29
30    // Function that simulates Promise.allSettled for an array of suppliers that return CompletableFuture.
31    // It returns a CompletableFuture that resolves to a list of objects indicating the outcome of each CompletableFuture.
32    public static CompletableFuture<List<ResultObj>> promiseAllSettled(List<Supplier<CompletableFuture<Object>>> suppliers) {
33        // List to hold the outcomes of each CompletableFuture.
34        List<CompletableFuture<ResultObj>> futures = new ArrayList<>();
35    
36        // Convert each supplier to a CompletableFuture and handle its resolution accordingly.
37        for (Supplier<CompletableFuture<Object>> supplier : suppliers) {
38            CompletableFuture<ResultObj> future = supplier.get()
39                    .thenApply(value -> new FulfilledObj(value))
40                    .exceptionally(ex -> new RejectedObj(ex));
41            futures.add(future);
42        }
43    
44        // Combine all CompletableFuture instances into a single CompletableFuture that will be resolved when all are completed.
45        CompletableFuture<Void> allDoneFuture = CompletableFuture.allOf(futures.toArray(new CompletableFuture[0]));
46    
47        // Return a CompletableFuture that resolves to a list of ResultObj instances representing the outcome of each.
48        return allDoneFuture.thenApply(v -> {
49            List<ResultObj> results = new ArrayList<>();
50            futures.forEach(f -> {
51                try {
52                    results.add(f.get());
53                } catch (InterruptedException | ExecutionException e) {
54                    // This should never happen since we're calling get after all futures are done.
55                    throw new RuntimeException(e);
56                }
57            });
58            return results;
59        });
60    }
61
62    // Example usage of the `promiseAllSettled` function.
63    public static void main(String[] args) throws ExecutionException, InterruptedException {
64        List<Supplier<CompletableFuture<Object>>> suppliers = new ArrayList<>();
65        suppliers.add(() -> CompletableFuture.supplyAsync(() -> {
66            // Simulate a task that takes some time to complete
67            try {
68                Thread.sleep(100);
69            } catch (InterruptedException e) {
70                e.printStackTrace();
71            }
72            return "Result";
73        }));
74
75        CompletableFuture<List<ResultObj>> promise = promiseAllSettled(suppliers);
76
77        // Start timing
78        long startTime = System.currentTimeMillis();
79
80        // When all CompletableFutures are settled, print the outcome.
81        promise.thenAccept(res -> {
82            long elapsedTime = System.currentTimeMillis() - startTime;
83            System.out.println("Elapsed time: " + elapsedTime + "ms");
84            for (ResultObj obj : res) {
85                if (obj instanceof FulfilledObj) {
86                    FulfilledObj fulfilled = (FulfilledObj) obj;
87                    System.out.println("Status: " + fulfilled.status + ", Value: " + fulfilled.value.toString());
88                } else if (obj instanceof RejectedObj) {
89                    RejectedObj rejected = (RejectedObj) obj;
90                    System.out.println("Status: " + rejected.status + ", Reason: " + rejected.reason.toString());
91                }
92            }
93        }).get(); // Waiting for completion to ensure that the results are printed out.
94    }
95}
96

1#include <future>
2#include <vector>
3#include <functional>
4#include <iostream>
5#include <chrono>
6
7// Define C++ equivalent types for both fulfilled and rejected future outcomes.
8struct FulfilledObj {
9    std::string status = "fulfilled";
10    std::shared_ptr<void> value; // Using shared_ptr for type-erased generic value
11};
12
13struct RejectedObj {
14    std::string status = "rejected";
15    std::string reason; // Assuming the reason will be string for simplicity
16};
17
18// Union-like structure that can hold either outcome.
19struct OutcomeObj {
20    std::string status;
21    std::shared_ptr<void> value; // For 'fulfilled'
22    std::string reason;          // For 'rejected'
23};
24
25// Function that simulates Promise.allSettled for an array of functions that return futures.
26// This function will return a future that resolves to a vector of OutcomeObj, representing each promise's outcome.
27std::future<std::vector<OutcomeObj>> promiseAllSettled(
28    const std::vector<std::function<std::future<void>()>>& functions) {
29
30    return std::async(std::launch::async, [functions]{
31        std::vector<OutcomeObj> outcomes;
32        // Reserve space for outcome objects based on the number of input functions.
33        outcomes.reserve(functions.size());
34      
35        // Iterate through the function array and execute each function.
36        for (const auto& func : functions) {
37            // Attempt to fulfill the future and handle the outcome accordingly.
38            try {
39                // Wait for the future to complete and store a FulfilledObj.
40                std::shared_ptr<void> result = func().get();
41                outcomes.push_back(OutcomeObj{"fulfilled", result, ""});
42            }
43            catch (const std::exception& e) {
44                // If an exception is thrown, store a RejectedObj.
45                outcomes.push_back(OutcomeObj{"rejected", nullptr, e.what()});
46            }
47        }
48      
49        // All futures are settled at this point, return the outcomes.
50        return outcomes;
51    });
52}
53
54// Example usage of the `promiseAllSettled` function.
55int main() {
56    // Create a vector of functions that return futures.
57    std::vector<std::function<std::future<void>()>> functions = {
58        // Example function that fulfills the future after a delay.
59        [] {
60            return std::async(std::launch::async, [] {
61                std::this_thread::sleep_for(std::chrono::milliseconds(100));
62                // In this example, return type is void. Type erasure can be done to hold any type.
63                return;
64            });
65        }
66    };
67
68    // Record start time.
69    auto startTime = std::chrono::high_resolution_clock::now();
70
71    // Call `promiseAllSettled` and wait for all futures to settle.
72    auto outcomesFuture = promiseAllSettled(functions);
73    outcomesFuture.wait(); // Wait for all futures to complete.
74  
75    // Calculate the elapsed time.
76    auto endTime = std::chrono::high_resolution_clock::now();
77    auto elapsedTime = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime).count();
78
79    // Retrieve the outcomes and print the results.
80    std::vector<OutcomeObj> outcomes = outcomesFuture.get();
81    for (const auto& outcome : outcomes) {
82        if (outcome.status == "fulfilled") {
83            std::cout << "{\"status\":\"" << outcome.status << "\",\"value\":\"Result\"}" << std::endl;
84        } else {
85            std::cout << "{\"status\":\"" << outcome.status << "\",\"reason\":\"" << outcome.reason << "\"}" << std::endl;
86        }
87    }
88
89    std::cout << "Elapsed Time: " << elapsedTime << "ms\n";
90    return 0;
91}
92

1// Define TypeScript types for both fulfilled and rejected promise outcomes.
2type FulfilledObj = {
3    status: 'fulfilled';
4    value: unknown;
5};
6type RejectedObj = {
7    status: 'rejected';
8    reason: unknown;
9};
10type Obj = FulfilledObj | RejectedObj;
11
12// Function that simulates Promise.allSettled for an array of functions that return promises.
13// It returns a Promise that resolves to an array of objects indicating the outcome of each promise.
14function promiseAllSettled(functions: (() => Promise<unknown>)[]): Promise<Obj[]> {
15    return new Promise(resolve => {
16        // Array to hold the outcomes of each promise.
17        const results: Obj[] = [];
18        // Counter to keep track of resolved promises.
19        let completedCount = 0;
20
21        // Iterate through the function array and execute each function.
22        functions.forEach((func, index) => {
23            // Assume that each function returns a promise and handle its resolution accordingly.
24            func()
25                .then(value => ({ status: 'fulfilled', value } as FulfilledObj))
26                .catch(reason => ({ status: 'rejected', reason } as RejectedObj))
27                .then(obj => {
28                    // When a promise is settled (either fulfilled or rejected), store its result.
29                    results[index] = obj;
30                    // Increment the number of completed promises.
31                    completedCount++;
32                    // When all promises have been settled, resolve the outer promise with the results array.
33                    if (completedCount === functions.length) {
34                        resolve(results);
35                    }
36                });
37        });
38    });
39}
40
41// Example usage of the `promiseAllSettled` function.
42// Uncomment the following code to test the functionality.
43/*
44const functions = [
45   () => new Promise(resolve => setTimeout(() => resolve('Result'), 100))
46];
47const startTime = performance.now();
48
49const promise = promiseAllSettled(functions);
50
51promise.then(res => {
52    const elapsedTime = Math.floor(performance.now() - startTime);
53    const output = { elapsed: elapsedTime, values: res };
54    console.log(output); // Expected output: {"elapsed":100,"values":[{"status":"fulfilled","value":"Result"}]}
55});
56*/
57

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The time complexity of the promiseAllSettled function is primarily determined by the functions[i]() Promises execution. Assuming that each function returns a Promise that settles in at most time T, the promiseAllSettled function has a time complexity of O(T). It's because Promise.allSettled executes all Promises concurrently, and the overall time taken depends on the longest-running Promise rather than the total count of Promises.

However, note that if the execution time T varies for the Promises, the time complexity in relation to the number of Promises n does not strictly apply as Promises are not executed sequentially. The time complexity in terms of concurrency is determined by the "slowest" or longest-running asynchronous operation.

Space Complexity

The space complexity of the promiseAllSettled function is O(n), where n is the number of functions (Promises) passed to it. This is because a result object (Obj) is stored for each Promise, and these are accumulated in the res array. The size of this array grows linearly with the number of Promises provided, so it scales linearly with the input size.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructureOverlapping subproblemsNon-overlapping subproblemsConstant time subproblems

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2795. Parallel Execution of Promises for Individual Results Retrieval

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings