Microsoft Interview Question
Software Engineer in TestsTeam: SDET
Country: India
Interview Type: Written Test
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 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?
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.
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);
}
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
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...
Why it is so? Why the distance of the intersection is always same from the head as the current node?
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;
}
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
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.
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;
}
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.
Its easy take two pointers increment one pointer by one and the other pointer by two and then
- vgeek May 28, 20131.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;
}