check the link given by DK for queue and see my post in this thread for
stack for doing in O(1)..you guys are discussing the things which are
already discussed !!
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Mon, Aug 1, 2011 at 11:20 AM, Aman
@ankit i am saying at the time of insertion of first element to last we
have to maintain a min element which store the min number
--
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.
using LL u cant delete in O(1) ... u have to traverse from head
On Jul 31, 1:47 pm, Shubham Maheshwari shubham@gmail.com wrote:
use a doubly linked list ... with a field node *min.
weneva you insert an element ... check for the value of min at the head ...
if the new inserted node has
its a *doubly* linked list ...
you can easily do the job ...
On Sun, Jul 31, 2011 at 2:23 PM, siva viknesh sivavikne...@gmail.comwrote:
using LL u cant delete in O(1) ... u have to traverse from head
On Jul 31, 1:47 pm, Shubham Maheshwari shubham@gmail.com wrote:
use a doubly linked
@shubham...i have a doubt.can't the same be done with singly linked list??
--
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
you mean circular linked list ...!!!
in case of stack ... we cn do it via SSL ...
for a queue implementation ... we will ned circular, or doubly for deletion
in O(1).
On Sun, Jul 31, 2011 at 2:38 PM, naveen ms naveenms...@gmail.com wrote:
@shubham...i have a doubt.can't the same be done with
Use a circular linked list with elements being inserted in sorted order.
Inserting minimum element :
struct node *p;
p is a pointer to last node in the circular singly linked list.
newmin-next=p-next;
p-next=newmin;
Deleting minimum element:
struct node *temp;
temp=p-next;
p-next=p-next-next;
hw cn u ensure that the elements are inserted in sorted order ...
wat if the elements are coming randmly ...
On Sun, Jul 31, 2011 at 2:49 PM, muthu raj muthura...@gmail.com wrote:
Use a circular linked list with elements being inserted in sorted order.
Inserting minimum element :
@shubham maheshawari
deletion can't be performed in O(1).
after extracting the min element, we need to find the next minimum element,
and worst case will take O(n) time.
On Sun, Jul 31, 2011 at 3:00 PM, Shubham Maheshwari
shubham@gmail.comwrote:
hw cn u ensure that the elements are
the operation is nt extract min ... its *find* min ...
On Sun, Jul 31, 2011 at 3:02 PM, Abhishek Gupta gupta.abh...@gmail.comwrote:
@shubham maheshawari
deletion can't be performed in O(1).
after extracting the min element, we need to find the next minimum element,
and worst case will
Qn is : Create a data structure where inserting, deleting and finding the
minimum element all have O(1) time.
so after deleting the minimum element, where will you point min pointer?
Sorry if i m wrong
On Sun, Jul 31, 2011 at 3:11 PM, Shubham Maheshwari
shubham@gmail.comwrote:
the
i am givin solution for implementing a queue or a stack ...
in which ...inserting, delelting and finding min element is of O(1).
hope this is clear now ...
On Sun, Jul 31, 2011 at 3:19 PM, Abhishek Gupta gupta.abh...@gmail.comwrote:
Qn is : Create a data structure where inserting, deleting and
here is what i think should be done to do thees operations in O(1)it is
quite popular interview question..
i am using two stacks
one stack arr[] in which elements in the elements will be pushed as they are
normally done in a stack
maintain another stack min[]whenever you insert an element
Guys the real question is :
Design a data structure which support following operation
1. insertion of an arbitrary element
2. removing the oldest element
3. Accessing min element
--
*With Regards :*
Ravinder Kumar
B.Tech Final Year
Computer Science and Engineering
MNNIT Allahabad
--
You
I think the exact question resembles as what ravinder kumar
saidAnd all these operations in O(1) time...ideas plz
On Jul 31, 5:21 pm, Ravinder Kumar ravinde...@gmail.com wrote:
Guys the real question is :
Design a data structure which support following operation
1. insertion of an
O(1) is possible in normal LL in below case:
i.If u have head then insertion , deletion and accesss to first element at
front .
ii.if u have tail then insertion and access to element at last .
if anything missing add anout normal LL
On Sun, Jul 31, 2011 at 9:47 PM, siva viknesh
i think you can just enter elements in a sorted order ( ie applying
insertion sort as the elements are added ) like we do in Bucket sort ..
maintaining sorted buckets for a hash value ..
and maintaining the min element at the head always we can do deletion of min
and finding min in O(1) time
This question has already been discussed in depth previously:
There are 2 ways to do this:
1. Using 4 stacks (actually 2 min stacks)
2. Using a queue and a deque
A highly detailed, easy to understand discussion of the problem
has already taken place in the group previously:
The complete
I think its stack where deletion insertion and finding min (as we will cal
min at the time of insertion only by taking min val ) will take O(1) time
correct me if i am worng...!
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
finding min will not take O(1) time in a stack i guess
On Mon, Aug 1, 2011 at 10:32 AM, kartik sachan kartik.sac...@gmail.comwrote:
I think its stack where deletion insertion and finding min (as we will cal
min at the time of insertion only by taking min val ) will take O(1) time
correct me
Think in terms of vector(C++, STL) :P
On Mon, Aug 1, 2011 at 11:01 AM, ankit sablok ankit4...@gmail.com wrote:
finding min will not take O(1) time in a stack i guess
On Mon, Aug 1, 2011 at 10:32 AM, kartik sachan kartik.sac...@gmail.comwrote:
I think its stack where deletion insertion and
(C(n+1,2))* (C(n+1,2))
choosing any two rows from n+1 rows, and any two columns from n+1 columns
will yield a rectangle .
So solution is the no of possible combinations.
On Wed, Jul 27, 2011 at 11:23 PM, Abhinav Arora
abhinavdgr8b...@gmail.comwrote:
It will be (1+2+3+,,,+n)^2.u can verify
It will be (1+2+3+,,,+n)^2.u can verify it for a chess board hich will
have 1296 rectangles for n=8
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
C(n+1,2)^2
--
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
oh...i forgot the case that a square is also a rectangle!!
On Jul 27, 11:48 pm, SkRiPt KiDdIe anuragmsi...@gmail.com wrote:
C(n+1,2)^2
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
25 matches
Mail list logo