Microsoft Interview Question for Software Engineer in Tests


Team: SDET
Country: India
Interview Type: Written Test




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

Its easy take two pointers increment one pointer by one and the other pointer by two and then
1.First find the meeting point of these two pointers.
2.After finding the meeting point take the first pointer to the start that is head and then increment n1 and n2 both by one until they point to the same value
Here is the code
LinkedListNode FindBeginning(LinkedListNode head) {

LinkedListNode n1 = head;

LinkedListNode n2 = head;


// Find meeting point

while (n2.next != null) {

n1 = n1.next;

n2 = n2.next.next;

if (n1 == n2) {

break;

}

}

// Error check - there is no meeting point, and therefore no loop

if (n2.next == null) {

return null;

}

/* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps

/* from the Loop Start. If they move at the same pace, they must

* meet at Loop Start. */

n1 = head;

while (n1 != n2) {

n1 = n1.next;

n2 = n2.next;

}

// Now n2 points to the start of the loop.

return n2;
}

- vgeek May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess there is a small mistake...// Find meeting point
while (n2.next != null)
==>
while (n2!=null && n2.next!=null)

- Anonymous September 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@zammer: care to give an example?

- aka May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1-->2-->3-->4-->5-->7-->8-->9-->10-->

suppose there is a linked list where 10 th node will point to 4 rth node , so there will be a loop . In that case 4th will be start node and 10 th will be the last node .

- zammer May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Zammer but as its a linked list and you dont have index so the very next node of the 10th can also hold the same value as of 4th so how will you distinguish as if its the repeated one or the new one?

- Jay May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Zammer but as its a linked list and you dont have index so the very next node of the 10th can also hold the same value as of 4th so how will you distinguish as if its the repeated one or the new one?

- Jay May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is very simple.Just find out the intersection point in this case 4 element but in the process of finding intersection point we should just keep track of previous node whose next node is the intersection point.

- aka May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

find_out(node *root)
{
        node *slow, *fast, *temp, *before_pointer;
	/* find out the intersection point */
        slow = root;
        fast = slow->next->next;
        while(slow != fast) {
                slow = slow->next;
                fast = fast->next->next;
        }
	/* ok now reset slow pointer to the start of node and
            fast pointer is pointing to the intersection point */
        temp = fast;
        slow = root;
        while(temp != slow) {
		/* before_pointer is just before the intersection point
                    i.e. last node as referred to in the question */
                before_pointer = temp;
                temp = temp->next;
                slow = slow->next;
        }
        printf("last data is %d\n", *before_pointer);
}

- aka May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Jay, the nodes don't have indexes but have memory address. In my solution has a Hash Table to find repeated address in the list traversal .

- thiago.xth1 May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you know at which node the loop originates then you can easily find the last node in the loop.
To find where the loop starts, apply the tortoise and hare concept of fast and slow pointer. When you run two pointers from the head with speed 1 and 2, they both meet at a certain node say X.
Now this node X will be at the same distance from the origin of loop as distance between head and origin of loop.

In your case above, the two pointers meet at node 8.
8->9->10->4
1->2->3->4

These lengths will always be same. Try any case you like.
Cheers

- Tarang May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please explain...because in the above example..initially slow node will be 1 and fast node will be 3...and as it proceeds..it will be 2,5 3,7 4,9 5,4 6,6 and the intersection node would be 6...please mention the mistake which i have done...

- piyush May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I initialized both pointers at 1 and then its 2,3 - 3,5 - 4,7 - 5,9 - 6,4 - 7,6, - 8,8

- Tarang May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why it is so? Why the distance of the intersection is always same from the head as the current node?

- Sumit May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why the distance is always the same? can you explain it? I don't know how to think it.

- yueming May 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

