Amazon Interview Question Software Engineer / Developers
1of 1 votefind maximum number in an Array of elements
max = INTEGER.MIN
for elem in myarray:
if elem > max:
max = elem
print max
big-O is O(n)
It is better to use the divide and conquer method - MaxMin algorithm (except we only want the max value) - reason: it reduces the number of comparisions. See the algo below..
Max(arr,start,end,max) {
if(start == end) {
max = arr[start];
return;
}
if(end - start == 1) {
max = arr[end] > arr[start] ? arr[end] : arr[start]
return;
}
else {
mid = (start + end) / 2;
Max(arr,start,mid,max1);
Max(arr,mid+1,end,max2);
max = max1 > max2 ? max1 : max2;
return max;
}
}
What is the running time of this Algorithm?
Looks like you will end up comparing more than n times...
Let me know if I m wrong.
I think that the solution is actually O(n). It's like a mergesort, except without the merge. Problem divides into two parts, and each part halves the problem.
Yes it is still O(n) but if you research a little the Divide and Conquer approach has (3n/2)-2 is the best, avg and worst case number of comparisions. With the straight approach the worst case (when the max is at the end of the list) the # of comparisions made is 2(n-1), hence the Divide and Conquer approach is preferred.
This is the question asked by AMAZON person in the interview and i believe this website is used to help people prepare for their interviews. There is nothing wrong in posting questions that have been asked even though it is simple.These might help a lot of people.
What is so special about it?
- hary February 20, 2010