Amazon Interview Question
SDE1sCountry: United States
That's not a bad thing. there are multiple search strings that will return the result. Use a pointer/reference to keep storage space down. Making each item searchable makes it an O(n) lookup vs an O(log n) lookup.
Contact is composed of other entities or properties. May be Contact has ph number, name etc.
Time to use command DP.
interface Searchable {
public SearchResult search();
}
class PhoneNumber implements Searchable {
// implement the method .....
}
class Contact implements Searchable {
// lots of layering :-)
public SearchResult search() {
return phNumber.search();
}
}
I think search can be applied on multiple attributes, for example, "name", "phone number", "company". Then we define the order we search from these attributes. Display relevant results.
c++ pseudo-code:
typedef struct ContactInfo
{
string name;
string company;
string address;
int phoneNumber[];
}
class ContactManipulate
{
public:
bool AddContact( ContactInfo c1 );
bool DeleteContact( ContactInfo* c1 );
bool UpdateContact( ContactInfo* c1 );
queue<ContactInfor> FindContact( string str );
bool IsContain( string searchString, string attr );
bool IsContain_phoneNum( int searchNum[], int phoneNum[] );
int GetNumOfContact();
ContactInfo* GetContactInfo( int i );
private:
int NumOfContacts;
}
// We can use KMP to match string,
// since we may just want part of attr match searchString
bool ContactManipulate::IsContain( string searchString, string attr )
{ }
queue< ContactInfo > FindContact( string str )
{
queue< ContactInfo > searchResults;
// Search all contacts,
// since we don't want to miss any info that matches search string.
for( int i = 0; i < length; i++ )
{
// If search string are all numbers, we search from phone numbers
if( StrIsNum(str) )
{
int num[] = StrToInt(str);
int phoneNum = GetContactInfo(i).phoneNumber );
if( IsContain_phoneNum( num, phoneNum )
searchResults.push(i);
// Otherwise, we can search from other fields.
else
{
if( IsContain( str, GetContactInfo(i).name )
searchResults.push(i);
else if( IsContain( str, GetContactInfo(i).company )
searchResults.push(i);
else if( IsContain( str, GetContactInfo(i).address )
searchResults.push(i);
}
}
return searchResults;
}
Use trie and attach entire contact node at the end of each string (it can be phone number, name or last name)
- Shankar May 09, 2013