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.

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.

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.

Read the full Uber Machine Learning Engineer interview experience this question came from

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.

Hints

  1. For a unimodal function, comparing F at two interior points lets you discard one side of the interval.
  2. 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.

Hints

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

Loading coding console...