2

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?

klaks
  • 31
  • 1
  • 6
  • 1
    the problem seems somewhat vague, do you want to, given a single string, search for either a last or first name that matches, do you want to search by last name and last name separatly, or do you want to search for a first/last name combination? For the first two cases, I'd go with separate BSTs, you could go with BSTs nested in BSTs for the last case – pasha Dec 21 '11 at 21:05
  • You can imagine as a addressbook scenario. we are given a list of names like emp.setName("A","J"), emp.setName("B","C"),... I need to get the emp details either when searched by first name or last name – klaks Dec 21 '11 at 21:31
  • Does this work in the above scenario too? – klaks Dec 22 '11 at 00:31

5 Answers5

7

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

Simple is best.

Peter Alexander
  • 53,344
  • 14
  • 119
  • 168
  • Yeah this solution is simple but do you think its efficient. I need two hashmaps for the same data? – klaks Dec 21 '11 at 21:33
  • 2
    Well it's fast: average O(1) for either lookup. Insertion and removal is average O(1), too and space is O(n). You're not storing the same data twice, you're storing lookup tables. I don't think you'll get asymptotically better than this. I don't know how many contacts you'll have, but I can't see this being a memory bottleneck. – Peter Alexander Dec 21 '11 at 21:39
2

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)

Kshitij Banerjee
  • 1,678
  • 1
  • 19
  • 35
0

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

Ken Wayne VanderLinde
  • 18,915
  • 3
  • 47
  • 72
0

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

Community
  • 1
  • 1
Tim Gee
  • 1,062
  • 7
  • 9
0

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.

Samus_
  • 2,903
  • 1
  • 23
  • 22