## Indeed Interview Question for SDE-2s

Country: United States

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

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
In 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

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.