Microsoft Interview Question for Software Engineer in Tests






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

1. Do a merge sort O(nlogn)
2. Apply the code of removal of duplicates in L.List O(n).

Total complexity: O(nlogn).

Can anyone put their comments?

- particularraj November 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Ahh.. 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.

- MSrej March 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Theoretically, yes.

for(i = 0 to 1114111)
for(j = 0 to n)
if(value[j] == i) if (flag) delete cur, else set flag.

O(1114111 n) = O(n)

- Anonymous August 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- zwfreesky March 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

then why not use merge sort, it can be applied on linked list, and always has complexity of O(nlogn)

- summer March 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

isn't that merge sort takes extra memory?

- Anonymous March 10, 2009 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think you can implement merge sort on linked list without taking extra memory

- summer March 10, 2009 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@summer,

Merge sort's Merge operation incurs extra memory.

- peace November 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Summer is right. You can do merge sort on linked list without using extra memory since merging of linked lists can be done in place.

- @peace March 12, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- T March 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- MSrej May 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

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

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

- Nick April 21, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- joy May 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Unicode characters range between 0 and 1,114,111. ASCII characters range between 0 and 255.

- mg August 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- dev May 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

who said we can change the order of the original node?
sorting will change the original node sequence.

- Anonymous July 17, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

(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).

- Anubhav June 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Really Good solution...

- Mark Antony June 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mals August 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Mals August 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sort the linked list with insertion sort or whatever. then it is easy to remove the duplicate. just compare n with n+1 if they are same delete it.

- handsomefellow March 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

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

True... This is called Counting sort... But this requires a whole bunch of extra memory... though under certain constraints, it can sort in O(n) and while sorting , u can check and remove your duplicates.... so its still O(n)

- Hmm... May 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- elios786 May 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 08, 2009 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

you dumb ass, merge sort requires random access, and do you know what that is? now shut up

- Anonymous January 05, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

please do not use obnoxious words...and do not try to be smart... If you know the solution ..then post it....This community is for discussion and doubts clearing...so ...you should answer ..in appreciating manner.............

- Anonymous March 06, 2010 | Flag


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