R – implement a telephone address book – reverse index

data structureslanguage-agnostic

Now I am trying to come up with a data structure for implementing a telephone adreess book.
Say there are two infos : name, telephone numbers. The same name can have more than one number.
Now i would like to come up with a data structure that will help me in fetching the number given a name and fetching the name, given a number. I have to do this in the least possible time.
I was thinking of maintaining a map (name to number) and then for a given number somehow reverse index into this map and then find the name.
I am not really sure whats the best way to do this.
Can you suggest an ideal data structure. Will using some reverse index help. If yes then how do i use it in this context.

Best Answer

I would maintain two (hash) maps.

The first map would have Names as the keys, and Sets (or lists or vectors) as the values, this list would contain all of the phone numbers for a specific person.

Map<String,Set<String>> NamesToNumbers;

The second map would have Phone Numbers as the keys, and Names as the values.

Map<String,String> NumbersToNames;

Additionally I would create a simple class with these two maps as private members, the purpose of this class would be to keep the two maps in sync, and pass all put(), remove(), etc. calls to both maps in the correct Key/Value format.

Psuedo code for how id write a put() method in the simple class:

public void put(String Name,String PhoneNumber)
{

Set NumbersForName = NamesToNumbers.get(Name);
if (NumbersForName == null)
  {
    NumbersForName = new Set();
    NamesToNumbers.put(Name,NumbersForName);
  }

NumbersForName.put(PhoneNumber);
NumbersToNames.put(PhoneNumber,Name);  

}

The cost of a look up will be O(1), and the cost of an insertion will be O(1) unless there is a hash collision.

If you are using Java 5+ you should check out Google Collections, they have a nifty Bi-map class which is essentially what I am trying to describe.

Related Solutions

How to implement a queue using two stacks

Keep 2 stacks, let's call them inbox and outbox.

Enqueue:

Push the new element onto inbox

Dequeue:

If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
Pop and return the top element from outbox

Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.

Here's an implementation in Java:

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}

C# – Select Multiple Fields from List in Linq

Anonymous types allow you to select arbitrary fields into data structures that are strongly typed later on in your code:

var cats = listObject
    .Select(i => new { i.category_id, i.category_name })
    .Distinct()
    .OrderByDescending(i => i.category_name)
    .ToArray();

Since you (apparently) need to store it for later use, you could use the GroupBy operator:

Data[] cats = listObject
    .GroupBy(i => new { i.category_id, i.category_name })
    .OrderByDescending(g => g.Key.category_name)
    .Select(g => g.First())
    .ToArray();

Best Answer

Related Solutions

How to implement a queue using two stacks

C# – Select Multiple Fields from List in Linq

Related Topic