Amazon Interview | Set 3

Feed: GeeksforGeeks
Posted on: Monday, August 27, 2012 12:57 AM
Author: GeeksforGeeks
Subject: Amazon Interview | Set 3

Please find the details of my Amazon interviews below. Date of Interviews: 26th July 2012 No of Rounds: 1 online exam + 4 PI Type of Interviews: Campus Interview for freshers Online test(Time): 90 Minutes 20 Objective Questions: Aptitude and basic C objective problems. 2 Subjective Questions: I. Given a linked […]

The post Amazon Interview | Set 3 appeared first on GeeksforGeeks.

W9GBo2_4Z6k

View article…

GeeksforGeeks

A computer science portal for geeks

Subscribe

Amazon Interview | Set 3

August 27, 2012

Please find the details of my Amazon interviews below.

Date of Interviews: 26th July 2012

No of Rounds: 1 online exam + 4 PI

Type of Interviews: Campus Interview for freshers

Online test(Time): 90 Minutes

20 Objective Questions: Aptitude and basic C objective problems.

2 Subjective Questions:
I. Given a linked list containing character in each node, segregate its nodes in such a way that all nodes containing a vowel are moved to the end of the linked list. We will have to maintain the order.
II. Parenthesis checker.

Interview Round 1(50 mins)

Question 1: You are given two linked lists whose nodes contain a digit as data member. Both lists represent a number. You have to add them and return the resultant list.
Input: 9->9->3->4->5 and 8->9->1 (represent 99345 and 891)
Output: 1->0->0->2->3->6
My Solution: Reverse the linked lists. Create the new sum list which is reversed. Finally reverse the resultant list.

Question 2: Interviewer asked to solve the above question without changing the original lists.
My Solution: Count number of nodes in both lists. If equal then simply add two lists recursively. If not then advance a temp ptr which is a pointer to head of larger list by diff of nodes and then add the list pointed by temp and list 2. Make sure to keep track of carry. Add recursively. Propagate the carry in remaining elements of larger list. Was asked to code. Coded it.

Interview Round 2(60 mins)

Question 1: Delete nth node from end of a linked list in a single scan.

Question 2: In a linked list, in addition to the next ptr, a random ptr is also present. Clone the linked list.
Did it in O(n) but by modifying the linked list and then restoring it. Was asked to do it without making any modifications in the original list. Did that in O(n^2)

Question 3: Two nodes of a BST are given. Print the path from 1st node to the 2nd node. You are also provided the parent pointers in addition to normal left and right pointers.

Interview Round 3(1 hour)

Question 1: An array of n integers is there in which the range of elements is n, i.e., the difference between maximum and minimum number is n. Find the repeating numbers.

Question 2: An extension of Question 1. Was asked to find number of times each number is repeated.

Question 3: There are n frames of m data element each. The data element in each frame is arranged in increasing order. You are provided m*n space in which you have to arrange all data in increasing order.

My 1st solution was to use merge sort. He modified the question as only O(n) space is there and you need to send data in increasing order as fast as you can.
My 2nd solution was to use min heap and construct it with the 1st element of all n frames. Min heap also contains extra field which signifies the frame number of data elements. This data structure can do the needful.

Interview Round 4(1 hour)

Question 1: Replace each element of an array with its greatest next integer in O(n).
I couldn’t do it. I tried but it didn’t click. Not expected when you are in your last round.

Question 2: Reverse every k nodes of a linked list.

