A similar problem which *is* possible is this: How would you implement a stack providing LIFO insert and delete AND the ability to report the minimum value in the stack each in constant time.
The solution is to keep a second stack for the minimum values. When an item is inserted, you push it into the minStack if it is less than or equal to the top value on the stack. When and item is deleted, pop the top value from the stack if it equals the value deleted. Then the minimum value is always on top of the stack. Don On Mar 5, 4:33 pm, Sehaj Singh Kalra <sehaj...@gmail.com> wrote: > @SAMM : Nice way to keep the track of the smallest number. But by your way > we won't be able to do search in constant time. > @Don : I was asked this question during an interview, so I think there > must/might be some possible solution. > > > > On Tue, Mar 6, 2012 at 3:55 AM, SAMM <somnath.nit...@gmail.com> wrote: > > Use two stack :- > > One stack is used for inserting and deleting the elements in the stack , > > supposing the the addition and deletion is done at the end of the stack . > > So it will be of in constant time . > > > The Second Stack is used keeping track of the smallest number . > > > For finding the element we need to used Separate Channing in hashing . > > > Take the element to be added suppose (N). > > Now compare the top element of second stack (suppose X) with N . > > > If (N < X) Added N to both the Stack . > > else if (N > X) Added N to the first Stack . > > > When the element(N) is removed from the top of the first stack. Then > > compare it with the second stack (X) . > > If (N = X) Remove N from both the Stack . > > > The Second stack will ensure that on removing or adding an element in the > > stack , The second stack will let u know the smallest element . > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
