Title: A friend of mine is being interviewed for Big 4. In the first round of screening, (s)he was asked about a linear time algorithm to find all the maximum element in a sliding window in an array.<p>Now this is a simple problem for anyone who has taken any DS or Algo Undergraduate level class since it involves the important concept of the priority queue. However, it is my understanding that to do this in a linear time is neither trivial nor straightforward and unless that person is really gifted. (Its something called Monotone Priority Queue which is not present in any standard Algorithm textbook) So my question to the general populace is: Are knowing obscure algorithms like this any test of a person&#x27;s programming ability ?
Upvote: