Pocketgems Interview Question
Software Engineer / DevelopersCountry: United States
Start with three intervals and determine whether they go net down or net up. If they're DDU or DDD (i.e the middle interval is net down), then you know the min is the 2nd or 3rd interval, so toss the first interval and split the third one. If they're DUU or UUU (i.e. the middle interval is net up), then you know the min is in the 1st or 2nd interval, so toss the third interval and split the first one. Keep applying the algorithm until your three intervals are suitably small.
Here is working code in Python:
def find_min(f, lo_x, hi_x, max_error):
x0 = lo_x
x3 = hi_x
x1 = (2*x0+1*x3) / 3.0
x2 = (1*x0+2*x3) / 3.0
while x2 - x1 > max_error:
if f(x2) > f(x1):
# The middle is increasing, so
# prune the right interval.
x3 = x2
x2 = x1
x1 = (x0+x1) / 2.0
else:
# The middle is decreasing, so
# prune the left interval.
x0 = x1
x1 = x2
x2 = (x2+x3) / 2.0
return x1
f = lambda x: (x - 1.5) ** 2
guess = find_min(f, -10, 7, 0.0001)
assert abs(guess - 1.5) < 0.0001
f = lambda x: (x - 3.7) ** 4
guess = find_min(f, 0, 5, 0.00001)
assert abs(guess - 3.7) < 0.00001
Here is the algorithm :
minima( x1, x2)
mid = (x1+x2)/2;M = convex(mid);
lmid = (x1+mid)/2;L = convex(lmid);
rmid = (mid+x2)/2; R = convex(rmid);
If M < R && L
then x1 = lmid;x2 = rmid;
else if M < L && M > R
then x1 = lmid;
else if M < R && M > L
then x2 = rmid;
go to line number 2;
if (x2-x1) < 1E-10
output (x1+x2)/2;
break;
If function is non decreasing or non increasing then we also use <=.
Complexity : Depends upon accuracy.
Interesting problem.
A simple approach is to just increment in small steps from x1 to x2. This is O(|x2-x1|) and potentially inefficent.
There is a more efficient binary-search like algorithm. The idea is to narrow down the interval in which the minimum lies.
Given current interval (x,y), compute two new points ((2x + y)/3, (x+2y)/3), call it (a,b).
if a and b are "equal" you return a.
Compute convex(a) and convex(b).
If convex(a) < convex(b), then b is surely in the increasing arm of the function.
Thus you can pick (x,b) as the new search interval.
if convex(a) > convex(b), then a is surely in the decreasing arm of the function. You can pick (a,y) as the new search interval.
if convex(a) == convex(b), we can pick either (x,b) or (a,y).
Thus we have an O(log (|x2 -x1|) time algorithm, as we cut a fixed fraction of the interval each time.
Here is sample python (neither exemplary, nor properly tested)
- Loler March 05, 2013