ListNode* loopLastNode(ListNode *head)
{
ListNode *snode = head;
ListNode *qnode = head->next;
int scount = 1;

while (qnode && snode && qnode!=snode) {
++scount;
snode = snode->next;
qnode = qnode->next;
if (!qnode)
break;
qnode = qnode->next;
}

if (!qnode || !snode)
return NULL;


int qcount = 1;
qnode = qnode->next;
while (qnode != snode) {
++qcount;
qnode = qnode->next;
}

int maxcount = max(qcount,scount);

qnode = snode->next;
for (int i=0; i<maxcount-scount; ++i)
qnode = qnode->next;

snode = head;
for (int i=0; i<maxcount-qcount; ++i)
snode = snode->next;

while (qnode->next != snode->next) {
qnode = qnode->next;
snode = snode->next;
}

return qnode;
}

- Anonymous May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous: logic?

- undefined May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry for my poor english

1) find the loop and the specific node
2) find the intersection of the loop list and the orginal list
1.scount Nodes from orginal list head to the specific node
2.qcount Nodes from loop list head to the specific node
3.forward snode or qnode until snode and qnode have same count of nodes to the specifice node
4.forward snode and qnode until the intersection

- Anonymous May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my solution. I use a implicit HashTable.

Node * find_least(Node *root) {
	HashTable H;
	H.insert((int)root);
	while (node != NULL) {
		if (H.has(node->next)) {
			break;	
		}
		node = node->next;
	}
	return node;
}

- thiago.xth1 May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a way that came to my mind.
-Start traversal.
-Keep track of current pointers in the process, Lets say a hash set allHashsets<Pointers>.
-if allHashsets<Pointers> contains next pointer. current element is the last element

in the example: 1-->2-->3-->4-->5-->7-->8-->9-->10-->
check if next pointer is in the hashset? the pointer for 1 will not be in the hash set so this means 1 is not the last element. add the pointer for 1 in the hashset. when the traversal reaches 10, the next pointer will be in the hashset. this means the last element is the current one.

- Prithvi May 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

amarendra

- Anonymous May 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it is very simple.Just find out the intersection point in this case. in the process of finding intersection point we should just keep track of previous node whose next node is the intersection point.
here is the code..

struct node
{
	int a;
	node *next;
};
#include<iostream>
using namespace std;
void insert(node **head,int data);
void printList(node *head);
node * get_last_node_loop(node *head);
int main()
{
	node *head = NULL;
	for(int i = 10;i>0;i--) insert(&head,i);
	//Print list having no  loop
	printList(head);
	//Create  a cycle
	node *temp = head;
	for(int i = 0;i<9;i++) temp = temp->next;
	temp->next = head->next->next->next->next;
	node *last = get_last_node_loop(head);
	cout<<"Last = "<<last->a<<"\n";
	return 0;
}
void insert(node **head,int data)
{
	node *newnode = new node;
	newnode->a = data;
	newnode->next = *head;
	*head = newnode;
}
void printList(node *head)
{
	while(head!=NULL)
	{
		cout<<head->a<<"-->";
		head = head->next;
	}
}
node * get_last_node_loop(node *head)
{
	//little variation in the loop finding code
	node * slow = head,*fast = head;
	
	slow = head->next;
	fast = head->next->next;
	while(slow!=fast)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	slow = head;
	node *prev ;
	while(slow!=fast)
	{
		prev = fast;
		slow = slow->next;
		fast = fast->next;
	}
	return prev;
}

- Sarthak Mall June 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a simple approach that is not cryptic at all and everybody should be able to understand.

1. One slow 1x and one fast pointer 2x. For instance, start slow one from first and fast one from second node.

2. When they meet, that has to be inside the loop. Say, they meet at node X.

3. Starting from X go to next until you come back to X again. Keep a count of number of other nodes you hit. Say, that's N. N is the number of nodes in the loop minus 1(X).

4. Take 2 pointers p1 = StartNodeOfLinkedList and p2 = StartNodeOfLinkedList.next().next()...N times.

5. Increment p1 an p2 until p2.next() == p1. p2 is the last node of the loop.

- pretentious.bastard March 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rohit: read the question again.

- aka May 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you fool!

- undefined May 29, 2013 | 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