amazon 电面题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

amazon 电面题

amazon 电面题# JobHunting - 待字闺中

b*y2010-09-05 07:09

1 楼

A sorted array is rotated(rotate position is unknown), find the index for
the smallest element.
Example: 1 2 3 4 5 6 7, after rotated to the right becomes 4 5 6 7 1 2 3

a*y2010-09-05 07:09

2 楼

每次比较中间和两头的值吧
跟rotated array的二分查找类似

【在 b******y 的大作中提到】

: A sorted array is rotated(rotate position is unknown), find the index for
: the smallest element.
: Example: 1 2 3 4 5 6 7, after rotated to the right becomes 4 5 6 7 1 2 3

B*g2010-09-05 07:09

3 楼

怎么知道中间？
One stupid algorithm I can think of:
int smallestIndex(int arr[], int size)
{
int smallest = arr[0];
int index = 0;
for( int i = 1; i < size; ++i ){
if( arr[i] < arr[i-1] && smallest > arr[i] ){
smallest = arr[i];
index = i;
}
}
return index;
}

【在 a*****y 的大作中提到】

: 每次比较中间和两头的值吧
: 跟rotated array的二分查找类似

c*e2010-09-05 07:09

4 楼

The trick of the question is that, in the worst scenario, the approach can
only be O(n). If the array has all a[i]=1, you have to go through every
element. If you do not, one of it (if only one of it) could be 0. But for
general case, it should be O(logn) (the binary search approach).
With that the approach is clear. Use recursion. For an array a[i] to a[j]
with i)/2 or k=(i+j+1)/2. If a[k]>a[j], then call the subroutine for

【在 b******y 的大作中提到】

: A sorted array is rotated(rotate position is unknown), find the index for
: the smallest element.
: Example: 1 2 3 4 5 6 7, after rotated to the right becomes 4 5 6 7 1 2 3