Facebook Pixel

2797. Partial Function with Placeholders 🔒

Problem Description

This problem asks you to implement a partial function application mechanism in JavaScript/TypeScript.

You need to create a function partial that takes two parameters:

  • fn: A function to be partially applied
  • args: An array of arguments that may contain placeholders

The partial function should return a new function partialFn that:

  1. Replaces placeholders: When partialFn is called with restArgs, it should replace any "_" placeholders in the original args array with values from restArgs in order. For example, if args = [1, "_", 3, "_"] and restArgs = [2, 4], the placeholders get replaced to form [1, 2, 3, 4].

  2. Appends remaining arguments: If there are more values in restArgs than there are placeholders, the extra values should be appended to the end of the arguments list. For example, if args = [1, "_"] and restArgs = [2, 3, 4], the final arguments become [1, 2, 3, 4].

  3. Calls the original function: Finally, partialFn should call the original function fn with the modified arguments array spread as individual parameters and return its result.

Example:

function add(a, b, c) {
    return a + b + c;
}

const partialAdd = partial(add, [1, "_", 3]);
partialAdd(2); // Returns 6 (calls add(1, 2, 3))

const partialAdd2 = partial(add, ["_", "_"]);
partialAdd2(1, 2, 3, 4); // Returns 6 (calls add(1, 2, 3, 4), extra argument 4 is passed but ignored by add)

The key challenge is to correctly track and replace placeholders while maintaining the order of arguments and handling any excess arguments appropriately.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we need to create a closure that "remembers" the original function and arguments template, then fills in the blanks when the returned function is called.

Think of it like a form with some fields already filled in and some blank spaces marked with "_". When someone provides the missing information (restArgs), we need to:

  1. Fill in the blanks in order
  2. Add any extra information at the end

The natural approach is to iterate through the original args array and whenever we encounter a placeholder "_", we replace it with the next available value from restArgs. We need a pointer (i) to track which value from restArgs we should use next.

Here's the step-by-step thought process:

  1. Two-pointer technique: We need one pointer (j) to traverse the args array and another pointer (i) to track our position in restArgs. This ensures we fill placeholders in the correct order.

  2. In-place replacement: When we find a "_" in args[j], we replace it with restArgs[i] and increment i to move to the next replacement value.

  3. Handle excess arguments: After replacing all placeholders, if we still have unused values in restArgs (when i < restArgs.length), these should be appended to the end. This allows for functions that can accept variable numbers of arguments.

  4. Spread operator for function call: Finally, we use the spread operator fn(...args) to pass the modified array as individual arguments to the original function, which is exactly how the original function expects to receive them.

The beauty of this solution is its simplicity - it modifies the args array directly during execution, making the logic straightforward and efficient with O(n) time complexity where n is the length of the arguments.

Solution Approach

The implementation uses a closure pattern to create a function that captures both the original function fn and the argument template args.

Here's the step-by-step implementation:

  1. Return a closure function: The partial function returns an anonymous function that accepts ...restArgs (using rest parameters to collect all arguments into an array).

  2. Initialize pointer for restArgs: We start with i = 0 to track our current position in the restArgs array.

  3. Replace placeholders in args:

    for (let j = 0; j < args.length; ++j) {
        if (args[j] === '_') {
            args[j] = restArgs[i++];
        }
    }
    • Iterate through each element in args using index j
    • When we find a placeholder "_", replace it with restArgs[i]
    • Increment i after each replacement to move to the next value in restArgs
    • Non-placeholder values in args remain unchanged
  4. Append remaining arguments:

    while (i < restArgs.length) {
        args.push(restArgs[i++]);
    }
    • After replacing all placeholders, check if there are unused values in restArgs
    • Append any remaining values to the end of args
    • This handles cases where restArgs has more values than there are placeholders
  5. Call the original function:

    return fn(...args);
    • Use the spread operator to pass the modified args array as individual arguments
    • Return the result of calling fn with these arguments

