Google Interview Question
SDE1sCountry: United States
1. it's unclear why its relevant that push pushes to the head. Because if pop takes out all elements with the same probability, as soon as there is more than one element in it, the "list" acts like a perfect shuffler. What you get out is randomized, no order, nothing. So, you will need to sort in some way. That may be, you push the element and it's original position so you can reconstruct easy, or you sort the output.
2. There is no difference between 2 and 1. You see a shuffled array when you try to access the data. Where it has been shuffled is really not that much of a deal.
I sugest restating the question so it becomes clearer.
for the follow-up question, it is a min-heap supporting updating elements. Introduction to algorithm shows how to do that.
- Feng January 05, 2018