CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Amazon Interview Question for Software Engineer / Developers


Team: AWS
Country: United States
Interview Type: Phone Interview
More Questions from This Interview



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

Do you really think (or the interviewer?) that a hash-table is the best for implementing a phonebook? I am quite puzzled after working with phonebook for about 12+ years...
The most used operation on phonebook is displaying the content fast and retrieving the contacts in some order (that varies) and with filtering for different conditions (like search for the first/few characters or pronounciation).
I doubt that a hash-table will help solving these fast.
Changing the content happens so rarely compared to retrieval that it does not really matter how fast/slow it is.
Of course this is just one point of view.

- Selmeczy, Péter December 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can a multiway search tree solve the purpose? i.e having a branch for each alphabet.

- raghu December 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Selmeczy, Péter I completely agree with you....A phonebook has to show the contacts generally in alphabetical order and it has to support searching with first few characters also. So, a trie tree or even a BST is a much better choice over a hash table.

- Vip December 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Trie works best

- Anonymous January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about Trie. can we use Trie for phonebook?

- time December 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i agree, Phonebook is never too large to have memory issues even if its implemented using a Trie.

- eatesh December 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Map and complexity O(logn)

- raghaa December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I will use a normal list to save the full record and use a prefix tree with record pointer in leaves to handle the retrieving operation and prediction and use a linked list of record pointers sorted in alphabetical order to handle the display. The pointer of each element of the sorted list(pointers to the full records) is also saved in prefix tree leaves.
When adding a new contact, first insert to normal list, then insert to prefix tree and finding its predecessor and its position in the sorted list and finally insert it in sorted list.

- yangqch December 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yenna rascala mind it!!

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

struct node 
{
       char *name; //only considered 1 name here. if both 1st name and last name, maintain two BSTs - one ordered by fname, one by lname
       char *address;
       unsigned long long phone_number;
       node *left,*right;
       int ht; //for maintaining height balance property
};

class phone_book
{
      node *root;
      node *add1(node *T, char *name,char *add,unsigned long long pno);
      int height(node*);
      int BF(node*);
      node *LL(node*);
      node *LR(node*);
      node *RL(node*);
      node *RR(node*);
      node *rotateright(node*);
      node *rotateleft(node*);
      void inorder1(node*);
      void find1(node*,char*);
      
      public:
      phone_book() {root=NULL; }
      void add(char *name,char *add,unsigned long long pno) {root=add1(root,name,add,pno); } 
      void inorder() { cout<<"\nInorder Traversal:\n "; inorder1(root); }
      void find(char* name) {find1(root,name);}
};

void phone_book::inorder1(node *T)
{
     if(T!=NULL)
     {
         inorder1(T->left);
         cout<<T->name<<", "<<T->phone_number<<"\n";
         inorder1(T->right);
     }
}

node* phone_book::rotateright(node*T)
{
      node *X=T->left;
      T->left=X->right;
      X->right=T;
      T->ht=height(T);
      X->ht=height(X);
      return(X);
}

node* phone_book::rotateleft(node*T)
{
      node *X=T->right;
      T->right=X->left;
      X->left=T;
      T->ht=height(T);
      X->ht=height(X);
      return(X);
}

node* phone_book::LL(node*T)
{
     T=rotateright(T);
     return(T);
}

node* phone_book::RR(node*T)
{
     T=rotateleft(T);
     return(T);
}

node* phone_book::RL(node*T)
{
     T->right=rotateright(T->right);
     T=rotateleft(T);
     return(T);
}

node* phone_book::LR(node*T)
{
      T->left=rotateleft(T->left);
      T=rotateright(T);
      return(T);
}

int phone_book::height(node *T)
{
     int lh,rh;
     if(T==NULL)
       return(0);
     if(T->left==NULL)
       lh=0;
     else
       lh=1+T->left->ht;
     if(T->right==NULL)
       rh=0;
     else
       rh=1+T->right->ht;
     if(lh>rh)
       return(lh);
     return(rh);
}

int phone_book::BF(node *T)
{
    int lh,rh;
    if(T==NULL)
      return(0);
    if(T->left==NULL)
       lh=0;
     else
       lh=1+T->left->ht;
     if(T->right==NULL)
       rh=0;
     else
       rh=1+T->right->ht;
     return(lh-rh);
}

