Literally came out of our work queue. Couldn't find a satisfactory off-the-shelf component for it, needed one built. Afterwards we liked it as a technical interview question.
If I was doing it today I'd use some sort of balanced tree using the priority to navigate the nodes. Each node would have pointers to the head and tail of a singly linked list. Insert when the priority isn't in the tree is a simple tree insert with head and tail pointing to a new single-element linked list, insert when the priority is in there is adding it to the tail of the right node and moving the tail pointer, removing is finding the right-most node, taking the head and advancing the head pointer by one element. If the list is now empty then delete the node.
But none of it matters. I don't care if someone would build it the way I would. I would never expect that. I don't even want an optimal or semi-optimal answer. I'd have accepted a singly linked list with O(n) insertion time and O(1) pop time. Or a plain list where new items are added to the end and a pop is an O(n) seek through the list.
What I care about is whether the developer come up with any solution, describe the tradeoffs that they are making, why they are making them, and what research they would do if any to find a better solution. If i could have this conversation that we're having right here, right now with them then they'd probably pass my hiring bar.
A binary heap has some advantages over using a balanced tree that could have significant performance impacts (and vice versa). Particularly in a situation where you need to roll your own priority queue.
That's why I said it's likely the person who built it would done a bit of research. When hiring someone I care that they remember enough to realize that and are capable of doing the research, more than that they remember exactly how to implement some data structure.
>If I could have this conversation that we're having right here, right now with them then they'd probably pass my hiring bar.
I think that's a totally reasonable. My problem is that this isn't what people are complaining about when complaining about white board interviews.
99% of the time the interviewer is asking for the answer to a very specific problem that is highly biased towards new grads who would have just seen it on a test.
And even if they say you don't care about the optimal solution they will always hire the person who gets the optimal solution in 15 minutes b/c they memorized it versus the person takes 30 min to bang out something that kind of works.
Here's my approach:
I ask someone else on my team to come up with an interview problem, so I haven't seen it before hand. Then I work with the candidate on hashing out a solution.