## Indeed Interview Question for SDE-2s

- 0of 0 votes

AnswersYou are given an array of length N consisting of integers, a={a1,…,aN}, and an integer L.

- neer.1304 August 15, 2019 in United States

Consider the following subproblem:

• You are given an integer S.

• Find the largest value in the interval [S,S+L−1] in the sequence a, that is, find max(aS,…,aS+L−1).

Solve this subproblem for every S=1,…,N−L+1.

Constraints

• 1≤N≤105

• 1≤L≤N

• −109≤ai≤109

Input

Input is given from Standard Input in the following format: N L a1 … aN

Output

Print the answers in N−L+1 lines. The i-th line should contain the answer to the subproblem where S=i.

Sample Input 1

5 3

3 4 2 1 5

Sample Output 1

4

4

5

• The subproblem where S=1 asks the largest value among a={a1,a2,a3}={3,4,2}, so the first line in the output should contain 4.

• The subproblem where S=2 asks the largest value among a={a2,a3,a4}={4,2,1}, so the second line in the output should contain 4.

• The subproblem where S=3 asks the largest value among a={a3,a4,a5}={2,1,5}, so the third line in the output should contain 5.

Sample Input 2

4 1

-1000000000 1000000000 -1000000000 1000000000

Sample Output 2

-1000000000

1000000000

-1000000000

1000000000| Report Duplicate | Flag | PURGE

Indeed SDE-2 Algorithm

**Country:**United States

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Essentially it is asking for the largest element in the set of L consecutive elements of array 'a' and the L slides from left to right as S goes from 1 to N-L+1

- Anon November 25, 2019In other words, the largest element in the first L elements, then the largest element in L elements starting from the 2nd element, then the largest of the L elements starting from 3 and so on till the index N-L+1, the last possible set of L elements

A max-heap is probably a decent way to solve this

[Heapify]

Read the first L elements (of array 'a') into a heap (which can be done in O(n))

the max element [obtained in O(logn)] corresponds to S=1

[Loop]

Insert the next element into the heap [in O(logn)] and get the max element [O(logn)].

This corresponds to S=2, if this element is in 'a' at index greater than or equal to S (or S-1, if array indices start at 0). If not, remove the max element(s) till one meets this criteria [O(logn)]

Insert the next element for get max for S=3

and so on..

Couple of things:

1) To support the index check without deteriorating to O(n) , the nodes of the heap is a slightly enhanced data structure. So the i-th entry into heap is not just the value a[i] but instead the node

HeapNode[

value = a[i]

index = i

]

The heap operations are based on 'value' while the 'index' would be used to weed out max-elements that have fallen out of the current window of L elements.

2) It might seem that the number of delete operations could balloon up to n thus giving an nlogn bound... however, on the whole sequence it amortizes to 1 delete for each S.. this is because the number of inserts are upper bounded by N and thus so would be the deletes