## Amazon Interview Question for Software Engineer / Developers

Team: AFT
Country: United States
Interview Type: In-Person

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

can you clarify the question? You have an array and you are searching for a value in it. that's a simple sequential search. or is the array sorted? what role does roration play?

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

I'm guessing the array was sorted prior to the rotation. Makes better sense that way

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

first find the index at which it was rotated
- split the array into two equal array
- compare first and last element of sub arrays
- one of the subarrays is skewed i.e. has first element greater than last element
- call the function recursively for the skewed subarray

once you have the this index, you can do a simple binary search

complexity is log n for finding the skew index and again log n for binary search

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

Interesting problem. I am assuming that the array is sorted before rotation. The algorithm would be:
1. binary search to find the "kink" in the series of numbers - O(n) worst case
2. modified binary search to find the number of interest - O(log n)
Here is some code (not tested, but outlines the idea):

``````public int binaryKinkSearch(Integer[] arr, int start, int end) {
if(start <= end)
return -1;

int mid = Math.ceil((end - start)/2);

if(arr[ mid-1 ] < arr[ mid ] && arr[ mid ] > arr[ mid+1 ])    // found the kink
return mid;
else {
binaryKinkSearch(arr, start, mid);    // search both halves
binaryKinkSearch(arr, mid+1, end);
}

return -1;
}

public int modifiedBinarySearch(Integer[] arr, int term, int start, int end){

if(start < 0 || end < 0)
return -1;

if(start == end)
return -1;

// calculating mid is a big deal!
int mid = Math.ceil((end - start)/2);
int prev = mid - 1;
int next = mid + 1;    // to keep track

if(end < start) {

if(start < arr.length/2) {
mid = arr.length + start;
prev = mid - 1;
next = mid + 1;
}
else {
mid = start + (arr.length - start + end)/2;

if(mid > arr.length) {
mid = mid - arr.length;
}
prev = mid - 1;
next = mid + 1;

if(mid == arr.length) {
mid = mid - arr.length;
prev = arr.length;
next = mid + 1;
}
else if(mid == arr.length -1 ) {
mid = mid - arr.length;
prev = arr.length;
next = mid + 1;
}
}
}

// now just regular binary search
if(arr[ mid ] > term)
modifiedBinarySearch(arr, term, start, prev);
else if (arr[ mid ] < term)
modifiedBinarySearch(arr, term, next, end);
else
return arr[ mid ];
}``````

Overall, O(n):O(1) in time:space

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

Thanks this looks good. A question regarding binaryKinkSearch.

It doesn't matter which direction the array is rotated in, so all we need to do is look for an element in array which is greater than element to its right. Therefore, can we implement binaryKinkSearch in following way:

``````int binaryKinkSearch(int[] arr, int start, int end)
{
if(start > end) return -1;

int mid = (start + end)/2;

if(arr[mid] > arr[mid+1])
{
return mid;
}

if(start == mid) return -1;

if(arr[start] > arr[mid-1])
{
return binaryKinkSeach(arr, start, mid-1);
}

if(arr[mid+1] > arr[r])
{
return binaryKinkSeach(arr, mid+1, r);
}

return -1;

}``````

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

#include <cstdlib>
#include <iostream>
#include <vector>
#include <map>

class question
{
public:
enum turn
{
clockwise,
counter_clockwise,
};
void set_array(std::vector<int>& value)
{
m_array = value;
index_array();
}
void index_array(void)
{
m_index.clear();
int array_index, array_max = (int)m_array.size();
for (array_index = 0; array_index < array_max; ++array_index)
{
m_index[m_array[array_index]] = array_index;
}
m_shift = 0;
}
void rotate(const turn direction)
{
if (m_array.size() > 1)
{
int front_value, back_value, new_size;
switch (direction)
{
case clockwise:
front_value = m_array.front();
m_array.erase(m_array.begin());
m_array.push_back(front_value);
--m_shift;
if ((m_shift < 0) && ((unsigned int)abs(m_shift) >= m_array.size()))
{
m_shift += m_array.size();
}
break;
case counter_clockwise:
back_value = m_array.back();
new_size = m_array.size() - 1;
m_array.resize(new_size);
m_array.insert(m_array.begin(), back_value);
++m_shift;
if (m_shift >= (int)m_array.size())
{
m_shift -= m_array.size();
}
break;
default:
break;
}
}
}
bool search(const int value, int& offset)
{
std::map<int, int>::iterator it = m_index.find(value);
bool rc = false;
if (it != m_index.end())
{
offset = m_index[value] + m_shift;
rc = true;
}
return rc;
}
private:
std::vector<int> m_array;
std::map<int, int> m_index;
int m_shift;
};

