[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations. How about a circular doubly linked list for the push and pop, and then a priority queue for the min? -- 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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@above What is the complexity of the pop_front() operation? -- 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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@above What is the complexity of the pop_front() operation? O(1) -- 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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@above Really? When one removes head then, min element should be updated. -- 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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@juver, thanks for the explanation... but a few more queries... In my implementation, when I delete first element, why should we access all other elements? I should do that if the element i'm deleting is the current minimum... or is my understanding of get_min() totally wrong? I assumed get_min() should return the smallest item in the queue... On Jan 10, 11:20 pm, juver++ avpostni...@gmail.com wrote: About 2 stack implementation. Yes some operations can be O(n) as a separate estimation. But all other will be constant, cause we access elements at most twice. So for the sequence of M operations (pop,push,min) total complexity will be O(M), so the average cost of each operations is O(1). There are no two consecutive operations which are linear. But in your implementation, when you delete first element, you will access all remaining elements. So, it is O(n) for every operation of delete! Insert M numbers, then remove all elements with accessing to the min item - this will cost you O(M*M) for all, and O(M) in average! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
You are right about purpose of get_min(). Please post detailed pseudocode for each operation. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Queue: 1 2 3 4 1 5 6 7 1. After deleting from the head, you always should update minimum element for O(n). However, there is another way for queue modification, so the current min is accessed for O(1). This can be done using queue and initial elements (may be in a separate queue). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Ok so here's the pseudocode...
class MyQueue
{
int? currentMinVal; //nullable
LinkedListint contents;
public void MyQueue()
{
contents = new LinkedListint();
currentMinVal = null;
}
//the regular implementations of insert and delete are below...
insert_rear, delete_front can be just as easily implemented as my
contents are in a linked list
public void Insert(int item)
{
contents.AddLastint(item); //add item to the linked list
//set the current min... O(1) operation
if(currentMinVal == null || currentMinVal.Value item)
currentMinVal = item;
}
public int Delete()
{
if(!contents.IsEmpty)
{
int itemToreturn = contents.First.Value;
contents.RemoveFirst(); //some method of linked list
that removes specified element from the linked list and adjusts head
and tail pointers
if(itemToRetun == currentMinVal) // check if the
item you remove is the current minimum...
RecomputeMinValue(); //O(n) operation to
set the new minimum
return itemToReturn;
}
else
throw new InvalidOperationException();
}
public int? get_min()
{
return currentMinVal;
}
}
For this, it's not true that for all deletes, I need to do a O(n)
operation O(n) operation on delete is needed only if the currently
deleted item is the current min...
for Queue: 1 2 3 4 1 5 6 7 1, the linked list will have 1 -7-6-5-
1-4-3-2-1 currentMinVal = 1. on first delete, since 1 is
going to be deleted, currentMin will be once again computed O(n)...
its once again 1 on second delete, the item to be deleted is 2...
this is not the current min... so we don't do a O(n) traversal of the
list to get the new currentMin...
On Jan 11, 6:35 am, juver++ avpostni...@gmail.com wrote:
Queue: 1 2 3 4 1 5 6 7 1. After deleting from the head, you always should
update minimum element for O(n).
However, there is another way for queue modification, so the current min is
accessed for O(1).
This can be done using queue and initial elements (may be in a separate
queue).
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
And what about the 1 2 3 1 1 1 1 1 1 1 3 5 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1. Your algo is inefficient in all cases. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
The best way to check your algo on practice, generate a very big test case with many operations. Check the time and amount of accesses for each element. In your case you have O(n) for the operation on average. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
yes... thats true... for the amortized constant time algo, u do a O(n)
operation for one of the delete operations... my version does a O(n)
operation for deletes of the min element... Min element can be deleted
only when it's either in the front or at the back (using delete_front
or the regular delete)...
In the amortized constant time algo, if you perform delete_rear and
delete_front in succession, it's gonna take O(n) time for each
operation... In my version, if the queue is sorted in one direction
and delete is performed on the min side, each operation will take O(n)
time...
On Jan 9, 10:49 pm, yq Zhang zhangyunq...@gmail.com wrote:
Then it is O(n) worst case. While juver's algo is amortized constant time in
worst case.
On Jan 9, 2011 10:26 PM, SVIX saivivekh.swaminat...@gmail.com wrote:
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9, 10:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min
value
for all remaining nodes.
So it's linear.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group. To post to this group, send email to
algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
. For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
You should analyze your algo more precisely and study something about amortized time complexity. Your delete operation takes O(n) time for EVERY query. So for the sequence of M deletetions there is an average time O(N) which is NOT constant on the worst case. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@ Juver, I got the following response in the group digest mail. It'll be great if you can provide some inputs so I can refine my understanding... Could you please help me understand how my delete operation takes O(n) time for every delete? I propose to maintain the minimum at the queue level (one variable for the entire queue object) which can change on each insert (O(1) operation to see if the newly inserted item is the new minimum) and on delete of a current min item, a O(n) list traversal is required to figure out what the min is now... if the deleted item is not the current min, no updates to current minimum value need to be made... I did a little bit of reading on amortized complexity. You're definitely correct. I don't know as much as you probably do on that subject. But is the following statement about the 2 stack implementation correct? After inserting a bunch of items, say 1, in your queue (which fills up stack 1), lets say you do delete_rear (u need to pop all items from stack 1 and push them in stack 2) and then a delete_front (pop from second stack and push all into first) in succession until the queue is empty, wont each operation cost O(n)? Based on my preliminary understanding, to estimate amortized complexity, we can ignore O(n) operations provided they occur only once in every K operations... but when there's a chance that they can occur for every 1 operation, that's the worst case scenario there. would it still be amortized... Pls Note: this is just to better my understanding.. am not challenging anybody... --- juver++ avpostni...@gmail.com Jan 10 06:25AM -0800 ^ You should analyze your algo more precisely and study something about amortized time complexity. Your delete operation takes O(n) time for EVERY query. So for the sequence of M deletetions there is an average time O(N) which is NOT constant on the worst case. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
About 2 stack implementation. Yes some operations can be O(n) as a separate estimation. But all other will be constant, cause we access elements at most twice. So for the sequence of M operations (pop,push,min) total complexity will be O(M), so the average cost of each operations is O(1). There are no two consecutive operations which are linear. But in your implementation, when you delete first element, you will access all remaining elements. So, it is O(n) for every operation of delete! Insert M numbers, then remove all elements with accessing to the min item - this will cost you O(M*M) for all, and O(M) in average! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Use a linked list (maintain both head and tail positions) and treat it as a queue insert/delete front or back... whatever... For each insert, see if it's less than the current min and maintain min... If you're deleting the current min, you may traverse from head to tail and recompute the min... On Jan 1, 9:23 pm, sourav souravs...@gmail.com wrote: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
All operations should constant at least on average. So your idea is not suitable. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
why's the linked list option not constant (at least for most cases)? the time's not constant only for delete operation (that too only if you delete the current min)... otherwise, everything is a O(1) operation... get_min() already has the min... push_rear(), pop_front() - you're maintaining the head and tail positions of the linked list... so u can easily do these... On Jan 9, 11:22 am, juver++ avpostni...@gmail.com wrote: All operations should constant at least on average. So your idea is not suitable. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
When you remove element from the front of queue, you should update min value for all remaining nodes. So it's linear. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min value
for all remaining nodes.
So it's linear.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9, 10:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min value
for all remaining nodes.
So it's linear.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Then it is O(n) worst case. While juver's algo is amortized constant time in
worst case.
On Jan 9, 2011 10:26 PM, SVIX saivivekh.swaminat...@gmail.com wrote:
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9, 10:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min
value
for all remaining nodes.
So it's linear.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@Juvier, @yq Zhang
In your approach, when you are asked pop_front() you keep popping from
one stack and pushing them to another and then from the other pop the
top element. What happens is this top element happens to have been the
Min element?Example
stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = ( element, min)
then you are asked pop_front(), you push to another stach like below
stck2: {(6,2),(3,2),(4,2),(2,2)}.
Then you remove (2,2)! Ok. But all elements in your stack2 still say
2 is the min element. But 2 is no more in the queue (or for that
matter in the stacks we are using).
On Jan 4, 9:07 am, yq Zhang zhangyunq...@gmail.com wrote:
@sourav,
As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's
because each element can be at most popped twice.
Thanks
Yq
On Mon, Jan 3, 2011 at 11:20 AM, sourav souravs...@gmail.com wrote:
@yq Zhang,
To pop if you are going to pop all from first stack and push into the
second stack, then does your operation remain constant time? Please
note that we need constant time implementation for the 3 functions
pop_front, push_rear and get_min(). Goint by your approach, not all of
them are constant time.
Thanks,
Sourav
On Jan 3, 9:44 pm, yq Zhang zhangyunq...@gmail.com wrote:
Push into one stack. When pop first pop all from the first stack and push
into the second stack. Then pop from the second stack
On Jan 3, 2011 7:42 AM, MOHIT mohit...@gmail.com wrote:
if only two stack are used but how pop_front is get?
suppose if element comes in order
12 15 4 3 7 20
then in min queue
1. 12 (12)
2. 12 12 (12,15)
3. 12 12 4 (12,15,4)
4.12 12 4 3 (12,15,4,3)
5.12 12 4 3 3 (12,15,4,3,7)
6.12 12 4 3 3 3 (12,15,4,3,20)
we can get min in constant by pop of stack but how pop front will work
using
two stack only in constant time?
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group. To post to this group, send email to
algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
. For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
When you push into stack2, you have to recompute the min value. So after you
push into stack2, it will be:
(6,6),(3,3),(4,3),(2,2)
On Thu, Jan 6, 2011 at 6:34 PM, sourav souravs...@gmail.com wrote:
@Juvier, @yq Zhang
In your approach, when you are asked pop_front() you keep popping from
one stack and pushing them to another and then from the other pop the
top element. What happens is this top element happens to have been the
Min element?Example
stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = ( element, min)
then you are asked pop_front(), you push to another stach like below
stck2: {(6,2),(3,2),(4,2),(2,2)}.
Then you remove (2,2)! Ok. But all elements in your stack2 still say
2 is the min element. But 2 is no more in the queue (or for that
matter in the stacks we are using).
On Jan 4, 9:07 am, yq Zhang zhangyunq...@gmail.com wrote:
@sourav,
As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's
because each element can be at most popped twice.
Thanks
Yq
On Mon, Jan 3, 2011 at 11:20 AM, sourav souravs...@gmail.com wrote:
@yq Zhang,
To pop if you are going to pop all from first stack and push into the
second stack, then does your operation remain constant time? Please
note that we need constant time implementation for the 3 functions
pop_front, push_rear and get_min(). Goint by your approach, not all of
them are constant time.
Thanks,
Sourav
On Jan 3, 9:44 pm, yq Zhang zhangyunq...@gmail.com wrote:
Push into one stack. When pop first pop all from the first stack and
push
into the second stack. Then pop from the second stack
On Jan 3, 2011 7:42 AM, MOHIT mohit...@gmail.com wrote:
if only two stack are used but how pop_front is get?
suppose if element comes in order
12 15 4 3 7 20
then in min queue
1. 12 (12)
2. 12 12 (12,15)
3. 12 12 4 (12,15,4)
4.12 12 4 3 (12,15,4,3)
5.12 12 4 3 3 (12,15,4,3,7)
6.12 12 4 3 3 3 (12,15,4,3,20)
we can get min in constant by pop of stack but how pop front will
work
using
two stack only in constant time?
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group. To post to this group, send email to
algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@googlegroups.com
. For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
only 2 stacks, one of them (or both...) should provide functionality for retrieving minimum. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Good point. Right. But we can avoid first stack of such structure, having separate variable (Minimum) for this. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
That's a big save of space! On Jan 5, 2011 9:03 AM, juver++ avpostni...@gmail.com wrote: Good point. Right. But we can avoid first stack of such structure, having separate variable (Minimum) for this. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Yes, you are right. Stack contains the following pair of elements - (Min, Element), where Min - minimum element among all elements in the stack below the current, Element - current element. When you add new element onto the stack, then you should push pair(min(stack.top().Min, Element), Element). To retrieve min element from the stack, simply access its top min. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@yq Zhang, To pop if you are going to pop all from first stack and push into the second stack, then does your operation remain constant time? Please note that we need constant time implementation for the 3 functions pop_front, push_rear and get_min(). Goint by your approach, not all of them are constant time. Thanks, Sourav On Jan 3, 9:44 pm, yq Zhang zhangyunq...@gmail.com wrote: Push into one stack. When pop first pop all from the first stack and push into the second stack. Then pop from the second stack On Jan 3, 2011 7:42 AM, MOHIT mohit...@gmail.com wrote: if only two stack are used but how pop_front is get? suppose if element comes in order 12 15 4 3 7 20 then in min queue 1. 12 (12) 2. 12 12 (12,15) 3. 12 12 4 (12,15,4) 4.12 12 4 3 (12,15,4,3) 5.12 12 4 3 3 (12,15,4,3,7) 6.12 12 4 3 3 3 (12,15,4,3,20) we can get min in constant by pop of stack but how pop front will work using two stack only in constant time? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Simulate queue using two stacks. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@juver++ how will implwment find_min() function? On Sun, Jan 2, 2011 at 2:33 PM, juver++ avpostni...@gmail.com wrote: Simulate queue using two stacks. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
keep min for stack is easy. just use another stack to keep the min for each top. Sent from Nexus one On Jan 2, 2011 11:43 AM, Anuj Kumar anuj.bhambh...@gmail.com wrote: @juver++ how will implwment find_min() function? On Sun, Jan 2, 2011 at 2:33 PM, juver++ avpostni...@gmail.com wrote: Simulate queue using two stacks. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
