Author |
Topic: guessing a data structure (Read 6626 times) |
|
transgalactic
Newbie
Posts: 11
|
 |
guessing a data structure
« on: Jan 18th, 2012, 12:01pm » |
 Quote  Modify
|
sugest data structure S which has the following functions
n-is the number of members
search(s,k)-finds k inside s in O(lgn)
INSERT(s,k)-inserts k into data structure s in O(lgn)
MAX(s)-returns the maximal member of s in O(1)
DELETE_MAX(s) -deletes the maximal member from the structure in O(lgn)
DELETE_OLD(s,t) -deletes the t oldests in the order of inserting in O(lgn)
i think its some sort of red black tree
and we need to have in each node the "age" of the node.
what is data stucture S
?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: guessing a data structure
« Reply #1 on: Jan 19th, 2012, 10:12pm » |
Quote Modify
|
You could combine a queue/list with a tree. The queue/list can keep track of the age, the tree of the sort-order.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ashmish2
Newbie
Posts: 12
|
|
Re: guessing a data structure
« Reply #2 on: Jan 28th, 2012, 11:13am » |
Quote Modify
|
I believe every else is take cared of my heap except the DELETE_OLD which can be solved by maintaing a seperate queue
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: guessing a data structure
« Reply #3 on: Sep 14th, 2012, 9:31pm » |
Quote Modify
|
on Jan 19th, 2012, 10:12pm, towr wrote:| You could combine a queue/list with a tree. The queue/list can keep track of the age, the tree of the sort-order. |
|
I think DELETE_OLD(s,t) is going to be tricky. Even with a tree-cum-list/queue kind of DS won't be trivial.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: guessing a data structure
« Reply #4 on: Sep 14th, 2012, 9:32pm » |
Quote Modify
|
on Jan 18th, 2012, 12:01pm, transgalactic wrote:sugest data structure S which has the following functions
...........
DELETE_OLD(s,t) -deletes the t oldests in the order of inserting in O(lgn)
...........
|
|
Shouldn't this depend on 't'? O(t lg n)?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: guessing a data structure
« Reply #5 on: Sep 14th, 2012, 11:46pm » |
Quote Modify
|
on Sep 14th, 2012, 9:31pm, R wrote:
I think DELETE_OLD(s,t) is going to be tricky. Even with a tree-cum-list/queue kind of DS won't be trivial.
|
|
I don't see the problem, you can find the oldest elements easily and delete them one at a time from the tree
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: guessing a data structure
« Reply #6 on: Sep 24th, 2012, 8:26am » |
Quote Modify
|
on Sep 14th, 2012, 11:46pm, towr wrote:
I don't see the problem, you can find the oldest elements easily and delete them one at a time from the tree |
|
Won't that make it a Theta(t log n) operation? While the requirement is O(log n). Say we choose t = n/2.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: guessing a data structure
« Reply #7 on: Sep 24th, 2012, 8:53am » |
Quote Modify
|
The only issue is keeping the tree balanced; deleting the nodes themselves is easy enough to do in O(t) Using a scapegoat-tree might help with that (As I understand it, it does the balancing at insertion using only the height of the inserted tree as guide, but I'm not well-versed in the workings of self-balancing trees, to be quite honest).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print