node* phone_book::add1(node *T,char *name,char *add,unsigned long long pno) 
{
     if(T==NULL)
     {
        T=new node();
        T->name=new char[strlen(name)+1];
        strcpy(T->name,name);
        T->address=new char[strlen(add)+1];
        strcpy(T->address,add);
        T->phone_number=pno;
        T->left=NULL; T->right=NULL;
     }
     else if((strcmp(name,T->name))>0)
     {
        T->right=add1(T->right,name,add,pno);
        if(BF(T)==-2) {
           if((strcmp(name,T->right->name))>0)
              T=RR(T);
           else
              T=RL(T);
           }
     }
     else if((strcmp(name,T->name))<0) 
     {
          T->left=add1(T->left,name,add,pno);
          if(BF(T)==2) {
             if((strcmp(name,T->left->name))<0)
                T=LL(T);
             else
                T=LR(T);
             }
     }
     else
     {
         T->address=add;
         T->phone_number=pno;
     }
     T->ht=height(T);
     return(T);
}

void phone_book::find1(node *T,char *name)
{
     while(T!=NULL)
     {
       if((strcmp(T->name,name))==0) {cout<<"\nFound!"<<" "<<T->name<<" "<<T->address<<" "<<T->phone_number; return;}
       else if((strcmp(T->name,name))>0) {T=T->left;}
       else if((strcmp(T->name,name))<0) {T=T->right;}
     }
     cout<<"\nNo such entry!! "<<name;
}
       
int main() //O(lgn) time for inserting, deleting and retrieving. memory for new number created on the fly.
{
    phone_book pb1;
    //Add 100 random names and numbers to the phone book - tested upto 1000 numbers!
    for(int i=0;i<100;i++)
    {
       int j;
      //Phone number
      int pno=rand();
      int len=(rand()%10)+2;
      //Name
      char *name;
      name=new char[len];
      for(j=0;j<len;j++)
       name[j]=(char)(97+(rand()%26));
      name[j]='\0';
      //Address
      len=(rand()%10)+2;
      char *add;
      add=new char[len];
      for(j=0;j<len;j++)
       add[j]=(char)(97+(rand()%26));
      add[j]='\0';
      //Add to phone book 
      pb1.add(name,add,pno);
      delete[] add;
      delete[] name;
    }
    pb1.add("ajinkya Kher","Pune",750083);
    pb1.add("neha","Pune",862464);
    pb1.add("sachin Tendulkar","Mumbai Indians",7171);
    
    //These are the phone numbers sorted as per the name
    pb1.inorder();
    
    //Search by name
    pb1.find("ajinkya Kher");
    pb1.find("Ronaldo");
    pb1.find("neha");
    pb1.find("sachin Tendulkar");
    pb1.find("asar");
    
    //Delete function easy to add, not added though! you try...
    getch();
    return 0;
}

- Rajnikanth March 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yenna rascala mind it!!

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

struct node 
{
       char *name; //only considered 1 name here. if both 1st name and last name, maintain two BSTs - one ordered by fname, one by lname
       char *address;
       unsigned long long phone_number;
       node *left,*right;
       int ht; //for maintaining height balance property
};

class phone_book
{
      node *root;
      node *add1(node *T, char *name,char *add,unsigned long long pno);
      int height(node*);
      int BF(node*);
      node *LL(node*);
      node *LR(node*);
      node *RL(node*);
      node *RR(node*);
      node *rotateright(node*);
      node *rotateleft(node*);
      void inorder1(node*);
      void find1(node*,char*);
      
      public:
      phone_book() {root=NULL; }
      void add(char *name,char *add,unsigned long long pno) {root=add1(root,name,add,pno); } 
      void inorder() { cout<<"\nInorder Traversal:\n "; inorder1(root); }
      void find(char* name) {find1(root,name);}
};

void phone_book::inorder1(node *T)
{
     if(T!=NULL)
     {
         inorder1(T->left);
         cout<<T->name<<", "<<T->phone_number<<"\n";
         inorder1(T->right);
     }
}

node* phone_book::rotateright(node*T)
{
      node *X=T->left;
      T->left=X->right;
      X->right=T;
      T->ht=height(T);
      X->ht=height(X);
      return(X);
}

