We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Function Composition

Number: 2741

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Yandex

Problem Description

Given an array of functions that each accept and return an integer, return a new function that represents the composition of the provided functions. In function composition, the functions are applied from right to left. If the array is empty, the identity function f(x) = x should be returned.

Key Insights

  • Compose functions by applying them from rightmost to leftmost.
  • An empty list of functions defaults to the identity function.
  • The composed function essentially nests the function calls: fn(x) = f1(f2(...(fn(x))...)).
  • Iteratively applying the functions in reverse order is a straightforward solution.

Space and Time Complexity

Time Complexity: O(n) per invocation of the composed function, where n is the number of functions. Space Complexity: O(1) additional space, aside from storing the function list and the call stack for individual function calls.

Solution

The solution creates a new function that, when called, applies the provided functions from right to left. We iterate through the functions array in reverse order, applying each function to the current result. If the functions array is empty, the composed function simply returns its input, acting as the identity function. This approach uses a simple loop to combine the functions, ensuring an efficient and clear implementation using closures or lambda expressions in various languages.

Code Solutions

# Define a function that composes a list of functions.
def compose_functions(functions):
    # Return a composed function that applies the functions from right to left.
    def composed(x):
        # Start with the input value.
        result = x
        # Iterate over the functions in reverse order.
        for func in reversed(functions):
            # Apply each function to the result.
            result = func(result)
        return result
    return composed

# Example usage:
# functions = [lambda x: x + 1, lambda x: x * x, lambda x: 2 * x]
# composed_func = compose_functions(functions)
# print(composed_func(4))  # Output: 65
← Back to All Questions