Amazon Interview Question: Telephone interview: Find lar... | Glassdoor

Interview Question

Software Development Engineer III Interview San Francisco, CA

Telephone interview: Find largest integer from an array of

integers. The integers in the array are arranged in strictly increasing (no 2 integers are same) or strictly increasing then decreasing; so like a curve and you have to find the peak. Discuss time complexity. Write code.
Tags:
algorithm

1

Binary search

Interview Candidate on Jul 17, 2012
0

First, binary search will not work since just looking at a single point will not tell you if it's on the decreasing or increasing side of the curve.

What you need is modified binary search. Looking at position i check position i+1 if it's increasing then search right otherwise search left;

Code:
int peak(vector V, int i, int iStart, int iEnd){
assert( i &gt;= 0 &amp;&amp; i = 0 &amp;&amp; iStart = 0 &amp;&amp; iEnd &lt; V.size());
assert( iStart &lt;= i &amp;&amp; i &lt;= iEnd );
if (i == iEnd)
return i;

int iCurr = V[i];
int iNext = V[i+1];

int iStartNew = iStart;
int iEndNew = iEndl

if( iCurr &lt; iNext )
iStartNew = i;
else
iEndNew = i;
int iNew = (iEndNew-iStartNew)/2;
if( iNew == i )
iNew++;
return peak(V, iNew, iStartNew, iEndNew);
}

Modified binary search on Aug 23, 2012
1

The question is a variation of the commonly asked problem of finding the start/end index of a sorted array that has been rotated. Takes O(log n) time.

Arun on Aug 24, 2012