I know this was solved 13 years ago, but I would like to reemphasize what gbulmer said:

If this is an interview question (and not on a closed-book test,) you should be asking questions. The interview actually has 3 goals:

• to see if you know the tech (the most obvious test, if you can't perform the task, you fail)

• to see if you need excessive hand-holding (if you ask dozens of questions you will fail this one,)

• to see if you will verify unspoken assumptions (if you ask 0 questions, you will fail this one instead)

The task looks neat and tidy, but it is actually ridiculously broad. Here are the questions you need to ask, before starting on your task:

1. What does "safe" mean?

   1. Should the data structure be type-safe? (and how do I handle garbage data?)

   2. Should it be thread-safe? (or can I assume only one process will ever use it?)

   3. Are there any additional "safety features" you need? (security, error correction, backups. They should say "no", but it doesn't hurt to ask.)

2. What does "efficient" mean?

   1. Should you prioritize time or space?

   2. Should you prioritize saving numbers or retrieving numbers?

3. What does "a phone book" mean?

   1. Can numbers be longer than 8 digits (18 on a 64 bit system?)

   2. Can numbers have additional and symbols in them (-,+,#, and space are likely) and if so, should these numbers be reproduced as written, stripped down to a sequence of digits, or reconstituted into a specific format?

   3. Can people's names consist entirely of numbers (and whatever additional symbols we designated in question 3.2?)

   4. Are there future plans to expand the phone book with additional fields (addresses for example) or can you assume that a name-to-number correspondence is all that will ever be needed?

   5. Can contacts be modified?

      1. A name assigned a new number?

      2. A number assigned a new name?

      3. The whole contact be deleted?

Having claridifed the task, you can proceed. Assuming the answers are: type-safe, but not thread-safe and the structure should return blank name or 0 when the input is incorrect, but never throw exceptions. Prioritize time and retrieval. Numbers can be as long as the user wants, but all numbers with the same digits are considered equal, names will include at least one letter and contacts will be deleted when they become obsolete, but no further modification will occur. A possible solution can do the following:

The data structure will expose 5 methods:

• boolean AddContact(string name, string number)

• string FindNumber(string name)

• string FindName(string number)

• boolean DeleteByName(string name)

• boolean DeleteByNumber(string number)

Internally it will consist of a HashMap (we are guaranteed no collisions between numbers and names, so one is enough) and a few helper methods.

Sample implementation here: https://dotnetfiddle.net/JWEUPi