Important Note: This implementation modifies the args array in place. In a production environment, you might want to create a copy of args first to avoid side effects if the same partial function is called multiple times:

const newArgs = [...args];  // Create a copy
// Then work with newArgs instead of args

The time complexity is O(n + m) where n is the length of args and m is the length of restArgs. The space complexity is O(1) if we modify in place, or O(n) if we create a copy of the args array.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to understand how the solution works:

function multiply(a, b, c) {
    return a * b * c;
}

const partialMultiply = partial(multiply, [2, "_", "_"]);
const result = partialMultiply(3, 4, 5);  // What happens here?

Step 1: Create the partial function

  • We call partial(multiply, [2, "_", "_"])
  • This returns a new function that "remembers" fn = multiply and args = [2, "_", "_"]

Step 2: Call the partial function with restArgs = [3, 4, 5]

Now let's trace through the algorithm:

Initialize pointer: i = 0 (points to first element of restArgs)

Replace placeholders loop:

  • j = 0: args[0] = 2 (not "_"), skip
  • j = 1: args[1] = "_" → Replace with restArgs[0] = 3, increment i to 1
    • args becomes [2, 3, "_"]
  • j = 2: args[2] = "_" → Replace with restArgs[1] = 4, increment i to 2
    • args becomes [2, 3, 4]

Append remaining arguments:

  • i = 2, restArgs.length = 3, so i < restArgs.length is true
  • Append restArgs[2] = 5 to args
  • args becomes [2, 3, 4, 5]

Call original function:

  • Execute multiply(...[2, 3, 4, 5]) which is multiply(2, 3, 4, 5)
  • Since multiply only uses 3 parameters, it computes 2 * 3 * 4 = 24
  • The extra argument 5 is ignored

Result: Returns 24

This example demonstrates all key aspects:

  1. Preserving non-placeholder values (the 2)
  2. Replacing placeholders in order ("_"3, then "_"4)
  3. Appending excess arguments (the 5)
  4. Proper function invocation with spread operator

Solution Implementation

