2666. Allow One Function Call

Easy

Problem Description

The problem statement requires us to create a higher-order function that takes a function fn as an argument and returns a new function. This new function must retain the behavior of the original fn, with the exception that it can only successfully execute once. This means that the very first time the new function is called, it should invoke fn, pass all given arguments to it, and then return the result of fn. Any calls to the new function after the first call should return undefined without invoking fn again. This ensures that fn is called at most once, regardless of how many times the new function is called.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To build a solution for this problem, we need to create a function that "remembers" if it has been called before. We can achieve this by using a closure - a programming pattern that allows a function to access variables from the scope in which it was created, even after that scope has closed. We define a boolean variable called within the scope of the once function but outside of the scope of the returned function. This variable called is set to false initially, indicating that fn has not been called yet.

When the returned function is invoked for the first time, it checks called which is false, so it proceeds to set called to true to mark that fn has been called and then invokes fn with all the arguments it received using the ...args spread syntax for parameters. It then returns whatever fn returns. For subsequent invocations, when the returned function is called again, called is now true, and the function simply returns undefined without calling fn. This logic ensures that fn is executed only once and enforces the restriction as specified by the problem description.

The TypeScript type annotations in the solution enforce that the types of the arguments and return of the returned function match those of the original function fn. This is done using generic type parameters and utility types like Parameters and ReturnType to derive the appropriate types for the arguments and return value of fn.

Solution Approach

The problem requires a solution that ensures a given function fn is only called once, regardless of how many times the newly created function is called. The solution provided uses a closure to capture the state of whether fn has already been called.

Here's the step-by-step implementation of the solution:

Create Closure: The main function once is given fn as an argument. Inside once, a variable called is declared and initialized to false. This variable captures the state within the closure of the function returned by once.
Return New Function: once returns a new function that takes a variable number of arguments using the ...args rest syntax. This is where the closure comes into play. The variables defined in the scope of once (fn and called) are accessible to this returned function.
Check and Invoke: Every time the returned function is called, it first checks the value of called. If called is false, it means fn has not been called before, and the current invocation is the first.
- The called variable is set to true to prevent any further invocation of fn.
- fn is called with all arguments passed to the returned function, using fn(...args), and the result is returned to the caller.
Subsequent Calls: If called is already true when the function is invoked (meaning fn has been called before), the function skips the invocation of fn and returns undefined.

The advantage of using a closure in this situation is that it allows us to maintain the state (called) across multiple invocations of the returned function without affecting the global scope or the scope of the function passed to once. Furthermore, the state is encapsulated within the returned function, adhering to good coding practices.

The solution approach also uses TypeScript generics and utility types for type inference:

T extends (...args: any[]) => any defines a generic type T for the function which can take any number of arguments and return any type.
Parameters<T> is a utility type that extracts the argument types of T so we can ensure the returned function accepts the same types of arguments.
ReturnType<T> is used to specify that the returned function should have the same return type as fn.

In conclusion, the implementation uses a combination of closures, generically typed functions, and control flow based on a boolean flag to satisfy the provided problem constraints.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have a function fn that simply multiplies any two numbers and returns the result. We want to ensure that fn can only be invoked once.

Firstly, we define the function fn:

function fn(x, y) {
  return x * y;
}

Now, following the solution approach, we implement the once function:

function once<T extends (...args: any[]) => any>(fn: T): (...args: Parameters<T>) => ReturnType<T> | undefined {
  let called = false;

  return function(...args: Parameters<T>): ReturnType<T> | undefined {
    if (!called) {
      called = true;
      return fn(...args);
    }
    return undefined;
  };
}

Next, we wrap fn using once to create the onceFn function which will be our higher-order function:

const onceFn = once(fn);

Now, let's walk through how this would work:

We call onceFn with arguments 2 and 3 for the first time.

const result = onceFn(2, 3); // 'onceFn' invokes 'fn', calculates 2 * 3, and returns 6
console.log(result); // Outputs: 6

During this initial call:

The called variable is still false at the start.
The onceFn sees that fn hasn't been called, so it sets called to true.
It invokes fn with the given arguments and returns the result.

We attempt to call onceFn again with any arguments - let's say 4 and 5:

const secondResult = onceFn(4, 5); // 'onceFn' does not invoke 'fn' this time, returns `undefined`
console.log(secondResult); // Outputs: undefined

On this second invocation:

The called variable is already true.
The onceFn does not call fn again and simply returns undefined.

The internal called state is maintained across these calls due to the closure created within the once function. The onceFn has remembered that fn has already been invoked once, and it upholds our rule that fn only gets called one time. This example illustrates the utility of closures to encapsulate state in a functional programming context, while also showing how TypeScript can be used to maintain type safety in higher-order function scenarios.

