How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Uber during technical interviews.

Find a Black-Box Convex Function Minimum

Company: Uber

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given access to a black-box function `F(x)`: each call returns the function value at a real number `x`. You are also given a search interval `[a, b]`. Assume `F` is convex or unimodal on this interval, so the global minimum lies within `[a, b]`. Design an algorithm to return an approximate minimizer `x*` or the corresponding minimum value `F(x*)` within precision `epsilon`. You may not use gradients, symbolic derivatives, or any information other than function evaluations. Discuss the continuous-domain case, the integer-domain case, and the time and space complexity.

Quick Answer: This question evaluates proficiency in zero-order optimization and algorithm design, focusing on reasoning about convexity and unimodality when only function evaluations are available.

Part 1: Approximate Minimum of a Continuous Unimodal Function

You are given a black-box function in the form of a Python expression string expr using the variable x. The function F(x) is guaranteed to be convex or unimodal on the continuous interval [a, b], so its global minimum lies within that interval. Using only function evaluations, return an approximate minimizer x*. In this judge, the black-box is simulated by evaluating expr. If a > b, treat the interval as [b, a]. Return the minimizing x rounded to 6 decimal places.

Constraints

expr is a valid Python expression using x, abs, and functions/constants from the math module such as exp, sqrt, sin, pi, and e.
F(x) is defined for every x in the search interval.
F(x) is convex or unimodal on [min(a, b), max(a, b)].
0 < epsilon <= 1
-1000000 <= a, b <= 1000000

Examples

Input: ('(x-2.5)**2 + 1', 0.0, 5.0, 1e-6)

Expected Output: 2.5

Explanation: A simple convex parabola with minimum at x = 2.5.

Input: ('abs(x-1.2)', 0.0, 4.0, 1e-6)

Expected Output: 1.2

Explanation: The function is convex but not differentiable at the minimum.

Input: ('exp(x)', -3.0, 2.0, 1e-6)

Expected Output: -3.0

Explanation: The function is increasing on the whole interval, so the minimum is at the left boundary.

Input: ('(x-10)**2', 7.0, 7.0, 1e-6)

Expected Output: 7.0

Explanation: Edge case: the interval contains only one point.

Hints

For a unimodal function, comparing F at two interior points lets you discard one side of the interval.
Keep shrinking the interval until its width is at most epsilon, then use the remaining interval to form your answer.

Part 2: Minimum of a Discrete Unimodal Function on an Integer Interval

You are given a black-box function in the form of a Python expression string expr using the variable x, and an integer search interval [a, b]. The function F(x) is guaranteed to be convex or unimodal over the integers in that interval. Using only function evaluations, return the integer x that minimizes F(x). If multiple integers achieve the same minimum value, return the smallest such x. In this judge, the black-box is simulated by evaluating expr. If a > b, treat the interval as [b, a].

Constraints

expr is a valid Python expression using x, abs, and functions/constants from the math module.
a and b are integers.
F(x) is defined for every integer x in [min(a, b), max(a, b)].
F(x) is discrete convex or unimodal on the integer interval.
-1000000000 <= a, b <= 1000000000

Examples

Input: ('(x-4)**2', 0, 10)

Expected Output: 4

Explanation: A standard convex parabola with a unique minimum.

Input: ('abs(x-2)', -5, 5)

Expected Output: 2

Explanation: The minimum occurs at the cusp.

Input: ('0 if 3 <= x <= 5 else (x-4)**2', 0, 10)

Expected Output: 3

Explanation: There is a flat minimum on {3, 4, 5}; return the smallest minimizer.

Input: ('x', -3, 4)

Expected Output: -3

Explanation: The function is increasing, so the minimum is at the left boundary.

Input: ('(x-100)**2', 7, 7)

Expected Output: 7

Explanation: Edge case: the interval contains only one integer.

Hints

On integers, comparing F(mid) and F(mid + 1) is enough to tell which side still contains a minimum.
If F(mid) == F(mid + 1), keep the left half if you want the smallest minimizing index.

Quick Overview

This question evaluates proficiency in zero-order optimization and algorithm design, focusing on reasoning about convexity and unimodality when only function evaluations are available.