wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Stack Designing
        
(Message started by: gotit on Oct 9^th, 2007, 3:23pm)

Title: Stack Designing
Post by gotit on Oct 9^th, 2007, 3:23pm

How will you design a stack so that the push(),pop() and extractMin() operations are performed in constant time?

Title: Re: Stack Designing
Post by TenaliRaman on Oct 9^th, 2007, 7:20pm

Reply number 23 to 30 (roughly) here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1163814740;start=).

-- AI

Title: Re: Stack Designing
Post by gowrikumar on Oct 24^th, 2007, 11:04am

on 10/09/07 at 15:23:24, gotit wrote:

How will you design a stack so that the push(),pop() and extractMin() operations are performed in constant time?

Let's make the question a bit more interesting.

Add one more operation, DeleteMin also.
Can we still perform all the operations in O(1) time?

Regards,
Gowri Kumar