Amazon Interview Question for Applications Developers


Country: India




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

if this is a singly linked list,
for (nodes: node list)
- add node to hashset
- check if node.next exists in the hashset
- if it does, node.next = node.next.next
- node= node.next

This eliminates having to use the "previous" node

- Anonymous October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

If we are allowed to use extra space then we can use hashmap. This way it is simple on pass traversal.
Time Complexity = O(n)
Space Complexity = O(n)
----------------------------------------------------------
Without using any extra space.
Time Complexity = O(n^2)
Space Complexity = O(1)

struct node * removeDuplicates(struct node * head)
{
      struct node* slow = head, fast;
      while(slow != NULL)
      {
            fast = slow;
            while(fast->next != NULL)
            {
                if(slow->data == fast.next.data)
                {
                    fast->next = fast->next->next;
                }
                else
                {
                    fast = fast->next;
                 }     
           }
           slow = slow->next;
     }
     return head;
}

- Nitin Gupta November 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why it is O(n^2)..can u plz explain

- sastry.soft November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sastry.soft - Its simple, for each node we are checking data of all subsequent nodes (see two while loops) hence complexity is O9n^2).

But if we go deeper and link list contains many duplicates then the size of link list will be decremented each time and complexity will be less than O(n^2).

But in worst case i.e. there are no duplicates it will be O(n^2)

- Nitin Gupta November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why don't sort first? use nlgn time to sort, use n time to find the duplicates. So it's nlgn

- Anonymous November 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if there is a constraint that we cannot modify original link list. Its always better not to modify original data as far as possible.

- Nitin Gupta November 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, order in a list is usually important, they often need to be preserved.

- Chris November 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

if it is a double linked list:

HashSet<T> set = new HashSet<T>();
while(linkedlistElement.next != null) {
if (!set.contains(linkedlistElement)) {
set.add(linkedlistElement);
} else {
linkedlistElment.previous = linkedlistElment.next;
linkedlistElment.next.previous = linkedlistElment.previous
}
}

- Meng Wang October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the link list and keep on adding element to the Set. If the set returns false, then remove the element from link list.

- nishant October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HASH table is better than SET. STL SET is implemented Balance Binary Tree. It it takes O(logN) to find the duplicate. HASH table only takes O(1).

Use data structure to determine if nodes are duplicates as the key. If more than one data, use the joint. Think about boos hash table.

- peter tang October 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this coding is wrong...it doesnot deleted duplicate record

- nidhi November 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sry by mistake i have typed this... :-( sry..

- nidhi November 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node{
int data ;
struct node* link ;
};
int main()
{ node *start=NULL,*prev,*prev2,*a,*start2 ;
char ch='y' ;
int u ;


while(ch!='n')
{
if(start==NULL)
{
start=(node*)malloc(sizeof(node));
prev=start ;
start2=start ;
printf("enter the data\n");
scanf("%d",&(start->data));
start->link=NULL ;

}
else
{
a=(node*)malloc(sizeof(node));
printf("enter the data\n");
scanf("%d",&(a->data));
prev->link=a ;
a->link=NULL ;
prev=prev->link ;
}
printf("wanna continue??\n");
fflush(stdin);
scanf("%c",&ch);
}
printf("linked list is \n");
while(start2!=NULL)
{
printf("%d->",start2->data);
start2=start2->link ;
}
printf("\n20\n");
prev=start ;
start2=start ;
prev2=start ;
while(start2!=NULL)
{
u=start2->data ;
printf("\n%d",u);
printf("\nerror\n");

for(prev=start2->link;prev!=NULL;prev=prev->link)
{
if(u==prev->data)
{ printf("\nerror22\n");

prev2->link=prev->link ;

//free(prev);

}
else
{
prev2=prev2->link ;
}
}


start2=start2->link ;
prev2=start2 ;

}
printf("linked list after removal of duplicates is \n");
start2=start ;
printf("%d\n",start);
while(start2!=NULL)
{
printf("%d->",start2->data);
start2=start2->link ;
}




getch();
return 0 ;
}

- umesh garg December 29, 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