-
January 25th, 2012, 02:06 AM
#1
data structrue to store data and calculate average
In this problem, we are interested in a data structure that supports keeping infinite numbers of Y axis parallel vectors.
Each node contains location (X axis value) and height (Y axis value). We can assume there are no two vectors in the same location.
Please advise for an efficient data structure that supports:
1. init((x1,y1)(x2,y2)(x3,y3)...(xn,yn)) - the DS will contain all n vectors, while VECTOR#i's location is xi VECTOR#i's hieght is yi.
We also know that x1<x2<x3<...<xn (nothing is known about the y) - complexity = O(n) on average
2. insert(x,y) - add vector with location x and hieght y. - complexity = O(logn) amortized on average.
3. update(x,y) - update vector#x's height to y. - complexity = O(logn) worst case
4. average_around(x) - return the heights average of logn neighbors of x - complexity = O(1) on average
Space Complexity: O(n)
so, after the long question... please advise
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|