Pass functions and analyze basic data structures
Company: eBay
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Implement a function applyTwice(f, x) that accepts a function f and a value x and returns f(f(x)) in your preferred language. Demonstrate how to pass functions (or delegates) as parameters and discuss closures and side effects. Then analyze arrays, linked lists, stacks, and queues: give time/space complexities for insert, delete, search, and iteration, and explain when you would choose each structure.
Quick Answer: This question evaluates proficiency with higher-order functions, passing functions or delegates, closures, and reasoning about side effects, alongside the ability to analyze fundamental data structures and their performance characteristics.
You are given a list of operations ops describing a unary integer function f and an integer x. Each operation is applied in order to transform the input. Supported operations are: "add v" (add integer v), "mul v" (multiply by integer v), "pow e" (raise to the non-negative integer exponent e), "neg" (negate), and "abs" (absolute value). If ops is empty, f is the identity function. Implement apply_twice(ops, x) to return f(f(x)).
Constraints
- 0 <= len(ops) <= 100
- Each op is one of: 'add v', 'mul v', 'pow e', 'neg', 'abs'
- v is a signed 64-bit integer; e is an integer in [0, 9]
- x is a signed 64-bit integer
- Apply operations left-to-right; 'pow e' uses integer exponentiation
- If ops is empty, return x (identity)
Solution
from typing import List
def apply_twice(ops: List[str], x: int) -> int:
def make_func(ops: List[str]):
def f(val: int) -> int:
for op in ops:
parts = op.strip().split()
if not parts:
continue
name = parts[0]
if name == 'add':
if len(parts) != 2:
raise ValueError('add expects 1 argument')
v = int(parts[1])
val += v
elif name == 'mul':
if len(parts) != 2:
raise ValueError('mul expects 1 argument')
v = int(parts[1])
val *= v
elif name == 'pow':
if len(parts) != 2:
raise ValueError('pow expects 1 argument')
e = int(parts[1])
if e < 0:
raise ValueError('pow exponent must be non-negative')
val = pow(val, e)
elif name == 'neg':
val = -val
elif name == 'abs':
val = abs(val)
else:
raise ValueError(f'unknown operation: {name}')
return val
return f
f = make_func(ops)
return f(f(x))
Explanation
Construct a function f using a closure that captures the ops list. The inner function iterates over ops and applies each operation to the input value. Then compute f(f(x)) by invoking the constructed function twice. Parsing is done by splitting each operation string and handling the supported commands and their arguments. This approach demonstrates passing functions via closures while keeping operations pure and deterministic.
Time complexity: O(m). Space complexity: O(1).
Hints
- Parse each operation by splitting on whitespace; handle negative constants (e.g., 'add -5').
- Apply operations sequentially to build f(x); then apply the same sequence again to f(x).
- Consider creating a helper that applies ops once to a value.
- If ops is empty, the identity function is applied twice, so return x.
- Treat operations as pure (no side effects) so applying twice is deterministic.