Amazon Interview Question
InternsCountry: India
Interview Type: Written Test
#include<iostream>
using namespace std;
#include<stdlib.h>
#include<conio.h>
#include<string.h>
struct node
{
char data;
node *next;
};
node *GetVowelFirstNumber(node *head)
{
if(!head)
return head;
else
{
node *list1,*list11;
node *list2,*list22;
node *list3,*list33;
list1=list11=list22=list2=list33=list3=NULL;
char c;
char ca[256];
for(int i=0;i<256;i++)
ca[i]=0;
while(head)
{
c=head->data;
if(c=='a'||c=='A'||c=='e'||c=='E'||c=='i'||c=='I'||c=='u'||c=='U'||c=='o'||c=='O')
{
if(ca[c]==0)
{
// cout<<"\n vowel";
ca[c]++;
if(!list1)
{
list1=list11=head;
head=head->next;
list11->next=NULL;
}
else
{
list11->next=head;
head=head->next;
list11=list11->next;
list11->next=NULL;
}
}
else
{
head=head->next;
}
}
else
{
if((c)>=48&&(c)<=57)
{
// cout<<"\n NUmber\n";
if(ca[c]==0)
{
ca[c]++;
if(!list3)
{
list3=list33=head;
head=head->next;
list33->next=NULL;
}
else
{
list33->next=head;
head=head->next;
list33=list33->next;
list33->next=NULL;
}
}
else
{
head=head->next;
}
}
else
{
if(ca[c]==0)
{
cout<<"\n consonant";
ca[c]++;
if(list2==NULL)
{ cout<<"list2\n";
list2=list22=head;
head=head->next;
list22->next=NULL;
}
else
{
cout<<"list2\n";
list22->next=head;
head=head->next;
list22=list22->next;
list22->next=NULL;
}
}
else
{
head=head->next;
}
}
}
}
// list3 number
// list2 cons
// list1 vowel
if(list1)
{
if(list2)
{
if(list3)
{
list33->next=list2;
list22->next=list1;
head=list3;
}
else
{
list22->next=list1;
head=list2;
//cout<<"\n"<<head->data<<"\n";
//return head;
}
}
else
{
if(list3)
{
list33->next=list1;
head=list3;
}
else
{
head=list1;
}
}
}
else
{
if(list2)
{
if(list3)
{
list33->next=list2;
head=list3;
}
else
{
head=list2;
}
}
else
{
head=list2;
}
}
return head;
}
}
int main()
{
char *a=new char[100];
cin>>a;
node *n=NULL;
for(int i=0;a[i]!='\0';i++)
{
inseart(&n,a[i]);
}
n=GetVowelFirstNumber(n);
display(n);
getch();
return 0;
}
My understand is :
1> Build a simple hash from an array, mapping '0'-'9', 'a'-'z', 'A'-'Z', to it. making sure 'a-z' point to same node as 'A-Z'.
2> Go through the list, count each keys accordingly. then list them according to the order of digital, consonant, vowel. You can also reuse the old list if you want.
I think solution is straight forward, since there is no limit on space complexity, the above solution could be achieved by creating three pointers of structure type.
- Anonymous March 25, 20131. numbers pointer will point to all numbers
2. consonant pointer will point to list of consonants
3. vowel pointer will point to all vowels in the list.
parse through the list one node at a time and add the nodes to either of list of numbers, vowel and consonant, add elements in the ascending orders this will help in not adding duplicate in the list. once the list is parsed completely then use three lists; go to the end of numbers list and point the lat node pointing to the end to point to the head of consonant list and then traverse till end and make last node of consonant list point to head of vowels list.
at the end change the head node to point to the new list.