Amazon Interview Question
Software Engineer / DevelopersTeam: AFT
Country: United States
Interview Type: In-Person
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
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
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;
}
#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
{
std::cout << value << " not found" << std::endl;
}
value = 3;
if (iq5.search(value, offset))
{
std::cout << value << " at index " << offset << std::endl;
}
else
{
std::cout << value << " not found" << std::endl;
}
return 0;
}
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[0] == 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;
}
}
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[6] = { 3, 2, 1, 6, 5, 4 };
int arr[9] = {4, 5, 8, 9, 11, 0, 1, 3, 2};
cout<<MinElement(arr,0,sizeof(arr)/sizeof(arr[0]));
return 0;
}
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.
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?
- sameepsheth January 30, 2014