CODEWITHSUNDEEP
algorithmlanguage-agnosticdata-structurescontactsbinary-search-tree
klaks
klaks

Reputation: 31

Algorithm and data structure to store First name and last name

Is there a efficient way to store first name and last name in data structure so that we can lookup using either first or last name? I would consider a binary search tree with first name. It would be efficient to search first name. But wouldnt be efficient when trying to search last name. we can also consider one more BST with last name. Any ideas to implement it efficiently?

What if the question is

String names[] = { "A B","C D"};

A requirement is to be able to extend this directory dynamically at runtime, without persistent storage. The directory can eventually grow to hundreds or thousands of names and must be searchable by first or last name.

Now we can't have hash tables to store. Any ideas?

Upvotes: 2

Views: 2949

Answers (5)

Kshitij Banerjee
Kshitij Banerjee

Reputation: 1748

Why not put both first and last names in a trie?

As a bonus, this way you can even get suggestions on partial names by traversing all leaves after current node (maybe on an asynchronous call)

Upvotes: 2

Samus_
Samus_

Reputation: 2993

if you need to search only by first name or only by last name then yes, two hashmaps are the best (and notice you're not duplicating the data, you're partitioning it) but if you don't mind then put both first and last names in a single hashmap and don't differentiate between the two.

Upvotes: 0

Tim Gee
Tim Gee

Reputation: 1062

Also, see Does Java have a HashMap with reverse lookup?…, which is specific to Java but the discussion on the data structures is relevant to any language.

Note that structures such as Bidirectional Sorted Maps also allow range searches (which dual hash tables don't).

Upvotes: 0

Ken Wayne VanderLinde
Ken Wayne VanderLinde

Reputation: 19339

You're idea is pretty good, but here's another option: how about implementing to hash tables?

The first hash table would use first names as a key, and the associated value would either be the last name or a pointer to a Name object. The second hash table would use last names as keys, with the first names or pointers to Name as the values.

Personally, for choosing the values, I would go for a pointer to a Name object, since this method would be more applicable in case you'd like to store even more information (e.g. data of birth, etc.)

Upvotes: 0

Peter Alexander
Peter Alexander

Reputation: 54270

Two hash tables: one from first name to person, and one from last name to person.

Simple is best.

Upvotes: 7

Related Questions