1def partial(fn, args):
2    """
3    Creates a partially applied function with placeholder support
4  
5    Args:
6        fn: The function to be partially applied
7        args: Initial arguments, where '_' acts as a placeholder for future arguments
8  
9    Returns:
10        A new function that accepts remaining arguments
11    """
12    def wrapper(*rest_args):
13        # Clone the args list to avoid mutating the original
14        final_args = args.copy()
15        rest_args_index = 0
16      
17        # Replace placeholders ('_') with arguments from rest_args
18        for i in range(len(final_args)):
19            if final_args[i] == '_':
20                # Check if there are still rest_args available
21                if rest_args_index < len(rest_args):
22                    final_args[i] = rest_args[rest_args_index]
23                    rest_args_index += 1
24      
25        # Append any remaining arguments that weren't used for placeholders
26        while rest_args_index < len(rest_args):
27            final_args.append(rest_args[rest_args_index])
28            rest_args_index += 1
29      
30        # Call the original function with the complete argument list
31        return fn(*final_args)
32  
33    return wrapper
34
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.function.Function;
5
6/**
7 * Creates a partially applied function with placeholder support.
8 * This implementation uses a functional interface to represent the partially applied function.
9 */
10public class PartialFunction {
11  
12    // Placeholder constant for argument positions that will be filled later
13    private static final Object PLACEHOLDER = "_";
14  
15    /**
16     * Creates a partially applied function with placeholder support
17     * @param fn - The function to be partially applied
18     * @param args - Initial arguments, where "_" acts as a placeholder for future arguments
19     * @return A new function that accepts remaining arguments
20     */
21    public static Function<Object[], Object> partial(Function<Object[], Object> fn, Object[] args) {
22        return (Object[] restArgs) -> {
23            // Clone the args array to avoid mutating the original
24            List<Object> finalArgs = new ArrayList<>(Arrays.asList(args));
25            int restArgsIndex = 0;
26          
27            // Replace placeholders ('_') with arguments from restArgs
28            for (int i = 0; i < finalArgs.size(); i++) {
29                if (PLACEHOLDER.equals(finalArgs.get(i))) {
30                    // Check if there are remaining arguments to use
31                    if (restArgsIndex < restArgs.length) {
32                        finalArgs.set(i, restArgs[restArgsIndex]);
33                        restArgsIndex++;
34                    }
35                }
36            }
37          
38            // Append any remaining arguments that weren't used for placeholders
39            while (restArgsIndex < restArgs.length) {
40                finalArgs.add(restArgs[restArgsIndex]);
41                restArgsIndex++;
42            }
43          
44            // Call the original function with the complete argument list
45            return fn.apply(finalArgs.toArray());
46        };
47    }
48}
49
1#include <functional>
2#include <vector>
3#include <any>
4#include <string>
5
6/**
7 * Creates a partially applied function with placeholder support
8 * @param fn - The function to be partially applied
9 * @param args - Initial arguments, where "_" acts as a placeholder for future arguments
10 * @returns A new function that accepts remaining arguments
11 */
12template<typename ReturnType, typename... FnArgs>
13std::function<ReturnType(const std::vector<std::any>&)> partial(
14    std::function<ReturnType(FnArgs...)> fn, 
15    const std::vector<std::any>& args) {
16  
17    // Return a lambda that captures fn and args
18    return [fn, args](const std::vector<std::any>& restArgs) -> ReturnType {
19        // Clone the args vector to avoid mutating the original
20        std::vector<std::any> finalArgs = args;
21        size_t restArgsIndex = 0;
22      
23        // Replace placeholders ('_') with arguments from restArgs
24        for (size_t i = 0; i < finalArgs.size(); i++) {
25            // Check if current element is a placeholder
26            if (finalArgs[i].has_value() && 
27                finalArgs[i].type() == typeid(std::string)) {
28                try {
29                    std::string val = std::any_cast<std::string>(finalArgs[i]);
30                    if (val == "_") {
31                        // Replace placeholder with next available argument
32                        if (restArgsIndex < restArgs.size()) {
33                            finalArgs[i] = restArgs[restArgsIndex++];
34                        }
35                    }
36                } catch (const std::bad_any_cast& e) {
37                    // Not a string, skip
38                }
39            }
40        }
41      
42        // Append any remaining arguments that weren't used for placeholders
43        while (restArgsIndex < restArgs.size()) {
44            finalArgs.push_back(restArgs[restArgsIndex++]);
45        }
46      
47        // Convert vector of any to tuple and call the original function
48        // Note: This requires helper function to unpack vector to function arguments
49        return applyFunction(fn, finalArgs);
50    };
51}
52
53// Helper function to apply function with vector of arguments
54template<typename ReturnType, typename... Args, size_t... Is>
55ReturnType applyFunctionImpl(
56    std::function<ReturnType(Args...)> fn,
57    const std::vector<std::any>& args,
58    std::index_sequence<Is...>) {
59    // Unpack vector elements and cast to appropriate types
60    return fn(std::any_cast<Args>(args[Is])...);
61}
62
63template<typename ReturnType, typename... Args>
64ReturnType applyFunction(
65    std::function<ReturnType(Args...)> fn,
66    const std::vector<std::any>& args) {
67    return applyFunctionImpl(fn, args, std::index_sequence_for<Args...>{});
68}
69
1/**
2 * Creates a partially applied function with placeholder support
3 * @param fn - The function to be partially applied
4 * @param args - Initial arguments, where '_' acts as a placeholder for future arguments
5 * @returns A new function that accepts remaining arguments
6 */
7function partial(fn: Function, args: any[]): Function {
8    return function (...restArgs: any[]): any {
9        // Clone the args array to avoid mutating the original
10        const finalArgs: any[] = [...args];
11        let restArgsIndex: number = 0;
12      
13        // Replace placeholders ('_') with arguments from restArgs
14        for (let i = 0; i < finalArgs.length; i++) {
15            if (finalArgs[i] === '_') {
16                finalArgs[i] = restArgs[restArgsIndex++];
17            }
18        }
19      
20        // Append any remaining arguments that weren't used for placeholders
21        while (restArgsIndex < restArgs.length) {
22            finalArgs.push(restArgs[restArgsIndex++]);
23        }
24      
25        // Call the original function with the complete argument list
26        return fn(...finalArgs);
27    };
28}
29

