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?

- sameepsheth January 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- GT January 30, 2014 | Flag
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

- sukheshmg January 30, 2014 | Flag Reply
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

- Nishant Kelkar January 31, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;

}

- cockroach February 14, 2014 | Flag
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
{
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;
}

- Miles Amblish January 31, 2014 | Flag Reply
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[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;
        }
    }

- techpanja January 31, 2014 | Flag Reply
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[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;
}

- kirankumarcelestial February 04, 2014 | Flag Reply
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.

- Priyank Gupta. February 04, 2014 | Flag Reply


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