Author |
Topic: Data structures (Read 1471 times) |
|
alexeigor
Newbie
Posts: 45
|
 |
Data structures
« on: Dec 12th, 2008, 7:28am » |
 Quote  Modify
|
1. Design queue with operations GetMax O(1), Enqueue O(1), Dequeue O(1), O(n) mem.
2. Design immutable queue.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Data structures
« Reply #1 on: Dec 12th, 2008, 7:44am » |
Quote Modify
|
Could you define what an "immutable queue" is? It sounds a bit like an oxymoron.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Data structures
« Reply #3 on: Dec 12th, 2008, 7:56am » |
Quote Modify
|
So basically for 2) you could take an array (or list), point to the start and end of the used area, and just never remove the front when you move that pointer forward after dequeuing?
Perhaps keep a second list/array to keep a history so you can undo any step (undoing dequeuing or enqueing consists merely of putting the respective pointer back a step).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Data structures
« Reply #4 on: Dec 12th, 2008, 8:46am » |
Quote Modify
|
In Java:
1) import java.util.*;
class MaxQueue<E extends Comperable<? super E> > {
private Queue<E> _queue, _max;
public MaxQueue() {
_queue = new LinkedList<E>();
_max = new LinkedList<E>();
}
public void enqueue(E elem) {
_queue.add(elem);
if (_max.isEmpty() || elem.compareTo(_max.element()) >= 0) {
_max.add(elem);
}
}
public E dequeue() {
if (_queue.element().compareTo(_max.element()) == 0) {
_max.remove();
}
return _queue.remove();
}
public E getMax() {
return _max.element();
}
}
2) import java.util.*;
class PersistentQueue<E> {
private List<E> _list;
private int _first, _last;
private PersistentQueue(List<E> list, int first, int last) {
_list = list; _first = first, _last = last;
}
public PersistentQueue() {
_list = new ArrayList<E>();
_first = _last = 0;
}
public PersistentQueue<E> enqueue(E elem) {
if (_last == _list.size()) {
_list.add(elem);
return new PersistentQueue(_list, _first, _last + 1);
} else {
List<E> copy = new ArrayList<E>(_list);
copy.remove(_last); copy.add(elem);
return new PersistentQueue(copy, _first, _last + 1);
}
}
public E front() {
if (_first == _last) throw new NoSuchElementException();
return _list.get(_first);
}
public PersistentQueue<E> dequeue() {
if (_first == _last) throw new NoSuchElementException();
return new PersistentQueue(_list, _first + 1, _last);
}
}
--SMQ
Edit: for 2) need to fork the queue (create a copy) if more than one element is enqueued to the same instance.
|
| « Last Edit: Dec 12th, 2008, 9:04am by SMQ » |
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Data structures
« Reply #5 on: Dec 12th, 2008, 11:40am » |
Quote Modify
|
I'm not quite sure that solution for 1) works. Either that or I can't figure out the code.
enqueue(3)
q[3]-m[3]
enqueue(4)
q[3,4]-m[3,4]
enqueue(1)
q[3,4,1]-m[3,4]
dequeue(3)
q[4,1]-m[3,4]
dequeue(4)
q[1]-m[3]
getMax()
-> 3?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Data structures
« Reply #6 on: Dec 12th, 2008, 12:12pm » |
Quote Modify
|
m is a queue as well, not a stack, do dequeue(3) leaves m[4], but then dequeue(4) leaves m[] so it still doesn't work... whoops 
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Data structures
« Reply #7 on: Dec 13th, 2008, 12:20pm » |
Quote Modify
|
I have known the problem 1) already. I present my amortised O(1) solution.
Maintain 2 queues, first containing all numbers, 2nd only decreasing subsequence ... whenever number is enqued, it is enqued to the first and all smaller (at the end) of the 2nd are removed prior the enqueing. Max query is answered by the first element of the 2nd queue. Technical problem with duplicates can be solved by count in the 2nd list. Dequeuing in the second list is performed only if the first value in both lists equals. It is actually replaced by count decrement if the count was nonzero.
What about the worst case?
|
|
IP Logged |
|
|
|
alexeigor
Newbie
Posts: 45
|
|
Re: Data structures
« Reply #8 on: Dec 13th, 2008, 1:18pm » |
Quote Modify
|
Looks good
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Data structures
« Reply #9 on: Dec 14th, 2008, 12:57pm » |
Quote Modify
|
It is not final solution, this can be done worst case!
It's only a hint 
|
|
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Data structures
« Reply #10 on: Dec 14th, 2008, 11:59pm » |
Quote Modify
|
I have known the problem 1) already. I present my amortised O(1) solution.
Quote:| Maintain 2 queues, first containing all numbers, 2nd only decreasing subsequence ... whenever number is enqued, it is enqued to the first and all smaller (at the end) of the 2nd are removed prior the enqueing. Max query is answered by the first element of the 2nd queue. Technical problem with duplicates can be solved by count in the 2nd list. Dequeuing in the second list is performed only if the first value in both lists equals. It is actually replaced by count decrement if the count was nonzero. |
|
can you explain it with example?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Data structures
« Reply #11 on: Dec 15th, 2008, 12:47am » |
Quote Modify
|
on Dec 14th, 2008, 11:59pm, nks wrote:| can you explain it with example? |
|
enqueue(3)
q[3]-m[3(1)]
enqueue(4)
q[3,4]-m[4(1)]
enqueue(3)
q[3,4,3]-m[4(1),3(1)]
enqueue(4)
q[3,4,3,4]-m[4(2)]
enqueue(1)
q[3,4,3,4,1]-m[4(2),1(1)]
enqueue(2)
q[3,4,3,4,1,2]-m[4(2),2(1)]
dequeue()
q[4,3,4,1,2]-m[4(2),2(1)]
dequeue()
q[3,4,1,2]-m[4(1),2(1)]
getMax()
-> 4
dequeue()
q[4,1,2]-m[4(1),2(1)]
dequeue()
q[1,2]-m[2(1)]
getMax()
-> 2
|
| « Last Edit: Dec 15th, 2008, 12:54am by Hippo » |
IP Logged |
|
|
|
nks
Junior Member
Gender:
Posts: 145
|
|
Re: Data structures
« Reply #12 on: Dec 15th, 2008, 3:33am » |
Quote Modify
|
At the 3 rd step
Quote:enqueue(3)
q[3,4,3]-m[4(1),3(1)] |
|
Should not it be q[3,4,3]-m[4(1),3(2)] ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Data structures
« Reply #13 on: Dec 15th, 2008, 3:51am » |
Quote Modify
|
on Dec 15th, 2008, 3:33am, nks wrote:At the 3 rd step
Should not it be q[3,4,3]-m[4(1),3(2)] ? |
|
No, because for the first 3 in the queue the maximum is still 4. It isn't until the 4 is dequeued that the (later) 3 can be a maximum (if a higher number hasn't been enqueued yet).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Data structures
« Reply #14 on: Dec 16th, 2008, 5:08am » |
Quote Modify
|
Would someone else write about eliminating the drawback in amortized complexity ... some operations took O(n) time, while the "average" O(1) is maintained?
(Case n,(n-1),...,1,(n+1) are enqued in this order...)
|
|
IP Logged |
|
|
|
miletus
Newbie
Posts: 4
|
|
Re: Data structures
« Reply #15 on: Jan 4th, 2009, 4:12am » |
Quote Modify
|
recall that how one can simulate a queue using two stacks: stack1 and stack2
1) for enqueue, push the element into stack1
2) for dequeue, pop stack2 and if stack2 is empty,
then dump element from stack1 to stack2
also recall that how a stack can be augmented
to support getMax() operation in O(1), using an
auxiliary stack to record the max values ( which
has been discussed in another thread )
so , for problem 1), we can maintain 3 stacks:
1) stack1, for enqueue
2) stack2, for dequeue
3) stack3, that stack3.top() is the current max
value for stack2
also we need an extra variable max1 to record
the max value of stack1
so the GetMax() = max( max1, stack3.top() )
|
|
IP Logged |
|
|
|
alexeigor
Newbie
Posts: 45
|
|
Re: Data structures
« Reply #16 on: Jan 4th, 2009, 11:01am » |
Quote Modify
|
looks very good
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Data structures
« Reply #17 on: Jan 4th, 2009, 3:16pm » |
Quote Modify
|
And the good thing is that a stack can easily be implemented as a permanent structure, answering (2) (in 1st post)
|
| « Last Edit: Jan 4th, 2009, 3:17pm by Grimbal » |
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Data structures
« Reply #18 on: Jan 4th, 2009, 3:22pm » |
Quote Modify
|
on Jan 4th, 2009, 4:12am, miletus wrote:recall that how one can simulate a queue using two stacks: stack1 and stack2
1) for enqueue, push the element into stack1
2) for dequeue, pop stack2 and if stack2 is empty,
then dump element from stack1 to stack2
also recall that how a stack can be augmented
to support getMax() operation in O(1), using an
auxiliary stack to record the max values ( which
has been discussed in another thread )
so , for problem 1), we can maintain 3 stacks:
1) stack1, for enqueue
2) stack2, for dequeue
3) stack3, that stack3.top() is the current max
value for stack2
also we need an extra variable max1 to record
the max value of stack1
so the GetMax() = max( max1, stack3.top() ) |
|
OK, so this is another solution with amortized O(1).
And making queue by 2 stacks in O(1) worst case overhead would be complicated ...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print