int main(int argc, char** argv)
{
static int values[] = { 4, 6, 7, 8, 3, 1, 0, 4, 5, 2 };
const unsigned int value_count = sizeof(values) / sizeof(int);
std::vector<int> input_values(values, values + value_count);
question iq5;
int offset, value;
iq5.set_array(input_values);
iq5.rotate(question::clockwise);
iq5.rotate(question::clockwise);
iq5.rotate(question::counter_clockwise);
value = 14;
if (iq5.search(value, offset))
{
std::cout << value << " at index " << offset << std::endl;
}
else
{
}
value = 3;
if (iq5.search(value, offset))
{
std::cout << value << " at index " << offset << std::endl;
}
else
{
}
return 0;
}

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

github.com/techpanja/interviewproblems/blob/master/src/arrays/searchrotatedsortedarray/SearchInRotatedSortedArray.java

``````public static boolean searchInRotatedSortedArray(int[] inputArray, int number) {
if (inputArray.length == 0) {
return false;
}
if (inputArray.length == 1) {
return inputArray == number;
}
int low = 0, high = inputArray.length - 1;
return recursiveSearch(inputArray, low, high, number);
}

private static boolean recursiveSearch(int[] inputArray, int low, int high, int number) {
if (high < low) {
return false;
}
int mid = (low + high) / 2;
if (inputArray[low] == number
|| inputArray[mid] == number
|| inputArray[high] == number) {
return true;
}
if (inputArray[low] < inputArray[mid]
&& inputArray[low] < number
&& number <= inputArray[mid]) {
return recursiveSearch(inputArray, low, mid - 1, number);
} else if (inputArray[mid] < inputArray[high]
&& inputArray[mid] < number
&& number <= inputArray[high]) {
return recursiveSearch(inputArray, mid + 1, high, number);
} else if (inputArray[low] > inputArray[mid]) {
return recursiveSearch(inputArray, low, mid - 1, number);
} else if (inputArray[mid] > inputArray[high]) {
return recursiveSearch(inputArray, mid + 1, high, number);
} else {
return false;
}
}``````

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

Recursive Solution that sorts both clockwise and anticlockwise.

``````# include <iostream>

using namespace std;

int MinElement(int *arr, int low, int high)
{
int mid, min, min1;

if(low >= high)
return -1;

mid = (low + high)/2;

if(arr[mid] < arr[mid-1] && arr[mid] < arr[mid+1])
return arr[mid];
if(arr[mid] > arr[mid-1] && arr[mid-1] < arr[mid+1])
return MinElement(arr,low,mid);
else
return MinElement(arr,mid,high);

}

int main()
{
//int arr = { 3, 2, 1, 6, 5, 4 };
int arr = {4, 5, 8, 9, 11, 0, 1, 3, 2};
cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr));

return 0;
}``````

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

If the array is not sorted then one has to go with the linear search.

Algorithm:
Assuming that the array is sorted.
Assuming the number to be found is x.

1. Taking any element as the first element create a simple array of the elements.
2. Break the array from a place where the number order changes from ascending to descending or descending to ascending.
a. If the Break is for ascending to descending. Compare the first element of the first array with x.
i. If x is less than the first element of the first array. Reject the first array.
ii. If x is more than the first element of the first array. Reject the second array.
iii. Compare the last last element of the accepted array with x.
iv. if x is less. break the array into two from middle and repeat step i-iv.
v. if x is more. Then the element does not exist in the given array.

b. If the Break is for descending to ascending. Compare the first element of the first array with x.
i. If x is more than the first element of the first array. Reject the first array.
ii. If x is less than the first element of the first array. Reject the second array.
iii. Compare the last last element of the accepted array with x.
iv. if x is more. break the array into two from middle and repeat step i-iv.
v. if x is less. Then the element does not exist in the given array.

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.