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
Answer

Interview Answer

3 Answers

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 >= 0 && i = 0 && iStart = 0 && iEnd < V.size());
assert( iStart <= i && i <= iEnd );
if (i == iEnd)
 return i;

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

int iStartNew = iStart;
int iEndNew = iEndl

if( iCurr < 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

Add Answers or Comments

To comment on this, Sign In or Sign Up.