## Interview Question

Country: India
Interview Type: Written Test

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

We need K variables to find minimum of K elements at any time.
Algo: i=0, K=user_input
Repeat the following steps from i=0 to i=N-K+1
1) Start traversing array from index i, moving towards right, considering K elements at a time.
2) Find min of K elements i.e A[i+0] to A[i+K-1]. Complexity=O(K)
3) Update B[i] with value as in step (2).
4) Increment i.

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

tere ko pakad pakda ke chodu learner

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

tere ko pakad pakda ke chodu learner

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

use heap

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

If we are starting from the first element on right then the B[1] = A[1]. now at every step we are adding on more element to compute the next min element.

-Let say we are trying to evaluate B[x] where x is in range i =< x <= n-k+1.
-B[x-1] already contains the min among A[i] - A[x-1].
-Now we compare A[x] to B[x-1].
-If A[x] < B[x-1] then B[x] = A[x] else B[x] = B[x-1].
-Itereate over the entire list in similar way.
I guess complexity will be O(n) and no extra space is required except the new array that we are creating.

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.