[mavelikara]

> The fact that there's an obscure algorithm to optimally solve this doesn't mean it's not a good test of someone's ability to think through an algorithmic problem - as long as you don't make it an algorithm memorization test.

From my read of the description, the OP implies that the candidate provided (or at least, if OP were the candidate s/he would have provided) a O(n log n) solution using PQs. The task was to specifically to make the algorithm O(n), which required an obscure data structure discovered in the late 90s. So I think this is more of an algorithm memorization test.

There are very few practical problems where an O(n log n) solution is completely unacceptable, and an O(n) is essential. And in those situations, many engineers can do the relevant literature study and come up the MPQ solution.