## Flipkart Interview Question for Software Engineer / Developers

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

This prob is equiv f finding the k-smallest elements, then ans is their sum.
Find the kth smallest using QuickSelect Algo and choosing pivot by median-of-medians method. O(n)
2. Use this element to partition the array so that all smaller elements come to one side.O(n)

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

Can any one please explain the question in detail? What we need to find with an example please

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

How about creating a min heap of size k and adding elements as we scan through the array.

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

this takes O(nlogk) time..

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

This can be done easily using a deque.We loop through the array, and at the same time we keep a deque with the minimums.Always, the front of the deque will be the minimum of the current subarray of length k.At a new value, while the last value in the deque is greater than the new one, we pop it.So it the deque will remain only the smallest values. If the current value and the beginning of the deque have indexes at a distance greater than k in the array, we pop from the beginning of the deque.At last, if the current index is greater than k, we can return the front of the deque as the samllest value in the current subarray of length k.Time complexity O(N) and space O(N).

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

@bogdan.cebere
could u plz elaborate ur approch

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

@bogdan.cebere
could u plz elaborate ur approach

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

Suppose A is the original vector, N it's length and deque the vector that acts like a deque. Initially back = -1 and front = 0.In the deque vector we keep the positions possible for the answer in the current subarray of length K. First we pop values front the back of the deque as long as the value at the position deque[back] is greater than the one at the position i. After we check is i - deque[front] is less or equal than K.If it isn't, it means that the valuw at deque[front] isn't useful anymore because it is too far from to current position. Finally, if we alredy seen k numbers, it means we can start to get minimums, whick will always be stored in deque[front]. I hope it's clear

``````for(int i = 1 ; i <= N ; i++)
{
while(front<=back && a[i]<=a[deque[back]]) back--;
deque[++back]=i;
if(deque[front] == i-K) front++;
if(i >= K) printf("%d\n",a[deque[front]]);
}``````

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

so you mean to say that you can store element in sorted order in deque in O(1) operation, think carefully your algorithm require O(N*K) time complexity with O(K) extra space, it can be done to (N*log(k)) + O(1) complexity too using AVL tree, or using heap.

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

Look carefully to what I wrote. Every element in the initial array is accesed only once, so the time complexity is O(n).

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

@Nitin Agarwal,
Could you please explain the question in detail with one example?

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

That can be easily accomplished by keeping an array 'sum' which will hold the sum of previous 'k' elements(including current one) and take the min. of them. Keeping the sum can be done in O(N) time and in O(N) space (you can even get it down to O(1)).
Here is the code for the same:

``````int input[200];
int main()
{
int N,K;
cin >> N >> K;
FOR(i,0,N) cin >> input[i];
int ans = 1<<25;
int sum = input[0];
FOR(i,1,N)
{
if(i<K)
{
sum += input[i];
}
else
{
sum = input[i]+sum-input[i-K];
}
if(i>=K-1)ans = min(ans,sum);
}
if(ans == (1<<25))cout << "Doesn't exist...\n";
else cout << ans << endl;
}``````

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

P.S: I didn't used the array in above code (although in explanation I mentioned of 'sum' as an array).

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

Subarray is not contigious, So I doubt if we can do it O(n) time.
Next what should the output? subarray and minimum?

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

even the sub-array is not contiguous also one can find O(n) soln.

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

If the subarray is contiguous then scan through array once in o(n) time maintaining sums over a moving window of size k. Sum calculation for each window can be done in o(1) time by maintaining a queue structure to remove element from front of queue and add a new one to back.

If the subarray is not contiguous then scan through the array once and find the min k elements by putting them into a min heap of size k. At the end sum up the element in the heap, that is the answer

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

We can partition the array according to (i+1)th smallest element.

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.