Amazon Interview Question
Applications DevelopersCountry: India
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;
}
@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)
Why don't sort first? use nlgn time to sort, use n time to find the duplicates. So it's nlgn
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.
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
}
}
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.
#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 ;
}
if this is a singly linked list,
- Anonymous October 31, 2012for (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