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 appliedargs
: An array of arguments that may contain placeholders
The partial
function should return a new function partialFn
that:
-
Replaces placeholders: When
partialFn
is called withrestArgs
, it should replace any"_"
placeholders in the originalargs
array with values fromrestArgs
in order. For example, ifargs = [1, "_", 3, "_"]
andrestArgs = [2, 4]
, the placeholders get replaced to form[1, 2, 3, 4]
. -
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, ifargs = [1, "_"]
andrestArgs = [2, 3, 4]
, the final arguments become[1, 2, 3, 4]
. -
Calls the original function: Finally,
partialFn
should call the original functionfn
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.
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:
- Fill in the blanks in order
- 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:
-
Two-pointer technique: We need one pointer (
j
) to traverse theargs
array and another pointer (i
) to track our position inrestArgs
. This ensures we fill placeholders in the correct order. -
In-place replacement: When we find a
"_"
inargs[j]
, we replace it withrestArgs[i]
and incrementi
to move to the next replacement value. -
Handle excess arguments: After replacing all placeholders, if we still have unused values in
restArgs
(wheni < restArgs.length
), these should be appended to the end. This allows for functions that can accept variable numbers of arguments. -
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:
-
Return a closure function: The
partial
function returns an anonymous function that accepts...restArgs
(using rest parameters to collect all arguments into an array). -
Initialize pointer for restArgs: We start with
i = 0
to track our current position in therestArgs
array. -
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 indexj
- When we find a placeholder
"_"
, replace it withrestArgs[i]
- Increment
i
after each replacement to move to the next value inrestArgs
- Non-placeholder values in
args
remain unchanged
- Iterate through each element in
-
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
- After replacing all placeholders, check if there are unused values in
-
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
- Use the spread operator to pass the modified
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 EvaluatorExample 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
andargs = [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 "_"), skipj = 1
:args[1] = "_"
→ Replace withrestArgs[0] = 3
, incrementi
to 1args
becomes[2, 3, "_"]
j = 2
:args[2] = "_"
→ Replace withrestArgs[1] = 4
, incrementi
to 2args
becomes[2, 3, 4]
Append remaining arguments:
i = 2
,restArgs.length = 3
, soi < 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 ismultiply(2, 3, 4, 5)
- Since
multiply
only uses 3 parameters, it computes2 * 3 * 4 = 24
- The extra argument
5
is ignored
Result: Returns 24
This example demonstrates all key aspects:
- Preserving non-placeholder values (the
2
) - Replacing placeholders in order (
"_"
→3
, then"_"
→4
) - Appending excess arguments (the
5
) - 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)
takesO(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 remainingrestArgs
: worst caseO(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
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!