CareerCup

Do you mean the efficient presentation of all available addresses to be used for look up of the specific given address?

I believe the answer would be Trie of cities, where each city will hold Trie of streets, where each street will hold array of size equals to number of houses - providing thus 0(1) look up table.

Can elaborate the scope of the system we are trying to design? Is the interviewer looking abstract DS or a OOD?

Tree

To me, best would be to use maps thus reduce coding to find out the destination address. It would be sometinh like...
PostalSystem <Map (<pincode>,<Map(<address>,<message>)>)>

This is basic you can expand including separate cover map for state country etc

Queues

If you want to use just one, I would recommend a vector (like in C++). You can simulate pretty much most of the data-structures using that.

Silly question though.