Amazon Interview Question
InternsCountry: India
Interview Type: Written Test
If you can create another data structure, simply go through the array and push all vowels you see onto a vowel queue and all consonants onto a consonant queue and then overwrite the array by first writing out the vowel and then the consonant queue. This is O(N).
If you can't create another data structure, then go through the array and each time you meet a vowel, push it through till just before the last vowel you've pushed, kind of like a bubble sort. If it's a consonant, just move to the next position. It would look like this:
r>oiutsag
o>riutsag
or>iutsag
oir>utsag
oiur>tsag
oiurt>sag
oiurts>ag
oiuarts>g
oiuartsg>
My guess is this would be O(N^2) worst case for an array like this: bbbbaaaa.
Here is the neat code
#include <iostream>
bool isVowel(char ch){
return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
bool isConsonant(char ch){
return (!isVowel(ch));
}
int main(){
char str[] = "aemlijfghohiaizouppauppio";
//str[1] = '+';
char *fastPtr = str;
char *slowPtr = str;
while(*fastPtr){
if(isConsonant(*slowPtr) && isConsonant(*fastPtr))
fastPtr++;
else{
if(isConsonant(*slowPtr) && isVowel(*fastPtr)){
char temp = *fastPtr;
char *p = fastPtr;
while(p != slowPtr){
*p = *(p-1);
--p;
}
*slowPtr = temp;
}
++slowPtr;
++fastPtr;
}
}
std::cout << str << std::endl;
}
I think some of your code is redundant.
while(*fastPtr){
if(isConsonant(*fastPtr))
fastPtr++;
else{
if(isVowel(*fastPtr)){
char temp = *fastPtr;
char *p = fastPtr;
while(p != slowPtr){
*p = *(p-1);
--p;
}
*slowPtr = temp;
}
++slowPtr;
++fastPtr;
}
}
@ aimjwizards
Nice refactoring!
Can you also explain the time complexity of this approach?
Thanks
public ListNode shift(ListNode head) {
ListNode newHead = null;
ListNode newTail = null;
ListNode headNode = new ListNode('#');
headNode.next = head;
ListNode cur = headNode;
while (cur != null) {
if (cur.next != null && (cur.next.val == 'a' || cur.next.val == 'e'
|| cur.next.val == 'i' || cur.next.val == 'o' || cur.next.val == 'u')) {
if (newHead == null) {
newHead = cur.next;
newTail = cur.next;
} else {
newTail.next = cur.next;
newTail = newTail.next;
}
cur.next = cur.next.next;
newTail.next = null;
} else {
cur = cur.next;
}
}
newTail.next = headNode.next;
return newHead;
}
#include<iostream.h>
#include<conio.h>
struct node
{
char data;
node *next;
}*head;
char dq[100], vq[100], cq[100];
int dfront=0, vfront=0, cfront=0;
int drear=0, vrear=0, crear=0;
node *getnode()
{
node *temp;
temp=new node;
temp->next=NULL;
return temp;
}
void display(node *temp)
{
while(temp!=NULL)
{
if(temp->data>=48&&temp->data<=56)
cout<<temp->data<<" ";
if(temp->data>=97&&temp->data<=122)
cout<<char(temp->data)<<" ";
temp=temp->next;
}
}
void shift(node *temp)
{
while(temp!=NULL)
{
if(temp->data>=48&&temp->data<=56)
dq[drear++]=temp->data;
else if(temp->data=='a'||temp->data=='e'||temp->data=='i'||temp->data=='o'||temp->data=='u')
vq[vrear++]=temp->data;
else
cq[crear++]=temp->data;
temp=temp->next;
}
temp=head;
while(dfront!=drear)
{
temp->data=dq[dfront++];
temp=temp->next;
}
while(vfront!=vrear)
{
temp->data=vq[vfront++];
temp=temp->next;
}
while(cfront!=crear)
{
temp->data=cq[cfront++];
temp=temp->next;
}
}
void create()
{
node *temp, *newnode;
int flag=1;
char ans, val;
do
{
cout<<"enter data: ";
cin>>val;
newnode=getnode();
newnode->data=val;
if(flag==1)
{
temp=newnode;
head=temp;
flag=0;
}
else
{
temp->next=newnode;
temp=newnode;
}
cout<<"enter more ? ";
cin>>ans;
}while(ans=='y');
cout<<"present list:"<<endl;
display(head);
cout<<endl<<"after shifting:"<<endl;
shift(head);
display(head);
}
main()
{
clrscr();
create();
getch();
}
public class Node
{
public char Value { get; set; }
public Node Next { get; set; }
}
public static Node Shift(Node head)
{
Func<char, bool> isVowel = c => c == 'a' || c == 'o' || c == 'e' || c == 'u' || c == 'i' || c == 'y';
Func<char, bool> isConsonant = c => c >= 'a' && c <= 'z' && !isVowel(c);
Node vowelHead = null;
Node vowelTail = null;
Node consonantHead = null;
Node consonantTail = null;
while (head != null)
{
if (isVowel(head.Value))
{
Add(ref vowelHead, ref vowelTail, head.Value);
}
else if (isConsonant(head.Value))
{
Add(ref consonantHead, ref consonantTail, head.Value);
}
else
{
// value is not in a range 'a'..'z'
// throw exception or handle this case in another way
}
head = head.Next;
}
if (vowelTail != null)
{
vowelTail.Next = consonantHead;
return vowelHead;
}
else
{
return consonantHead;
}
}
private static void Add(ref Node head, ref Node tail, char val)
{
Node n = new Node { Value = val };
if (tail != null) tail.Next = n;
if (head == null) head = n;
tail = n;
}
Here is the python code with explanation.
Step-1: go through the list and get lastVowel pointer
Step-2: go through the list again. If cur node is consonant then remove it and insert it next to lastVowel.
If it's vowel then simply advance the cur pointer
def arrangeList(head):
lastVowel = getLastVowel(head) # get pointer to last Vowel in the list
if lastVowel == head or lastVowel == None: # Stop if lastVowel = head or there is no vowel
return
cur = head
prev = None
while cur != lastVowel:
if not isVowel(cur.data): # If cur node is consonant then remove it and insert it next to last vowel
n = cur # save cur so we can insert it next to last vowel
# Removing cur node
if prev == None: # if cur node is the first node
head = head.next
else: # if cur is any intermediate node
prev.next = cur.next
cur = cur.next # cur was still pointing to removed node so advance cur to next node
# inserting n next to last vowel
n.next = lastVowel.next
lastVowel.next = n
else: # just move forward if cur is consonant
prev = cur
cu = cur.next
def getLastVowel(head):
lastVowel = None
cur = head
while cur != None:
if isVowel(cur.data):
lastVowel = cur
cur = cur.next
return lastVowel
def isVowel(data):
return data in ['a','e','i','o','u']
Use Sorting to solve this problem
import java.util.Scanner;
import java.util.*;
public class vo{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
String s=sc.next();
int l[]=new int[s.length()];
int count=0;
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(c=='a' || c=='e' || c=='i' || c=='o' || c=='u'){
l[i]=i;
count++;
}else{
l[i]=i+s.length();
}
}
Arrays.sort(l);
for(int j=0;j<count;j++){
System.out.print(s.charAt(l[j]));
}
for(int j=count;j<s.length();j++){
System.out.print(s.charAt(l[j]-s.length()));
}
System.out.println();
}
}
struct *node
- pintuguptajuit(PINTU GUPTA) March 23, 2013{
char val;
node *next;
};
node *GetVowelFirst(node *head)
{
if(!head)
return head;
else
{
node *list1,*list11;
node *list2,*list22;
list1=list11=list22=list2=NULL;
char c;
node *dhead=head;
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(!list1)
{
list1=list11=head;
head=head->next;
list11->next=NULL;
}
else
{
list11->next=head;
head=head->next;
list11=list11->next;
list11->next=NULL;
}
}
else
{
if(!list2)
{
list2=list22=head;
head=head->next;
list22->next=NULL;
}
else
{
list22->next=head;
head=head->next;
list22=list22->next;
list22->next=NULL;
}
}
}
list11->next=list2;
head=list1;
return head;
}
}