Flipkart Interview Question Software Engineer / Developers
Will this work if the max element happens to be a[0]?
Something like { 10, 1, 6, 8, 4, 5 }
good catch Murthy.
first two lines should be
min = min(a[0], a[1]);
max = max(a[0], a[1]);
Then it should work. Or we can start i from 0. either way should work.
minmax(int[] a,int start,int end){
if end==start
min=a[start],max=a[end]
else if end-start=1{
if(a[start]>a[end])
max=a[start]
min=a[end]
else
max=a[end]
min=a[start]
}
else{
mid=start+(end-start)/2
(min1,max1)=minmax(a,start,mid)
(min2,max2)=minmax(a,mid+1,end)
min=minimum(min1,min2)
max=maximum(max1,max2)
}
return (min,max)
}
worst case total comparisons = (2n-2),
best case total comparisons = (n-1)
questions sound dumb,dude. u sure u wanna work for this company
Hmm... Question is dumb at first go.. but try this.. you can do better in (2n-2) in worst case.
@ Baris,GekkoGordan:A linear search would do 2n-2 comparisons but here for n elts in an array no: of comparisons c(n)=2*c(n/2)+2...(2*c(n/2) is for the 2 halves and 2 is 1 for min and 1 for max)c(2)=1 is the base case...Solving u will get c(n)=3*n/2 - 2 comparisons.This is a common example of divide and conquer strategy
@Sathya: yes, a divide and conquer strategy which i believe is being abused in this case. A couple of things you got wrong about the 'minmax' function that you provided:
1. It does 2 additional comparisons before calling recursively (the first 'if' and 'else if' conditions)
2. c(2) = 2 due to the same reason above.
3. c(1) = 1 because that's when the first 'if' condition is satisfied.
3. It will be really slow compared to basic looping strategy because the your function has overhead with every function call.
So basically c(n) = 2*c(n/2) + 4 and c(2) = 2,
--> c(n) = 3*n-4. Consider example, n=8, no. of comparisons = 20.
Consider a simpler approach as below:
int min=array[0],max=array[0],i=0;
for(;i<array.size();++i)
if(min>array[i]){
min=array[i];
continue; //no need to check for max
}else if(max<array[i]){
max=array[i];
continue;
}
//The worst case for this would be a ascending series of numbers
//which gives number of comparisons including the for loop condition checking for 'i' --> (2*n - 2 + n) --> 3*n - 2
//best case would be a descending series of numbers --> (n - 1 + n) --> 2*n-1 (includes the loop condition checking)
So compared to an algorithm that always takes 3*n-4 comparisons with space and stack overhead I prefer the above approach.
Sort the array using Binary Search Tree and then report the first and last elements in the array. Takes approximately logn time
there is a better solution with 3n/2 comparisons only.
idea:
min = a[0]; max = a[1]; //note: i incremented 2 at a time for(i = 2; i < n ; i += 2) { if (a[i] < a[i+1]) { if (min > a[i]) min = a[i]; if (max < a[i+1]) max = a[i+1]; } else { if (min > a[i+1]) min = a[i+1]; if (max < a[i]) max = a[i]; } }loop is n/2 times
- yours.ramesh February 06, 2011each iteration 3 comparisons to decide min and max.
so 3n/2 comparions. let me know if it is not clear.