CareerCup

I was comparing this to the problem we face in databases. Search data on various fields.
I decided to model my solution similar to what databases do ( Primary and Secondary Indexes)
We build every phone record and add it to a hash table where the phone record is the value and the number is the key (Our primary index)
For every other searchable index (e.g. name) we build a map with the name as key and the phone number as value. (Secondary index).
Every secondary key can lead us to the phone number, base on which we can then track the complete record.
Pros - fast map based lookup, easy to add new keys/ discard keys and even update appropriate maps.
Cons - higher memory requirements as keys increase

One condition the interviewer mentioned is should not use any predefined datastructures like lists

I think you may have told them about creating a hash table first making the name a key. But, for the later one, I have no idea.

I think one of the way to do it is use a Trie. Store all substrings and numbers in it.

hash table wont work , as memory contraint will be there ...
using trie how can we search with name and with number as well?? I mean using single ntri

We add all the the substrings to the trie. The end of the substring node will point to the actual object.
e.g. John Smith 415-333-3333.

Insert John, Smith and 4153333333 in the trie.
If user searches for John, the last node which stores "n", will point to an object with John Smith's info. Ideally it should point to a link list which has all the contacts with John in it. This link list can be created when we insert records in the trie.

#include "stdafx.h"
#include<iostream>
#include<map>
#include<cstring>

using namespace std;


class name{
char Name[40];
public:
name(){
strcpy(Name ,"");
}
name(char *s){
strcpy(Name,s);
}
char * get_name(){return Name;}
};
class phoneNum{
char phone[15];
public:
phoneNum(){
strcpy(phone ,"");
}
phoneNum(char *p){
strcpy(phone,p);
}
char * get_phone(){return phone;}
};
// Must define less than relative to name objects.
bool operator<(name a, name b)
{
return strcmp(a.get_name(), b.get_name()) < 0;
}

int main()
{
map<name,phoneNum> Dir;
Dir.insert(pair<name, phoneNum>(name("Tom"),phoneNum("91-8036487300")));

Dir.insert(pair<name, phoneNum>(name("Dick"),phoneNum("91-8036487301")));

Dir.insert(pair<name, phoneNum>(name("Harry"),phoneNum("91-8036487302")));

Dir.insert(pair<name, phoneNum>(name("jarry"),phoneNum("91-8036487303")));
// given a name, find number
char str[80];
cout << "Enter name: ";
cin >> str;
map<name, phoneNum>::iterator p;
p = Dir.find(name(str));
if(p != Dir.end())
cout << "Phone number: " << p->second.get_phone();
else
cout << "Name not in directory.\n";

return 0;
}

/* search based on name*/
#include<iostream>
#include<map>
#include<cstring>

using namespace std;


class name{
char Name[40];
public:
name(){
strcpy(Name ,"");
}
name(char *s){
strcpy(Name,s);
}
char * get_name(){return Name;}
};
class phoneNum{
char phone[15];
char address[50];
public:
phoneNum(){
strcpy(phone ,"");
strcpy(address,"");
}
phoneNum(char *p,char *a){
strcpy(phone,p);
strcpy(address,a);

}
char * get_phone(){return phone;}
char * get_address(){return address;}
};


// Must define less than relative to name objects.
bool operator<(name a, name b)
{
return strcmp(a.get_name(), b.get_name()) < 0;
}

int main()
{
map<name,phoneNum> Dir;
Dir.insert(pair<name, phoneNum>(name("Tom"),phoneNum("91-8036487300","hdjfshfkjjsdkl")));

Dir.insert(pair<name, phoneNum>(name("Dick"),phoneNum("91-8036487301","dhsfjkdfjdkf")));

Dir.insert(pair<name, phoneNum>(name("Harry"),phoneNum("91-8036487302","dcshjkshfkjsdk")));

Dir.insert(pair<name, phoneNum>(name("jarry"),phoneNum("91-8036487303","bfdshfjdsjfdj")));
// given a name, find number
char str[80];
cout << "Enter name: ";
cin >> str;
map<name, phoneNum>::iterator p;
p = Dir.find(name(str));
if(p != Dir.end())
cout << "Phone number: " << p->second.get_phone()<<" Address: "<< p->second.get_address();
else
cout << "Name not in directory.\n";

return 0;
}

Can't grep be used in field separated list ?