Indeed Interview Question SDE-2s
Country: United States
is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
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