## Flipkart Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

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
each iteration 3 comparisons to decide min and max.
so 3n/2 comparions. let me know if it is not clear.

Comment hidden because of low score. Click to expand.
0

Will this work if the max element happens to be a[0]?

Something like { 10, 1, 6, 8, 4, 5 }

Comment hidden because of low score. Click to expand.
0

if i starts from 0, it works. I guess you need a small change. Good algorithm..

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Small correction: I think we dont need two comparisons in initializing min and max. I think this will also work

min = a[0];
max = a[1];

if(arr[0] > arr[1]){
max = arr[0];
min = arr[1];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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)``````

}

Comment hidden because of low score. Click to expand.
0

"else if end-start=1"

lvalue required as left operand of assignment

Code is wrong..

Comment hidden because of low score. Click to expand.
0
of 0 vote

How is this asymptotically any better than a linear search? In fact I think a linear search would perform better with larger arrays. Unless I am missing something?

Comment hidden because of low score. Click to expand.
0
of 0 vote

worst case total comparisons = (2n-2),
best case total comparisons = (n-1)
questions sound dumb,dude. u sure u wanna work for this company

Comment hidden because of low score. Click to expand.
0

Hmm... Question is dumb at first go.. but try this.. you can do better in (2n-2) in worst case.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

@ 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

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array using Binary Search Tree and then report the first and last elements in the array. Takes approximately logn time

Comment hidden because of low score. Click to expand.
0

time complexity for that is
nlogn (to build BST ) + logn

Comment hidden because of low score. Click to expand.
0

number of comparison will be more as well as complexity...

Comment hidden because of low score. Click to expand.
0
of 0 vote

int max = a[0]
int min = a[0]

for ( i = 0; i< a.length ; i++)
{
if(a[i] < min) {min = a[i];} else if (a[i] > max) { max = a[i];}
}

Total of n -1 comparisons. O(n) solution

}

Comment hidden because of low score. Click to expand.
0

@Umesh. each time you are doing 2 comparisions (one for min, one for max). and it is for n-1 elements. so it is 2(n-1) comparisions i guess

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Why don't we simply use merge sort and take the first and last number in the array
The time complexity would be nlogn for this solution``````

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.

### 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.