## Pocketgems Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: United States

Comment hidden because of low score. Click to expand.
2
of 2 vote

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)

``````def minima(x,y, f):
err = 0.00000000000000000001
a,b = (2.0*x + y)/3.0, (x+2.0*y)/3.0

if b-a < err:
return a

delta = f(a) - f(b)

if delta*delta < err*err:
return minima(x,b,f)

if delta < 0:
return minima(x,b,f)

if delta > 0:
return minima(a,y,f)

return b

def square(x):
return x*x;

minima(-1.0,1.0, square)``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````This is a straight forward ternary search problem
double minima(int x1, int x2)
{
double lo(x1), hi(x2), x, y;
while (fabs(x1-x2) >= 1e-6)
{
x = (2*lo + hi)/3;
y = (2*hi + lo)/3;
if (x>= y) lo = x;
else hi = y;
}
return (lo+hi)/2;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.