algorithm - Best data structure for a given set of operations - Add, Retrieve Min/Max and Retrieve a specific object -

-

i looking optimal (time , space) optimal data structure supporting following operations:

  1. add persons (name, age) global data store of persons
  2. fetch person minimum , maximum age
  3. search person's age given name

here's think of:

  • keep array of persons, , keep adding end of array when new person added
  • keep hash of person name vs. age, assist in fetching person's age given name
  • maintain 2 objects minperson , maxperson person min , max age. update if needed, when new person added.

now, although keep hash better performance of (3), think may not best way if there many collisions in hash. also, addition of person mean overhead of adding hash.

is there can further optimized here?

note: looking best (balanced) approach support these operations in minimum time , space.

it looks need data structure needs fast inserts , supports fast queries on 2 different keys (name , age).

i suggest keeping 2 data structures, 1 sorted data structure (e.g. balanced binary search tree) key age , value pointer person object, other hashtable key name , value pointer person object. notice don't keep 2 copies of same object.

a balanced binary search tree provide o(log(n)) inserts , max/min queries, while hastable give o(1) (amortized) inserts , lookups.

when add new person, add pointer both data structures. min/max age query, can retrieve object querying bst. name query can query hashtable.

your question not ask updates/deletes, doable suitably updating both data structures.


Comments

Post a Comment

Popular posts from this blog

objective c - Change font of selected text in UITextView -

-
can suggest me how change font of selected text in uitextview.i cannot use uiwebview since have edit text. have seen pages app.how possible in app. see formatting text within uilabel differently . since need editing, should @ javascript-based editors such ckeditor or tinymce . highly recommend wwdc 2011 video session 511: "rich text editing in safari on ios."
Read more

php - Accessing POST data in Facebook cavas app -

-
so i've got simple form in canvas / iframe facebook app, , i'm trying pass along values post. reading on s.o. , fb's latest docs, understand it, data send via post form can accessed on receiving end $_request object. i read on thread on s.o. in order post forms work need pass along input named "signed_request" value current signed_request (i have signed request working ok otherwise...all login , authentication stuff working fine). isnt mentioned anywhere in official fb docs. so problem comes in $_request object signed request, , bunch of other session stuff. form inputs found. the way can read them set method of form "request" isn't real form method. takes of inputs , sends them args in url. horrible. here's sample page canvas app form i'm using try debug (leaving out authentication stuff): <form enctype="application/x-www-form-urlencoded" method="post" target="_top" id="my_form" action=...
Read more

c# - Getting control value when switching a view as part of a multiview -

-
i have following code in aspx page: <asp:button id="display_button" runat="server" text="display" onclick="button1_click" /> &nbsp; <asp:button id="edit_button" runat="server" text="edit" onclick="button2_click" /> &nbsp; <asp:button id="save_button" runat="server" text="save" onclick="button3_click" visible="false" /> &nbsp; <asp:multiview id="multiview1" runat="server" activeviewindex="0"> <asp:view id="view1" runat="server"> <asp:formview id="view_program" runat="server"> <itemtemplate> <%# eval("status").tostring().trim() %> </itemtemplate> </asp:formview> </asp:view> <asp:view id="view2" runat="server"> ...
Read more