Uber·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Uber ML engineer interview with a pretty meaty algorithmic question about black-box function minimization. No gradient info allowed, just raw function evaluations. The question covered a lot of ground and I wasn't fully prepared for the integer domain twist.

Questions Asked (1)

You have a black-box function F(x) you can query at any real number x, and a search interval [a, b] where F is convex or unimodal. Design an algorithm to find an approximate minimizer x* within precision epsilon, using only function evaluations (no gradients, no derivatives). Cover the continuous case, the integer domain case, and analyze time and space complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This is basically ternary search, which I knew, but I stumbled when they pushed into the integer domain case.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem: F is convex/unimodal, we can only evaluate F, and we need an approximate minimizer within epsilon. Then present the continuous case using ternary search or golden-section search, explain the integer case with discrete ternary search or binary search on differences, and analyze time and space complexity for each.

Pro tip: Mention that golden-section search is more efficient than ternary search because it reuses one evaluation per iteration, reducing the number of function calls—a key consideration when evaluations are expensive.

1. Clarify assumptions and constraints

Confirm that F is convex or unimodal on [a, b], that we can only query F(x), and that we need an approximate minimizer within epsilon. Discuss whether epsilon is absolute or relative, and if there are any constraints on the number of evaluations.

2. Continuous domain: ternary search

Explain ternary search: iteratively divide the interval into three parts using two points m1 and m2, compare F(m1) and F(m2), and discard the subinterval that cannot contain the minimum. Continue until the interval width is less than epsilon.

3. Continuous domain: golden-section search

Introduce golden-section search as an improvement: it uses the golden ratio to place points so that one function evaluation is reused per iteration, reducing the total number of evaluations. Show how it maintains the interval and converges linearly.

4. Integer domain: discrete ternary search

For integer domain, adapt ternary search by choosing integer points m1 and m2, and narrowing the interval based on comparisons. Alternatively, use binary search on the discrete derivative: find the first point where F(x+1) >= F(x).

5. Complexity analysis

Analyze time complexity: O(log((b-a)/epsilon)) for continuous, O(log(b-a)) for integer. Space complexity is O(1) for iterative implementations. Compare ternary vs golden-section in terms of constant factors.

Key Points to Mention

Convexity/unimodality guarantees that ternary search works; if not, the algorithm may fail.
Golden-section search reduces function evaluations by reusing one point per iteration, which is crucial when F is expensive to evaluate.
For integer domain, binary search on the difference F(x+1)-F(x) finds the minimum in O(log(b-a)) evaluations.
Precision epsilon determines the stopping criterion: stop when interval width < epsilon (or < 2*epsilon for integer).
Time complexity is logarithmic in the ratio (b-a)/epsilon; space complexity is constant.
Discuss trade-offs: ternary search is simpler but uses more evaluations; golden-section is more efficient but slightly more complex.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.