## Amazon Interview Question for Software Engineer / Developers

Country: United States

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

``````Using a modified binary search to find the index of a number within a sorted array. Will return -1 if the index was not found
Edge cases:
* circular array null or empty
* circular array with 1 element
* circular array not rotated. e.g {1,2,3,4,5,6,7,8,9}
* circular array is inverted. e.g  {9,8,7,6,5,4,3,2,1}
* circular array half rotated e.g {5,6,7,8,9,1,2,3,4}
* number is not in circular array
int findIndex(int[] array, int num){
if(array != null && array.length > 0)
return(search(array, num, 0, array.length - 1));
return(-1);
}
int search(int[] array, int num, int start, int end){
int mid = (start + end) / 2;
if(array[start] == num)
return(start);
if(array[end] == num)
return(end);
if(array[mid] == num)
return(mid);
if(end - start <= 1)
return(-1);
if(array[mid] > array[start] && array[start] < num && array[mid] > num)
return(search(array, num, start, mid));
if(array[mid] < array[start] && (array[start] > num || array[mid] < num))
return(search(array, num, start, mid));
if(array[mid] < array[end] && array[mid] < num && array[end] > num)
return(search(array, num, mid, end));
if(array[mid] > array[end] && (array[mid] > num || array[end] < num))
return(search(array, num, mid, end));
return(-1);
}``````

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

@ eyeonu.imtiyaaz: Can you please be little more clear on what do you mean by sorted array implemented as ring buffer? Does that mean that the least element can occur at any position and as it's a ring buffer you can traverse starting from the least element position to get the ascending list?
@CodeSpace: What do you mean by 'inversely rotated/half rotated? Can you explain what are you trying to do in those 4 if statement above? Is that a simple binary search that you are doing or have you modified BS for the ring buffer stuff?

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

I have added some additional comment. This is a regular binary search with modifications to handle a rotated sorted array. e.g {5,4,3,2,1,9,8,7,6}

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

@The Artist - say the array is of fixed size n. When you are done filling the array from 0 to n-1, the next insertion would take place at the zeroth position. For example, you have array like this -
Values 1 2 3 4 5 6 7 8 9 10
Array Index 0 1 2 3 4 5 6 7 8 9

Now, if values 11, 12 and 13 are inserted, your array would like like -
Values 11 12 13 4 5 6 7 8 9 10
Array Index 0 1 2 3 4 5 6 7 8 9

That being said, the answer to your first question is yes, the least element can occur at any position. For the question about traversal, I mentioned it that we have to keep it less than n, that is, the linear time. So, traversal should be avoided and as CodeSpace mentioned, binary search is the solution with some modification.

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

can you please tell how the elements in the buffer are inversely sorted

I still don't get it

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

``````int findElement(int [] a, int start, int end, int value)
{
if (start > end)
{
return -1;
}
int mid = (start+end)/2;
if (a[mid]==value)
{
return mid;
}

if (a[mid] >= a[start])  // first half is sorted
{
if (value>=a[start] && value<a[mid])
{
return findElement(a, start, mid-1, value);
}
else
{
return findElement(a, mid+1, end, value);
}
}
else
{
if (value>a[mid] && value<=a[end])
{
return findElement(a, mid+1, end, value);
}
else
{
return findElement(a, start, mid-1, value);
}
}
}``````

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

The fact that the interviewer said "sorted" circular array gives enough proof that he's expecting an algorithm of O (log n) running time. Tweaking up binary search (with index wrap around) should do the trick :)

Add a Comment
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.

Learn More

### 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.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More