Microsoft Interview Question
Software Engineer in TestsAhh.. forgot to add interviewer wanted to know if there is a better solution than O(N square) without using extra memory. O(N2) solution would be to start from head and go till the end and see if the value is there. Repeat the process from the second node and so on.
Can we change the position of the element?
We can do a quick sort on the link list which is O(n*logn), and then do a traversal from the beginning to end and eleminate the duplicated elements (O(n)).
So the complexity of this algorithm is O(n*logn)
I have a question, how can we quick sort on linklist?
then why not use merge sort, it can be applied on linked list, and always has complexity of O(nlogn)
MSrej, are you sure the interviewer said, "no extra memory"? Did he mean O(1) extra space is allowed, instead? And the "no extra memory" constraint is just your interpretation?
If no extra memory is allowed, then you cannot even have pointers to access the list.
Please, get the question right before posting it. There are too many ambiguous questions being posted here.
I only say this because it is specifically mentioned that the data is Unicode characters, in which case I think, with O(1) space usage, there is an O(n) time solution.
Hi,
sorry coming here after a long time. To answer your question, the main aim of the question was to solve this problem with minimum or no extra data-structures. When I said pointers is allowed then I guess it implies you can use O(1) space (I may be wrong on this implication and that is why I am 'MSrej')
I think the fact why the interviewer has explicitly mentioned about the unicode is a hint to the solution. One can use bitmap structure to solve this problem. Unicode characters go from 0-255 i.e one byte long. If each integer is of 16 bits then we will need 16 intergers to represent the bitmap structure. Thus an array of 16integers is the constant extra memory you need irrespective of the linked list length to remove all duplicates in O(n) time complexity. Does this sound fexible?
Can you or someone else please elaborate on this solution? I did some search on google and couldn't find any examples on unicode characters.
In response to the above solution;
- What is a bitmap structure?
- I thought the size of unicode characters is 2 bytes. Please clarify this point.
Would really appreciate a response from someone.
Thanks,
Nick
(a) Merge sort the link list(recursively) which is O(nlogn) without requiring extra storage although some pointers are required.
(b)Traverse the sorted list and remove duplicates O(n)
Node<T>* Chain<T>::GetNthNode(int num)
{
Node<T> *prev = first, *temp = first;
for(int x= 0 ; x < num && prev ; x++)
{
prev = temp;
temp = temp->GetNext();
}
return prev;
}
template<typename T>
void Chain<T>::Swap(Node<T> *first, Node<T> *second)
{
T temp = second->GetData();
second->SetData(first->GetData());
first->SetData(temp);
}
template<typename T>
void Chain<T>::sort(int left , int right)
{
int i = left;
int j = right;
int mid = (i+j)/2;
do
{
while(GetNthNode(i)->GetData() < GetNthNode(mid)->GetData())
i++;
while(GetNthNode(j)->GetData() > GetNthNode(mid)->GetData())
j--;
if (i <= j)
{
Swap(GetNthNode(i),GetNthNode(j));
i++;
j--;
}
}
while(i<=j);
if (left < j) sort(left,j);
if (i < right) sort(i,right);
}
(Use Hashing)
We traverse the link list from head to end. For every newly encountered element, we check whether it is in the hash table: if yes, we remove it; otherwise we put it in the hash table.
Thanks to bearwang for suggesting this method.
Time Complexity: O(n) on average (assuming that hash table access time is O(1) on average).
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
node *next;
};
node *newnode(char c)
{
node *p=new node;
p->data=c;
p->next=NULL;
return p;
}
void removedup(node *&head)
{
bool visited[256]={false};
node *p=head;
node *prev=NULL;
while(p)
{
if(!visited[p->data])
{
visited[p->data]=true;
prev=p;
p=p->next;
}
else
{
prev->next=p->next;
p=p->next;
}
}
}
void display(node *head)
{
while(head)
{
cout<<head->data<<" ";
head=head->next;
}
}
int main()
{
node *head=newnode('z');
head->next=newnode('m');
head->next->next=newnode('m');
head->next->next->next=newnode('z');
head->next->next->next->next=newnode('q');
removedup(head);
display(head);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct node{
char data;
node *next;
};
node *newnode(char c)
{
node *p=new node;
p->data=c;
p->next=NULL;
return p;
}
void removedup(node *&head)
{
bool visited[256]={false};
node *p=head;
node *prev=NULL;
while(p)
{
if(!visited[p->data])
{
visited[p->data]=true;
prev=p;
p=p->next;
}
else
{
prev->next=p->next;
p=p->next;
}
}
}
void display(node *head)
{
while(head)
{
cout<<head->data<<" ";
head=head->next;
}
}
int main()
{
node *head=newnode('z');
head->next=newnode('m');
head->next->next=newnode('m');
head->next->next->next=newnode('z');
head->next->next->next->next=newnode('q');
removedup(head);
display(head);
return 0;
}
Insert Sort is O(N*N). Quick Sort needs to swap elements, probably not fit for link list. Merge Sort is the O(N*logN) solution. If the data set is limited(say < k), you can get less than k*N operation.
Merge sort has space complexity of O(n), and it violates the given space constraint. Heap sort uses O(1) space and O(nLogn) time complexity. But I'd rather go with quicksort, of which space is O(1) if implemented properly, because it's faster than heap sort in many practical cases.
if using array, mergesort requires extra space to store sorted array. using linked list, mergesort requires no extra space and is very easy to be implemented
you dumb ass, merge sort requires random access, and do you know what that is? now shut up
1. Do a merge sort O(nlogn)
- particularraj November 02, 20092. Apply the code of removal of duplicates in L.List O(n).
Total complexity: O(nlogn).
Can anyone put their comments?