node* phone_book::rotateleft(node*T)
{
      node *X=T->right;
      T->right=X->left;
      X->left=T;
      T->ht=height(T);
      X->ht=height(X);
      return(X);
}

node* phone_book::LL(node*T)
{
     T=rotateright(T);
     return(T);
}

node* phone_book::RR(node*T)
{
     T=rotateleft(T);
     return(T);
}

node* phone_book::RL(node*T)
{
     T->right=rotateright(T->right);
     T=rotateleft(T);
     return(T);
}

node* phone_book::LR(node*T)
{
      T->left=rotateleft(T->left);
      T=rotateright(T);
      return(T);
}

int phone_book::height(node *T)
{
     int lh,rh;
     if(T==NULL)
       return(0);
     if(T->left==NULL)
       lh=0;
     else
       lh=1+T->left->ht;
     if(T->right==NULL)
       rh=0;
     else
       rh=1+T->right->ht;
     if(lh>rh)
       return(lh);
     return(rh);
}

int phone_book::BF(node *T)
{
    int lh,rh;
    if(T==NULL)
      return(0);
    if(T->left==NULL)
       lh=0;
     else
       lh=1+T->left->ht;
     if(T->right==NULL)
       rh=0;
     else
       rh=1+T->right->ht;
     return(lh-rh);
}

node* phone_book::add1(node *T,char *name,char *add,unsigned long long pno) 
{
     if(T==NULL)
     {
        T=new node();
        T->name=new char[strlen(name)+1];
        strcpy(T->name,name);
        T->address=new char[strlen(add)+1];
        strcpy(T->address,add);
        T->phone_number=pno;
        T->left=NULL; T->right=NULL;
     }
     else if((strcmp(name,T->name))>0)
     {
        T->right=add1(T->right,name,add,pno);
        if(BF(T)==-2) {
           if((strcmp(name,T->right->name))>0)
              T=RR(T);
           else
              T=RL(T);
           }
     }
     else if((strcmp(name,T->name))<0) 
     {
          T->left=add1(T->left,name,add,pno);
          if(BF(T)==2) {
             if((strcmp(name,T->left->name))<0)
                T=LL(T);
             else
                T=LR(T);
             }
     }
     else
     {
         T->address=add;
         T->phone_number=pno;
     }
     T->ht=height(T);
     return(T);
}

void phone_book::find1(node *T,char *name)
{
     while(T!=NULL)
     {
       if((strcmp(T->name,name))==0) {cout<<"\nFound!"<<" "<<T->name<<" "<<T->address<<" "<<T->phone_number; return;}
       else if((strcmp(T->name,name))>0) {T=T->left;}
       else if((strcmp(T->name,name))<0) {T=T->right;}
     }
     cout<<"\nNo such entry!! "<<name;
}
       
int main() //O(lgn) time for inserting, deleting and retrieving. memory for new number created on the fly.
{
    phone_book pb1;
    //Add 100 random names and numbers to the phone book - tested upto 1000 numbers!
    for(int i=0;i<100;i++)
    {
       int j;
      //Phone number
      int pno=rand();
      int len=(rand()%10)+2;
      //Name
      char *name;
      name=new char[len];
      for(j=0;j<len;j++)
       name[j]=(char)(97+(rand()%26));
      name[j]='\0';
      //Address
      len=(rand()%10)+2;
      char *add;
      add=new char[len];
      for(j=0;j<len;j++)
       add[j]=(char)(97+(rand()%26));
      add[j]='\0';
      //Add to phone book 
      pb1.add(name,add,pno);
      delete[] add;
      delete[] name;
    }
    pb1.add("ajinkya Kher","Pune",750083);
    pb1.add("neha","Pune",862464);
    pb1.add("sachin Tendulkar","Mumbai Indians",7171);
    
    //These are the phone numbers sorted as per the name
    pb1.inorder();
    
    //Search by name
    pb1.find("ajinkya Kher");
    pb1.find("Ronaldo");
    pb1.find("neha");
    pb1.find("sachin Tendulkar");
    pb1.find("asar");
    
    //Delete function easy to add, not added though! you try...
    getch();
    return 0;
}

- Rajnikanth March 04, 2012 | 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