Amazon Interview Question for Interns


Country: India
Interview Type: Written Test




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

struct *node
{
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;
}

}

- pintuguptajuit(PINTU GUPTA) March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how is input given ??

- Anonymous March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

linked list contain...
a->m->a->z->o->n
output
a->a->o->m->z->n
because of vowel and consonent should be preserved....

- pintuguptajuit(PINTU GUPTA) March 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please elaborate the question with an example

- DashDash March 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- Punit Patel March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

@ aimjwizards
Nice refactoring!
Can you also explain the time complexity of this approach?
Thanks

- Anon March 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ aimjwizards
Your code is incorrect.
Try input where all characters are vowel : "aoeiu" (from description of a problem - order of characters should be preserved)

- ZuZu May 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can you elaborate your question with an example?

- ajit March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apply Quicksort,
Value of each element is calculated as,
Vowel -> Index in string
Non Vowel-> Index in string + string length

- readyToGo March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

its time complexity will be O(n) in worst case..

- pintuguptajuit(PINTU GUPTA) March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think modified merge sort can give in O(nlogn)

- Anonymous March 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<cstdio>
#include<iostream>
using namespace std;

- Anonymous March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- jowett.lee April 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Devang April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int lastSeen = -1;
        final list = "aemlijfghohiaizouppauppio".toList()
        for (int i = 0; i < list.size(); i++) {
            if(["a","e","i","o","u"].contains(list[i])){
                def temp = list[i]
                list.remove(i);
                list.add(++lastSeen,temp);
            }
        }

        println list.join("")

- anaon April 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ZuZu May 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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']

- G10 May 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- sp1rs July 03, 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