Well did that but was not finally selected……. :(

This article is compiled by Vinay Khetan. We will be soon publishing Vinay’s Yahoo and Microsoft interviews as separate posts. Vinay was selected in Microsoft. Many Many congratulations to Vinay for his selection.

If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to contribute@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

7 comments so far

  1. icanth says:
    August 28, 2012 at 6:34 AM
    Round 4-2

     void list_reserve (List *list, const int k) { if ( list == NULL || *list == NULL ) return; Node *p = (*list) - > next, *q = *list; for(int i = 1; i < k && p != NULL; i++) { Node *tmp = p - > next; p - > next = q; q = p; p = tmp; } // for Node *head = *list; (*list) - >next = p; *list = q; list_reserve(& head - >next, k); } // list_reserve 

    Reply

  2. Sunil Rai says:
    August 27, 2012 at 11:59 PM
    //Parenthesis checker

    #include

    #define max 15
    int error=0,top=0,stack[max];

    void push(int n){
    if(top==max-1)
    printf(“overflow\n”);
    else {
    if(top==0 || stack[top-1]>=n)
    stack[top++]=n;
    else error=1;
    }
    }

    void pop(int n){
    if(top==0)
    printf(“underflow\n”);
    else if(top==0 && stack[–top]!=n)
    error=1;
    }

    void par_num(char ch){
    if(ch=='[‘)
    push(3);

    else if(ch=='{‘)
    push(2);

    else if(ch=='(‘)
    push(1);
    else if(ch==’]’)
    pop(3);
    else if(ch==’}’)
    pop(2);
    else if(ch==’)’)
    pop(1);
    }
    void main(){
    char ch;
    printf(“enter the paranthesis sequence”);
    do{
    scanf(“%c”,&ch);
    par_num(ch);
    }while(error!=1 && ch!=’\n’);

    if(error!=1)
    printf(“correct paran sequence”);
    else printf(“wrong paran sequence”);
    }

    Reply

  3. leet says:
    August 27, 2012 at 10:02 PM
    Plz explain the ques 1 Round 4(replace with next greatest).
    I am not getting it .plz give example.waht do you mean by greatest next integer.
    thanks

     /* Paste your code here (You may delete these lines if not writing code) */ 

    Reply

  4. Amit says:
    August 27, 2012 at 9:55 PM
    round 4-ques 2

     void revalt(struct node **head,int k) { struct node *p=*head,*q,*r; int j=k; if(!p || !(p - >next)) return; q = p - >next; r = q - >next; while(r && j!=1) { q -> next=p; p = q; q = r; r = r - >next; j--; } if(j != 1) { printf("insufficient no. of nodes\n"); (*head) - >next = r; q - >next = p; *head = q; return; } (*head) - >next = q; r = *head; *head = p; revalt(&q, k); r - >next = q; } 

    Reply

    • Amit says:
      August 27, 2012 at 9:56 PM
      void revalt(struct node **head,int k)
      {
      struct node *p=*head,*q,*r;
      int j=k;
      if(!p || !(p->next))
      return;
      q=p->next;
      r=q->next;
      while(r && j!=1)
      {
      q->next=p;
      p=q;
      q=r;
      r=r->next;
      j–;
      }
      if(j!=1)
      {
      printf(“insufficient no. of nodes\n”);
      (*head)->next=r;
      q->next=p;
      *head=q;
      return;
      }
      (*head)->next=q;
      r=*head;
      *head=p;
      revalt(&q,k);
      r->next=q;
      }

      Reply

  5. SUNIL says:
    August 27, 2012 at 7:19 PM

     /*Given a linked list containing character in each node, segregate its nodes in such a way that all nodes containing a vowel are moved to the end of the linked list. We will have to maintain the order.*/ #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; /* Link list node */ typedef struct list{ char data; struct list *next; }node; /* A utility function to insert a node at the end of a linked list*/ void insert(node **h,char ch){ node *temp,*trav=*h; temp=(node *)malloc(sizeof(node)); temp-&gt;data=ch; temp-&gt;next=NULL; if((*h)==NULL) *h=temp; else{ while(trav-&gt;next!=NULL) trav=trav-&gt;next; trav-&gt;next=temp; } } /* A utility function to print a linked list*/ void print(node *h){ while(h){ printf(&quot;%c &quot;,h-&gt;data); h=h-&gt;next; } } /* A utility function to check if given data is a vowel*/ int check_vowel(char ch){ if(ch=='A'||ch=='a'||ch=='E'||ch=='e'||ch=='I'||ch=='i'||ch=='O'||ch=='o'||ch=='U'||ch=='u') return 1 ; else return 0 ; } /*function to push the vowels at the end of list maintaining relative order*/ void rearrange(node **h){ node *last=*h,*limit,*trav=*h,*prev=*h; while(*h &amp;&amp; last-&gt;next) last=last-&gt;next; limit=last; while(trav!=limit){ if(check_vowel(trav-&gt;data)){ last-&gt;next=trav; last=trav; prev-&gt;next=trav-&gt;next; trav=trav-&gt;next; if(trav==*h){ prev=trav; *h=trav; } last-&gt;next=NULL; } else { prev=trav; trav=trav-&gt;next; } } } //main body void main(){ node *head=NULL; char ch; int i,n; printf(&quot;enter the no of characters in name to be inserted&quot;); scanf(&quot;%d&quot;,&amp;n); printf(&quot;enter the name to be inserted&quot;); for(i=0;i&lt;=n;i++){ scanf(&quot;%c&quot;,&amp;ch); insert(&amp;head,ch); } printf(&quot;\n&quot;); print(head); rearrange(&amp;head); printf(&quot;\n&quot;); print(head); } 

    Reply

  6. Elena says:
    August 27, 2012 at 2:03 PM
    Hi,

    How did you solve question 2, round 2 (the one with the random pointer)?//please explain me briefely both solutions

    I was thinking that pointers are in fact integer numbers. I would start parsing the list as a graph/tree (I would use a hash to keep track of the already visited nodes). I don’t have the complete solution, but it wouldn’t modify the original list and it would be in O(n); the bad thing is that you have to use some extra-memory….
    What do you think about this solution? Sounds..ok?:D

    Many thanks,
    Elena

    Reply

Comment

Click here to cancel reply.
Name (Required) Email (Required) Website URI Your Comment (Writing code? please paste your code between sourcecode tags)

 /* Paste your code here (You may delete these lines if not writing code) */ 
  • Loading
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s