Taro Logo

Function Composition

#716 Most AskedEasy
7 views
Topics:
Arrays

Given an array of functions [f1, f2, f3, ..., fn], return a new function fn that is the function composition of the array of functions.

The function composition of [f(x), g(x), h(x)] is fn(x) = f(g(h(x))).

The function composition of an empty list of functions is the identity function f(x) = x.

You may assume each function in the array accepts one integer as input and returns one integer as output.

Example 1:

Input: functions = [x => x + 1, x => x * x, x => 2 * x], x = 4
Output: 65
Explanation:
Evaluating from right to left ...
Starting with x = 4.
2 * (4) = 8
(8) * (8) = 64
(64) + 1 = 65

Example 2:

Input: functions = [x => 10 * x, x => 10 * x, x => 10 * x], x = 1
Output: 1000
Explanation:
Evaluating from right to left ...
10 * (1) = 10
10 * (10) = 100
10 * (100) = 1000

Example 3:

Input: functions = [], x = 42
Output: 42
Explanation:
The composition of zero functions is the identity function

Constraints:

  • -1000 <= x <= 1000
  • 0 <= functions.length <= 1000
  • all functions accept and return a single integer

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:

  1. What are the possible data types of the functions we will be composing, and do they all accept and return the same type?
  2. Can the input function array be empty or null?
  3. If the input function array is empty, what should the composed function return, or how should it behave when called?
  4. What should the composed function return if any of the functions in the array throw an error?
  5. Is the order of function application important, and should I assume it's right-to-left or left-to-right?

Brute Force Solution

Approach

The brute force approach to function composition means we're going to try applying the functions in every possible order. We'll go through each function, apply it, and then try every possible next function on the result. This makes sure we explore every possible combination.

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

  1. Start by picking one function from the list and applying it to the initial input.
  2. Then, take the result from that and pick another function from the list to apply to *that* result.
  3. Keep doing this, picking functions one after another, until you've used all the functions from the list in one particular order.
  4. Store the final result you get from applying all the functions in that order.
  5. Now, repeat this whole process, but start by picking a *different* function as the first one to apply.
  6. Keep repeating the process, trying every single possible order in which you can apply the functions.
  7. Finally, after trying every possible order, you'll have a list of results. Choose the one from the list that matches what you're looking for, based on the requirements of the problem.

Code Implementation

def compose_functions_brute_force(functions, initial_value):
    results = []
    
    def apply_permutation(current_value, remaining_functions, current_permutation):
        if not remaining_functions:
            results.append(current_value)
            return

        # Iterate through available functions
        for i in range(len(remaining_functions)):
            function_to_apply = remaining_functions[i]
            new_value = function_to_apply(current_value)

            # Create a copy of the remaining functions for the recursive call.
            next_remaining_functions = remaining_functions[:i] + remaining_functions[i+1:]
            apply_permutation(new_value, next_remaining_functions, current_permutation + [function_to_apply])

    # Generate all permutations by trying each function first.
    apply_permutation(initial_value, functions, [])
    
    # Assuming we want the maximum result after applying all function permutations
    if results:
        return max(results)
    else:
        return initial_value

Big(O) Analysis

Time Complexity
O(n!) – The brute force approach explores all possible orderings of applying n functions. Generating all permutations of n functions leads to n! (n factorial) different orderings. For each of these n! orderings, we apply n functions sequentially, resulting in n operations. However, the dominant term is still the generation of n! permutations. Therefore, the overall time complexity is O(n!).
Space Complexity
O(N!) – The algorithm explores every possible order of applying N functions. To store the final results from each permutation of function applications, we need a list to hold these results. In the worst-case scenario, each permutation could yield a unique result, necessitating storage for all N! results. Therefore, the auxiliary space required grows factorially with the number of functions, N, giving us a space complexity of O(N!).

Optimal Solution

Approach

The core idea is to chain together multiple functions, where the output of one function becomes the input of the next. We want to apply these functions in a specific order, from right to left, to get a final result. This requires careful management to ensure each function receives the correctly transformed data.

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

  1. Start by creating a single, master function that will manage the whole process.
  2. This master function should accept an array of functions as input.
  3. Inside the master function, consider the functions as a series of steps to apply, starting with the last function in the array.
  4. The output from the rightmost function will be piped as the input to the function on its left, and so on.
  5. The very first value which is the input to all the functions, is passed to the last function in the functions array.
  6. Repeat this process until all functions have been applied in the right-to-left sequence.
  7. Make sure that functions handle empty function arrays by returning the original input value.

Code Implementation

def function_composition(
    functions_array
):
    # Handle the case where the input array is empty.
    if not functions_array:
        return lambda initial_value: initial_value

    def composed_function(initial_value):
        # Accumulator starts with the initial value.
        accumulator = initial_value

        # Apply functions from right to left.
        for function in reversed(functions_array):
            # Each function transforms the accumulator.
            accumulator = function(accumulator)

        return accumulator

    # Return the master composed function.
    return composed_function

Big(O) Analysis

Time Complexity
O(n) – The compose function iterates through the array of functions once, applying each function in sequence. The number of functions in the array determines the number of iterations. Therefore, if n is the number of functions in the input array, the time complexity is directly proportional to n, resulting in O(n).
Space Complexity
O(1) – The function composition process, as described, iteratively applies functions without creating auxiliary data structures that scale with the number of functions (N). Intermediate results are passed directly from one function to the next without storing them in a collection. Therefore, the space required is constant, regardless of the number of functions to be composed. This constant space primarily includes variables used to manage the function application, and the space required for parameter passing, which does not depend on N.

Edge Cases

Empty array of functions
How to Handle:
Return the initial value directly since there are no functions to apply.
Initial value is null or undefined
How to Handle:
Check for null/undefined initial value and either throw an error or return it, depending on requirements.
One of the functions throws an error
How to Handle:
Catch the error and either re-throw it or return a default error value/state, depending on the desired behavior.
Functions with incompatible input/output types
How to Handle:
Ensure type compatibility by using type checking during development or runtime (if language allows).
Very large number of functions to compose
How to Handle:
Consider potential stack overflow issues if using recursion and switch to an iterative approach.
Functions are not pure (have side effects)
How to Handle:
Document the side effects clearly or refactor code to avoid them.
Functions modify the input value unexpectedly
How to Handle:
Create copies of input values within functions to prevent unintended modifications and ensure data integrity.
Composed function result exceeds maximum representable value.
How to Handle:
Handle potential overflow by checking result boundaries, using larger data types if needed, or returning an error.
0/1718 completed