Solution Implementation

1# Define a generic function `once` which takes a function (`func`) and returns
2# a new function that can be called only once. Subsequent calls return the result
3# of the first invocation, otherwise returns None.
4
5def once(func):
6    """
7    Creates a function that invokes `func` once, no matter how many times it is called.
8    Subsequent calls to the created function return the result of the first invocation.
9  
10    :param func: The function to restrict to be called once.
11    :return: A new function that is restricted to invoking `func` only once.
12    """
13    # A list is used here to hold `called` and `result` as it can be modified within the inner function.
14    # In Python, nonlocal variables cannot be primitive types when modified within an inner function.
15    called_and_result = [False, None]
16
17    def wrapper(*args, **kwargs):
18        if not called_and_result[0]:
19            called_and_result[0] = True  # Update the state to prevent further invocations.
20            # Call the original function with the provided arguments and store the result.
21            called_and_result[1] = func(*args, **kwargs)
22        return called_and_result[1]  # Return the stored result or None if function has been called before.
23
24    return wrapper
25
26# Example usage:
27
28# Define `sum_fn` as a function that takes three numbers and returns their sum.
29def sum_fn(a, b, c):
30    """Function that calculates the sum of three numbers."""
31    return a + b + c
32
33# Create a function `once_sum_fn` that encapsulates `sum_fn` and restricts it to a single call.
34once_sum_fn = once(sum_fn)
35
36# Call `once_sum_fn` with arguments (1, 2, 3). It should return 6.
37print(once_sum_fn(1, 2, 3))  # Expected output: 6
38
39# Attempt to call `once_sum_fn` with different arguments (2, 3, 6).
40# Since `once_sum_fn` was already called, it should return None without calling `sum_fn`.
41print(once_sum_fn(2, 3, 6))  # Expected output: None
42

1import java.util.function.Function;
2
3// Create a generic functional interface `OnceFunction` that extends Function,
4// specifying its argument and return type with generics.
5@FunctionalInterface
6interface OnceFunction<T, R> extends Function<T, R> {
7    // Override the apply method from Function to define custom behavior.
8    @Override
9    R apply(T t);
10}
11
12public class OnceExample {
13
14    /**
15     * Creates a function that invokes the given function once, no matter how many times it's called.
16     * Subsequent calls to the created function return the result of the first invocation.
17     *
18     * @param func The function to restrict to a single call.
19     * @param <T>  The input type of the function.
20     * @param <R>  The return type of the function.
21     * @return A new function that is restricted to invoking the given function only once.
22     */
23    public static <T, R> OnceFunction<T, R> once(Function<T, R> func) {
24        // Create a new instance of `OnceFunction`.
25        return new OnceFunction<>() {
26            // A flag to keep track if the function has been called.
27            private boolean called = false;
28
29            // The result of the first call to remember.
30            private R firstResult = null;
31
32            @Override
33            public R apply(T t) {
34                // Check if the function has not been called yet.
35                if (!called) {
36                    // If not, invoke the function with the provided arguments and store the result.
37                    firstResult = func.apply(t);
38                    // Update the state to prevent further invocations.
39                    called = true;
40                    // Return the stored result.
41                    return firstResult;
42                }
43                // If the function was already called, return the stored result.
44                return firstResult;
45            }
46        };
47    }
48
49    // Example usage:
50    public static void main(String[] args) {
51        // Define a function that takes an integer array and returns the sum of all elements.
52        Function<int[], Integer> sumFn = (int[] numbers) -> {
53            int sum = 0;
54            for (int n : numbers) {
55                sum += n;
56            }
57            return sum;
58        };
59
60        // Create a once-wrappable version of the `sumFn` function.
61        OnceFunction<int[], Integer> onceSumFn = OnceExample.once(sumFn);
62
63        // Call `onceSumFn` with an integer array. It should return the sum of the numbers.
64        System.out.println(onceSumFn.apply(new int[]{1, 2, 3})); // Expected output: 6
65
66        // Attempt to call `onceSumFn` again, this time with a different integer array.
67        // Since `onceSumFn` has already been called, it should return the result of the first call.
68        System.out.println(onceSumFn.apply(new int[]{2, 3, 4})); // Expected output: 6
69    }
70}
71

