## Flipkart Interview Question for Software Engineer / Developers

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

Use the partition algorithm in quicksort till there are 2 elements in the right

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

this is the best solution

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

A min heap of length 3 will do the job...

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

this is not O(n)

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

en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

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

Sorting the array has complexity O(nlogn).

Here is a O(n) solution:

Maintain a priority queue (PQ) that never grows beyond size 3, and where the order is ascending, i.e. the element in front is the lowest of the 3 elements. Step through the array. Whenever a value is greater than the front of the PQ, remove the front element from the PQ, and put the new value in its right place in the PQ. When finished, the 3rd largest integer will be in front of the PQ.

Complexity:
Scanning the array: O(n)
Replacing an element in the PQ: O(1) (since the size is a constant k=3)
Totally: O(n)

Often a heap is used for PQ, but in this case the PQ is so small that an array will do fine.

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

Insertion and deletion would still take atmost log(k).
So in your case, algorithm complexity is O(nlogk). I would prefer Fibonacci heaps since they can insert and peek at the maximum priority element in amortized constant time and deletions take O(logk). if k <<< n then this wud be very useful. else if k > n/2 then quick sort would give similar performance.

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

Find the largest integer and discard it from the array. Do this twice. Find the largest integer once more and return it. O(n) and simple to describe but not the best constant factor for O(n).

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

Heapify and Remove Three Elements

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

``````int thirdLargest(int[] arr,int k){
return createMaxHeap(arr,k);
}

int createMaxHeap(int[] arr,int k){
Heap h = new Heap(arr.length);
for(int i=0;i<arr.length;i++){
h.insert(arr[i]);
}
int max = 0;
int i = 0;
while(i < k-1){
max = h.extractMax();
i++;
}
return max;
}

class Heap{

private int[] heapArray;
private int currentSize;
private int maxSize;
private int FRONT = 1;

Heap(int maxSize){
this.maxSize = maxSize;
this.currentSize = 0;
this.heapArray = new int[maxSize];
}

public boolean insert(int key){

if(currentSize==maxSize)return false;
heapArray[currentSize] = key;
tickleUp(currentSize++);
return false;

}

public int extractMax(){
if(currentSize==0)
return Integer.MAX_VALUE;

int root = heapArray[0];

if(currentSize>1){
heapArray[0] = heapArray[currentSize-1];
maxHeapify(0);
}
currentSize--;
return root;
}

public void maxHeapify(int i){
int l = 2*i+1;
int r = 2*i+2;

int largest = i;

if(l < currentSize && heapArray[i] < heapArray[l] )
largest = l;

if(r < currentSize && heapArray[i] < heapArray[r] )
largest = r;

if(largest != i){
int t = heapArray[i];
heapArray[i] =heapArray[largest];
heapArray[largest] = t;
maxHeapify(largest);
}

}``````

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

Sort the Integer array and get the third largest interger

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

Sort the Integer array and get the third largest integer

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

do bubble sort for 3 times. o(n) as 3 is constant.

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

That's O(n*k). Since k << n ~ O(n).
so the worst case would be where k = n/2, in this case your algo would do it in O(n * n/2) i.e. O(n2). in such a case, simeple sort of O(n lg n) would be better.

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

Since the number is 3rd largest, you need to take 3 variables and set the values of max1,max2,max3 from the a[0],a[1] and a[2] elements using basic if-then compares. Now keep traversing the array till you reach the end. Every time you get a number larger than the largest i.e. max1 store it in max1 and ripple the values to max2 and max3.

What V has suggested would also work, but you traverse 3 times, here you traverse only once. The time-complexity of the algo remains the same at O(n).

For the generic kth largest element, you can use the QuickSelect or the median of median algorithm.

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

I have tried following code with basic if/else.

static void findThirdLargest(int[] array){
int max1,max2,max3;
max1=max2=max3=0;
for(int i=0;i<array.length;i++){
//Single assignment is possible
if(array[i]>max1){
max2=max1;
max3=max2;
max1=array[i];
continue;
}
if(array[i]>max2 && array[i]<max1){
max3=max2;
max2=array[i];
continue;
}
if(array[i]>max3 && array[i]<max2){
max3=array[i];
continue;
}
}
System.out.println(" Max1 -> "+max1+" Max2 -> "+max2+" Max3 -> "+max3);
}

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

Why can't we just scan the complete array 3 times to find the 3rd largest number??

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

That would be O(n*k). if k<<n its fine but for k = n/2 it would be O(N2).

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

Here k = 3, so it will do.

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

Yes we can but the method the above guy used is morec efficient and i think interviewer was expecting tht efficient algo only

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.