CareerCup

For fast retrieval and search of zip codes, I will go wid Trie Tree

I would use array.

How about hash table ?

What are the requirements?
Secondary storage (like disk) needed? What is the read/write/query scenario.. etc.

In my opinion: when it is asked about "data structures", they mean to store stuff in main memory. So a Trie would certainly be the best in this case, where the tree height will be no more than the length of the data (zipcode or SSN). The height will be even shorter if we take multi-stride tries.

http://en.wikipedia.org/wiki/Trie

Arrays will take O(n) comparisons to retrieve data, and hashtables waste storage space.

Just because it's an interview question does not mean we need to INVENT some COOL answer. I love it when interviewers use such questions to spot people who have memorized stuff.

These codes are derived from multiple inputs like state+area
one state we have multiple areas

In this case, we have Hash of Hash. Each row signify State.

Trie it is!

Set associative mapping method is better, in this case.

you have to ask yourself what the data will be used for. SSN and area code are will probably be assigned to a person with a potential personID. Given a personID you should be able to quickly retrieve his/her data. Hash table would be ideal. arrays would work if the index of the element is also the ID passed in.

A Trie can be used here as SSNs and ZIP codes share a huge number of prefixes, thereby maximizing space utilization.

Before going into technical details I would ask if we have clearance from the Legal Department to store SSNs ;)

@Cristi:
I think we don't have the requisite clearance for storing the SSNs, so that's the "Smart Answer" the interviewer is expecting.
Answer it and get hired!

TRIE