0

This was asked to me in an interview,

I was first asked to design a stack that does getMin() in constant time. This is a fairly well known problem where you add an extra field to the stack element and maintain min value. I was then asked to extend this functionality to provide popMin() in constant time. I'm drawing a blank on how to do this. Any ideas?

Aks
  • 5,188
  • 12
  • 60
  • 101
  • Are other operations allowed to take longer than usual (e.g. Θ(log n) `push`)? If not, this would violate the Θ(n log n) bound for comparison sorts. –  Feb 05 '14 at 10:34
  • nope, all constant time. I actually suggested violating the idea of a stack by using a linked list to create the stack, keep pointers to the min nodes and then just delete them directly. Dunno if they actually felt that was ok – Aks Feb 05 '14 at 10:37
  • 6
    I'm referring to the fact that this data structure would be mathematically impossible: It would allow a linear time sorting algorithm, by inserting all items in this stack and then repeatedly `popMin()`-ing. This is well known to be impossible when you order by a black-box comparison function. If the values were integers, that might change things. Were you given any other restrictions or liberties? –  Feb 05 '14 at 10:40
  • ah, get it. but thats all they said. Implement popMin() in constant time. Maybe they wanted me to tell them it was impossible – Aks Feb 05 '14 at 10:48
  • 1
    have you read this? http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 – Daniele Feb 05 '14 at 10:58
  • @Daniele, like I mentioned, getMin is trivial. I'm talking about popMin – Aks Feb 05 '14 at 11:13
  • "This is a fairly well known problem where you add an extra field to the stack element and maintain min value" - this won't work once you `pop` the min. – Karoly Horvath Feb 05 '14 at 11:27
  • Even if you could make `popMin()` work, this wouldn't be a stack anymore, because a stack is pretty much defined by *cannot insert or remove elements in the middle*. So the question should be stated as *come up with a data structure that supports this operation and call it a stack*. – pentadecagon Feb 05 '14 at 11:31
  • @pentadecagon: "defined by" - huh? you define things by what they can do... doing the opposite wouldn't make sense. there's an infinite amount of things an entity can't do, enumerating them is futile.... – Karoly Horvath Feb 05 '14 at 11:35
  • @Karoly Let me put it this way: A stack is defined by having functions `push` and `pop`, where the latter retrieves elements in the reverse order. With this operation `popMin`, `pop` wouldn't work anymore as expected. You probably would have to redefine `pop` as *skips over elements retrieved by* `popMin`. Sure, you still can call this thing a stack, but it's pointless. You should call it something else, maybe list or priority queue or whatever. – pentadecagon Feb 05 '14 at 11:42
  • @pentadecagon: definitions: think of it as a pile of paper. push pushes to top, pop removes the top element. why wouldn't you be allowed to remove some elements from the middle? I could understand your concern if it was actually called *FIFO*, but it isn't. – Karoly Horvath Feb 05 '14 at 11:46
  • Well, I'm not alone, http://en.wikipedia.org/wiki/Stack_(abstract_data_type) says about a stack *... all additions and deletion are restricted to one end that is Top.* – pentadecagon Feb 05 '14 at 11:51
  • 1
    Perhaps the definition of popMin is to pop all items until the minimum is reached - in which case the problem becomes rather straightforward again? – Peter de Rivaz Feb 05 '14 at 11:59
  • But if `popMin` is to pop all items until the minimum is reached, then it can't be done in constant time. `popMin` becomes an O(n) operation. Likely the linked question and the accepted answer (4th or 5th comment) is what the OP is looking for. – Jim Mischel Feb 05 '14 at 15:05

1 Answers1

0

easiest: sorted linked list. more efficient - all kinds of heaps: http://en.wikipedia.org/wiki/Heap_%28data_structure%29

piotrek
  • 13,982
  • 13
  • 79
  • 165