Author |
Topic: online subset sum (Read 1834 times) |
|
inexorable
Full Member
Posts: 211
|
 |
online subset sum
« on: May 13th, 2011, 1:32pm » |
 Quote  Modify
|
You have to maintain a set of numbers, starting with an empty set.
A stream of numbers come along with an operation request. The request could be
1)Add(n) - add the number n to the set
2)Remove(n) - remove the number n if already present in set.
3)int FindSum(n) - find the sum of all the numbers in the set that are less than n.
what would be the ideal data structure to support the above operations with optimal time and space complexity?
can we prove lower bound for the data structure that supports above operations?
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: online subset sum
« Reply #1 on: May 14th, 2011, 8:35am » |
Quote Modify
|
A binary search tree with the sub-tree total stored at each node would be perfect for that. If you balance the tree it should take O(log n) average time for all operations.
[oops, silly mistake fixed]
|
| « Last Edit: May 18th, 2011, 1:36am by Grimbal » |
IP Logged |
|
|
|
inexorable
Full Member
Posts: 211
|
|
Re: online subset sum
« Reply #2 on: May 14th, 2011, 10:27pm » |
Quote Modify
|
If it was to be implemented without writing 'redblack' trees or 'avltrees' from scratch for a balanced binary search tree.
would it be possible using c++ stl, boost ?
|
|
IP Logged |
|
|
|
spicy
Newbie
Gender: 
Posts: 8
|
|
Re: online subset sum
« Reply #3 on: May 15th, 2011, 5:55am » |
Quote Modify
|
By using hash and array we can do
insert and delete in O(1) and findsum(n) in O(N)
|
|
IP Logged |
|
|
|
mmgc
Newbie
Gender:
Posts: 47
|
|
Re: online subset sum
« Reply #4 on: May 16th, 2011, 3:31am » |
Quote Modify
|
on May 14th, 2011, 8:35am, Grimbal wrote:A binary search tree with the sub-tree total stored at each node would be perfect for that. If you balance the tree it should take O(n log n) average time for all operations.
|
|
How about just maintaining the sum ( of all numbers less than the node ) at each node in BST. time complexity - O(lg n )
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: online subset sum
« Reply #5 on: May 16th, 2011, 8:40am » |
Quote Modify
|
on May 16th, 2011, 3:31am, mmgc wrote:| How about just maintaining the sum ( of all numbers less than the node ) at each node in BST. time complexity - O(lg n ) |
|
Then you'd need to update all nodes if you add a number that is less than all numbers already in the set. So updates wouldn't be O(log n) as they are in Grimbal's case.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: online subset sum
« Reply #6 on: May 17th, 2011, 3:22am » |
Quote Modify
|
on May 14th, 2011, 8:35am, Grimbal wrote:A binary search tree with the sub-tree total stored at each node would be perfect for that. If you balance the tree it should take O(n log n) average time for all operations.
|
|
O(n log n) time will be the avg time for one operation? If i am not wrong, for a balanced bst, insert , remove will take O(log n) time and findSum(n) will have to traverse the tree for nodes less than n, so O(n) time. How O(n log n) is arrived?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: online subset sum
« Reply #7 on: May 18th, 2011, 1:39am » |
Quote Modify
|
Oops, I meant O(log n). My finger sometime type ahead of what I mean.
And I said "on average" because I wasn't sure whether the balancing of the tree can occasionally take more than O(log n), but I guess it shouldn't.
If the sum of a node and all children is stored at each node, you should be able to return the partial sum in O(log n).
|
| « Last Edit: May 18th, 2011, 1:40am by Grimbal » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print