Time and Space Complexity

Time Complexity: O(n) where n is the total number of arguments (args.length + restArgs.length)

  • The first for loop iterates through args.length elements: O(args.length)
  • The while loop iterates through remaining restArgs elements: O(restArgs.length)
  • The spread operation fn(...args) takes O(args.length) time to pass arguments
  • Overall: O(args.length + restArgs.length) = O(n)

Space Complexity: O(n) where n is the total number of arguments

  • The returned function creates a closure that captures the original args array: O(args.length)
  • The args array is mutated in place, but can grow by pushing remaining restArgs: worst case O(args.length + restArgs.length)
  • The spread operation creates a temporary argument list: O(args.length)
  • Overall: O(args.length + restArgs.length) = O(n)

Note: There's a bug in this implementation - the args array is mutated on each call to the returned function, which means the function will not work correctly if called multiple times. The placeholders '_' will be permanently replaced after the first call.

Common Pitfalls

1. Mutating the Original Args Array

The most critical pitfall is modifying the original args array in place. This causes the partial function to behave incorrectly when called multiple times.

Problem Example:

def add(a, b, c):
    return a + b + c

# BAD: Modifying args directly
def partial_buggy(fn, args):
    def wrapper(*rest_args):
        rest_index = 0
        # Directly modifying args - BUG!
        for i in range(len(args)):
            if args[i] == '_':
                args[i] = rest_args[rest_index]
                rest_index += 1
        # ... rest of code
        return fn(*args)
    return wrapper

partial_add = partial_buggy(add, ['_', '_', 3])
print(partial_add(1, 2))  # Returns 6 (correct)
print(partial_add(4, 5))  # Returns 12 (incorrect! Should also be 12, but args is now [1, 2, 3])

Solution: Always create a copy of the args array:

def wrapper(*rest_args):
    final_args = args.copy()  # Create a copy!
    # Now work with final_args instead of args

2. Not Handling Insufficient Rest Arguments

When there are more placeholders than provided rest arguments, the code might crash or leave placeholders unreplaced.

Problem Example:

partial_add = partial(add, ['_', '_', '_'])
partial_add(1, 2)  # Only 2 arguments for 3 placeholders

Solution: Check bounds before accessing rest_args:

for i in range(len(final_args)):
    if final_args[i] == '_':
        if rest_args_index < len(rest_args):  # Bounds check
            final_args[i] = rest_args[rest_args_index]
            rest_args_index += 1
        # Optionally: else leave as '_' or replace with None/default value

3. Using Wrong Comparison for Placeholder Check

Using is instead of == for string comparison can fail unexpectedly due to Python's string interning behavior.

Problem Example:

# BAD: Using identity comparison
if args[i] is '_':  # May not work reliably
    # ...

# GOOD: Using equality comparison  
if args[i] == '_':  # Always works correctly
    # ...

4. Not Preserving Function Metadata

The wrapper function loses the original function's metadata (name, docstring, etc.).

Solution: Use functools.wraps decorator:

from functools import wraps

def partial(fn, args):
    @wraps(fn)  # Preserves fn's metadata
    def wrapper(*rest_args):
        # ... implementation
    return wrapper
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

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


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More