CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: data structrue to store data and calculate average

1. Junior Member
Join Date
Jan 2012
Posts
2

## 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.

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)

2. ## Re: data structrue to store data and calculate average

Well, let me first ask you: what are your thoughts on this topic? What reasoning led you to your (initial) ideas?

3. Junior Member
Join Date
Jan 2012
Posts
2

## Re: data structrue to store data and calculate average

well at first, due to the average complexity, I've tried to use hash table and skip list... that's didn't work... i still think it is possible, its just that i cant make the average function in O(1)

second opinion is that the insert and update complexity makes me think about going for either a tree or a list with binary search... but again, what with the average...

i think they want us to use heap/hash/skip list...

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•