1#include <iostream>
2#include <functional>
3#include <tuple>
4
5// Define a template for a function that takes any number and type of arguments and
6// returns a `std::optional` value of the function's return type.
7template<typename Func>
8class OnceFunction {
9public:
10    using ReturnType = std::optional<std::invoke_result_t<Func, decltype(std::placeholders::_1)>>;
11
12    OnceFunction(Func&& fn) : function_(std::forward<Func>(fn)), called_(false) {}
13
14    // A function to invoke the stored function only once. Subsequent calls return `std::nullopt`.
15    template<class... Args>
16    ReturnType operator()(Args... args) {
17        if (!called_) {
18            called_ = true; // Mark as called
19            return function_(std::forward<Args>(args)...);
20        }
21        return std::nullopt; // Function was already called, return `std::nullopt`
22    }
23
24private:
25    Func function_; // The original function that should be called at most once.
26    bool called_; // Boolean flag to track if the function has been called or not.
27};
28
29/**
30 * Creates a function that invokes `func` once, no matter how many times it is called. Subsequent calls
31 * to the created function return `std::nullopt`.
32 * @param func - The function to restrict to be called once.
33 * @returns An `OnceFunction` functor that invokes `func` only once.
34 */
35template<typename Func>
36auto once(Func&& func) {
37    return OnceFunction<Func>(std::forward<Func>(func));
38}
39
40// Example usage of the once function template:
41
42// A function that takes three numbers and returns their sum.
43auto sumFn = [](int a, int b, int c) -> int {
44    return a + b + c;
45};
46
47int main() {
48    // Create a function `onceSumFn` that encapsulates `sumFn` and restricts it to a single call.
49    auto onceSumFn = once(sumFn);
50
51    // Call `onceSumFn` with arguments (1, 2, 3). It should return the sum, 6.
52    std::cout << "First call result: ";
53    if (auto result = onceSumFn(1, 2, 3); result) {
54        std::cout << *result << std::endl; // Expected output: First call result: 6
55    } else {
56        std::cout << "undefined" << std::endl;
57    }
58
59    // Attempt to call `onceSumFn` again with different arguments (2, 3, 6).
60    // Since `onceSumFn` was already called, it should return 'undefined' without calling `sumFn`.
61    std::cout << "Second call result: ";
62    if (auto result = onceSumFn(2, 3, 6); result) {
63        std::cout << *result << std::endl;
64    } else {
65        std::cout << "undefined" << std::endl; // Expected output: Second call result: undefined
66    }
67
68    return 0;
69}
70

1// Define a generic function type `OnceFunction` which takes a function with any number and types of arguments
2// and returns its return type or undefined.
3type OnceFunction<T extends (...args: any[]) => any> = (...args: Parameters<T>) => ReturnType<T> | undefined;
4
5/**
6 * Creates a function that invokes `func` once, no matter how many times it is called. Subsequent calls
7 * to the created function return the result of the first invocation.
8 * @param func - The function to restrict to be called once.
9 * @returns A new function that is restricted to invoking `func` only once.
10 */
11function once<T extends (...args: any[]) => any>(func: T): OnceFunction<T> {
12    // Declare a variable to track if the function has been called.
13    let called = false;
14  
15    // Return a new function that captures arguments and invokes the original function only if not called before.
16    return function (...args: Parameters<T>): ReturnType<T> | undefined {
17        // Check if the function has already been called.
18        if (!called) {
19            // Update the state to prevent further invocations.
20            called = true;
21            // Call the original function with the provided arguments and return its result.
22            return func(...args);
23        }
24        // If the function was called before, return undefined.
25        // No further action is taken, and the original function is not called.
26    };
27}
28
29// Example usage:
30// Let `sumFn` be a function that takes three numbers and returns their sum.
31let sumFn = (a: number, b: number, c: number) => a + b + c;
32
33// Create a function `onceSumFn` that encapsulates `sumFn` and restricts it to a single call.
34let onceSumFn = once(sumFn);
35
36// Call `onceSumFn` with arguments (1, 2, 3). It should return 6.
37console.log(onceSumFn(1, 2, 3)); // Expected output: 6
38
39// Attempt to call `onceSumFn` with different arguments (2, 3, 6).
40// Since `onceSumFn` was already called, it should return undefined without calling `sumFn`.
41console.log(onceSumFn(2, 3, 6)); // Expected output: undefined
42

Time and Space Complexity

Time Complexity

The time complexity of the once function wrapper is O(1), also referred to as constant time complexity. This is because the wrapper does not perform any operations that scale with the size of the input, it only checks a boolean flag and, if not previously called, executes the function fn once. The time complexity of calling the wrapped fn function is not included in the complexity of the once wrapper itself. When the original function fn is called via onceFn, its time complexity is dependent on the implementation of fn.

Space Complexity

The space complexity of the once function wrapper is O(1), which means it uses a constant amount of space. It only allocates space for one boolean variable called. It does not allocate additional space that grows with the size of the input. However, the space complexity of the closure that includes the fn function and the called value is subject to the space requirements of fn itself, which are not accounted for in the once wrapper's space complexity.

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

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don't know