Amazon Interview Question for SDE1s


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

using trie will lead to duplicate leaf nodes

- PM May 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- rotinom June 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use ternary search tree instead of a trie.

- Baahu June 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
	}
}

- EK MACHCHAR May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- cctsinghua May 05, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More