Amazon Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
Quicksort will be best. After the first iteration the pivot is in the right position and all values left are smaller than pivot and all values to the right are larger than the pivot. Now do the same iteration again on the right subarray till you set the last element. Avg: O(logN). Worst case (already sorted array): O(n).
Hi, after your first iteration, you have already visited all the elements in the array. so should this be O(N)?
Yes, modifying quicksort is best (lg n)
Not sure you can beat logarithmic unless array is already sorted (then it is O[1] ).
QuickSort is the best for sorting , not for finding max element in array. At the first iteration itself with constant pivot we are traversing all the element to do the partition(small->left,max->right).
Instead with dynamic (NewPivot=>(pivot<currentvalue)) pivot value at the first iteration itself will find the max value. And this too is not O(logn) ,It's O(n).
Correct me if i'm wrong.
There is no way that this is less than O(n) since on your first pass with a selection algorithm will touch every element on its first run and logarithmically degrades after that. The easiest solution is to just scan the entire list and keep track of which is the highest for O(n). This can change given the circumstances. If the list is sorted or even partially sorted you can achieve better than O(n) but otherwise that's the best you can do.
So, there's plenty of explanation on how/why to do a QuickSort, but in my opinion, something MAJOR is left out here, which is to *Ask your interviewer questions before answering!* QuickSort can quickly become the wrong answer with some detail.
1. Is the list sorted? Probably not, but worst case you get "no" and best case, you're applauded for being thorough.
2. Can I sort the list? And if not, do I have the memory to copy then sort the list? A no here means that again QuickSort is out.
3. How big is the list? If you've got an int array list of a constant size 5, QuickSort is sort of using the broad sword when the butter knife will do.
All a bit pedantic here perhaps, but keeping this mindset is vital.
1. Bubble sort in increasing order
2. Linear scan to end of array, and grab last element (which should be max)
O(n^2) + O(n) .
Easy.
Do a quicksort.
After the first iteration the pivot is in the right position and all values left are smaller than pivot and all values to the right are larger than the pivot.
Sort the array left of the pivot and you have the largest element, or just do comparisons.
Best case, if pivot is the largest number.
Worst case, if pivot is the smallest number.
Average case, O(log N)
1.If the array is sorted the largest element can be found at the end of array
2.If the array is not sorted traverse through the array find the max
3.If there are frequent insert options that can be taking place on the array along with the finding largest element,
- sort the array first
- do the insert options in the sorted order
- find largest element at the end of array
Hi, Please help me to understand why we need of bubble sort. This can be achieved simply traversing array once which is O(n-1).
{{class Maxinarray {
public static void main(String[] args) {
int[] a={1,5,6,8,90,4,3,2,2};
int max=a[0];
for(int i=1;i<a.length;i++)
{
if(a[i]>max) max=a[i];
}
System.out.println("Max is="+max);
}
}
}}}
- nani.m March 18, 2014