Just like math homework back in the day, the teacher didn't do it to check your answer, they did it to check how you arrived at your answer.
I would expect a good candidate to:
1. know that a heap is optimal here (remembering whether Counter uses it is optional)
2. express reluctance to implement it from scratch because surely the stdlib can do it better.
So IMHO using libraries like this ruins the question only in the sense of showing its not a challenge for the candidate. Something so simple should not take a page of code.
Creating a heap is O(n) if I remember correctly, so that may well be the most efficient solution.
Therefore, I am unlikely to take the job.
Just to give another example, our consulting company still gets requests for projects to be deployed against Java 1.4!