CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    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.

    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

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    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?
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

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

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
  •  





Click Here to Expand Forum to Full Width

Featured